av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁(yè)技術(shù)文章
文章詳情頁(yè)

詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)

瀏覽:4日期:2022-08-22 17:32:03

一, 斐波那契搜索算法簡(jiǎn)述

斐波那契搜索(Fibonacci search) ,又稱(chēng)斐波那契查找,是區(qū)間中單峰函數(shù)的搜索技術(shù)。

斐波那契搜索采用分而治之的方法,其中我們按照斐波那契數(shù)列對(duì)元素進(jìn)行不均等分割。此搜索需要對(duì)數(shù)組進(jìn)行排序。

與二進(jìn)制搜索不同,在二進(jìn)制搜索中,我們將元素分成相等的兩半以減小數(shù)組范圍-在斐波那契搜索中,我們嘗試使用加法或減法來(lái)獲得較小的范圍。

斐波那契數(shù)列的公式是:

Fibo(N)=Fibo(N-1)+Fibo(N-2)

此系列的前兩個(gè)數(shù)字是Fibo(0) = 0和Fibo(1) = 1。因此,根據(jù)此公式,該級(jí)數(shù)看起來(lái)像是0、1、1、2、3、5、8、13、21。。。這里要注意的有趣觀察是:

Fibo(N-2) 大約是1/3的 Fibo(N) Fibo(N-1) 大約是2/3的 Fibo(N)

因此,當(dāng)我們使用斐波那契數(shù)列來(lái)劃分范圍時(shí),它會(huì)以與上述相同的比率進(jìn)行分割。

二,斐波那契搜索算法代碼實(shí)現(xiàn)

/** * * @param integers * @param elementToSearch * @return */ public static int fibonacciSearch(int[] integers, int elementToSearch) { int fibonacciMinus2 = 0; int fibonacciMinus1 = 1; int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; int arrayLength = integers.length; while (fibonacciNumber < arrayLength) { fibonacciMinus2 = fibonacciMinus1; fibonacciMinus1 = fibonacciNumber; fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; } int offset = -1; while (fibonacciNumber > 1) { int i = Math.min(offset+fibonacciMinus2, arrayLength-1); if (integers[i] < elementToSearch) { fibonacciNumber = fibonacciMinus1; fibonacciMinus1 = fibonacciMinus2; fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; offset = i; } else if (integers[i] > elementToSearch) { fibonacciNumber = fibonacciMinus2; fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2; fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; } else return i; } if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch) return offset+1; return -1; }

三,斐波那契搜索算法總結(jié)

首先從找到斐波那契數(shù)列中最接近但大于數(shù)組長(zhǎng)度的數(shù)字開(kāi)始。這fibonacciNumber是在13剛好大于數(shù)組長(zhǎng)度10時(shí)發(fā)生的。

接下來(lái),我們比較數(shù)組的元素,并根據(jù)該比較,執(zhí)行以下操作之一:

將要搜索的元素與處的元素進(jìn)行比較fibonacciMinus2,如果值匹配,則返回索引。 如果elementToSearch比當(dāng)前元素時(shí),我們移動(dòng)在斐波納契數(shù)列上一步,而改變的值fibonacciNumber,fibonacciMinus1與fibonacciMinus2相應(yīng)。偏移量將重置為當(dāng)前索引。 如果elementToSearch比當(dāng)前元素小,我們繼續(xù)前進(jìn)后退兩步在斐波納契數(shù)列和改變的值fibonacciNumber,fibonacciMinus1與fibonacciMinus2相應(yīng)。

輸出結(jié)果:

詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)

時(shí)間復(fù)雜度

此搜索的最壞情況時(shí)間復(fù)雜度為O(log(N))。

空間復(fù)雜度

雖然我們需要將三個(gè)數(shù)字保存在斐波那契數(shù)列中并要搜索的元素,但我們需要四個(gè)額外的空間單位。

對(duì)空間的要求不會(huì)隨著輸入數(shù)組的大小而增加。因此,可以說(shuō)斐波那契搜索的空間復(fù)雜度為O(1)。

當(dāng)除法運(yùn)算是CPU要執(zhí)行操作時(shí),將使用此搜索。二進(jìn)制搜索之類(lèi)的算法由于使用除法對(duì)數(shù)組進(jìn)行劃分,因此效果較差。

這種搜索的另一個(gè)好處是當(dāng)輸入數(shù)組的元素?zé)o法放入RAM中時(shí)。在這種情況下,此算法執(zhí)行的局部操作范圍可幫助其更快地運(yùn)行。

四,跳轉(zhuǎn)搜索算法完整代碼

If you are interested, try it.

public class SearchAlgorithms { /** * * @param integers * @param elementToSearch * @return */ public static int fibonacciSearch(int[] integers, int elementToSearch) { int fibonacciMinus2 = 0; int fibonacciMinus1 = 1; int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; int arrayLength = integers.length; while (fibonacciNumber < arrayLength) { fibonacciMinus2 = fibonacciMinus1; fibonacciMinus1 = fibonacciNumber; fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; } int offset = -1; while (fibonacciNumber > 1) { int i = Math.min(offset+fibonacciMinus2, arrayLength-1); if (integers[i] < elementToSearch) { fibonacciNumber = fibonacciMinus1; fibonacciMinus1 = fibonacciMinus2; fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; offset = i; } else if (integers[i] > elementToSearch) { fibonacciNumber = fibonacciMinus2; fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2; fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; } else return i; } if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch) return offset+1; return -1; } /** * 打印方法 * @param elementToSearch * @param index */ public static void print(int elementToSearch, int index) { if (index == -1){ System.out.println(elementToSearch + ' 未找到'); } else { System.out.println(elementToSearch + ' 在索引處找到: ' + index); } } //測(cè)試一下 public static void main(String[] args) { int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67); print(67, index); }}

到此這篇關(guān)于詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java Fibonacci Search 內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)!

標(biāo)簽: Java
相關(guān)文章:
主站蜘蛛池模板: h片在线播放 | 特级毛片www | 夜夜爽99久久国产综合精品女不卡 | 国产区在线视频 | 亚洲黄色国产 | 亚洲欧美在线观看 | 成人欧美一区二区三区黑人孕妇 | 欧美二区在线 | 国产精品成人在线观看 | 天天干天天爱天天爽 | 91久操网| 久久久成 | 成人精品视频在线观看 | 成人国产精品久久久 | 亚洲 欧美 日韩 精品 | 日韩一级一区 | 免费成人在线网站 | 国产精品自拍啪啪 | 日韩国产高清在线观看 | 国产91在线视频 | 国产精品久久久久久238 | 91精品国产综合久久婷婷香蕉 | 成人在线中文字幕 | 九九免费在线视频 | 中文字幕在线第一页 | 欧美精品在线免费 | 色www精品视频在线观看 | 一区二区视屏 | 欧美在线视频一区 | 国产伦精品一区二区三区四区视频 | 日韩免费一区二区 | 久久精品福利视频 | 精品一区二区三区在线观看 | 成人免费毛片片v | 色爱区综合 | 久久久久免费精品国产小说色大师 | 国产欧美在线 | 精品在线观看入口 | 国产精品一区二区欧美黑人喷潮水 | 日韩性生活网 | 国产一区二区在线播放 |