文档章节

常见的查找算法(四):斐波那契查找

o
 osc_wws45aot
发布于 2019/08/20 22:23
字数 769
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  斐波那契搜索技术是一种使用分而治之算法搜索排序数组的方法,该算法借助斐波纳契数来缩小可能的位置。二元搜索相比,排序数组被分成两个大小相等的部分,其中一个进一步检查,斐波那契搜索将数组分成两个部分,其大小为连续的斐波纳契数。平均而言,这导致执行的比较增加了大约4%,但它的优点是只需要加法和减法来计算被访问数组元素的索引,而经典二进制搜索需要比特移位,除法或乘法,这些操作在Fibonacci搜索时首先不常见出版。Fibonacci搜索具有O(log n的平均和最差情况复杂度。

  总的来说是二分查找的一个优化。

  Fibonacci序列具有一个数字是其前面两个连续数的总和的属性。因此,可以通过重复添加来计算序列。两个连续数字的比率接近黄金比率,1.618 ...二进制搜索通过将搜索区域除以相等的部分(1:1)来工作。Fibonacci搜索可以将其分成接近1:1.618的部分,同时使用更简单的操作。

 

  构建斐波那契序列数组(越到后面,前一个数与后一个数的比例接近0.618):

1     //构建斐波那契数列
2     public static void fibonacci(int[] F) {
3         F[0] = 0;
4         F[1] = 1;
5         for (int i = 2; i < max_size; ++i)
6             F[i] = F[i - 1] + F[i - 2];
7         System.out.println(Arrays.toString(F));
8     }

  斐波那契查找算法:

 1     public static int fibonacciSearch(int[] a, int n, int key) {
 2         int low = 0;
 3         int high = n - 1;
 4 
 5         int F[] = new int[max_size];
 6         fibonacci(F);//构建斐波那契数组
 7 
 8         //计算 n 位于斐波那契数列的位置
 9         int k = 0;
10         while (n > F[k] - 1)
11             ++k;
12 
13         //将数组a扩展到F[k]-1的长度
14         int tmp[];
15         tmp = new int[F[k] - 1];
16         System.arraycopy(a, 0, tmp, 0, n);
17 
18         for (int i = n; i < F[k] - 1; ++i)
19             tmp[i] = a[n - 1];//用数组最后一个元素扩展
20 
21         while (low <= high) {
22             int mid = low + F[k - 1] - 1;//借助斐波纳契数确定位置
23             if (key < tmp[mid]) {
24                 high = mid - 1;
25                 k -= 1;
26             } else if (tmp[mid] < key) {
27                 low = mid + 1;
28                 k -= 2;
29             } else {
30                 if (mid < n)
31                     return mid;
32                 else
33                     return n - 1;
34             }
35         }
36         tmp = null;
37         return -1;
38     }

  如果被搜索的元素具有非均匀访问存储器存储(即,访问存储位置所需的时间根据所访问的位置而变化),则斐波那契搜索可能具有优于二分搜索的优势,从而略微减少访问所需的平均时间存储位置。

  最坏情况下,时间复杂度为O(log2n),且其期望复杂度也为O(log2n)。

  测试代码:

1     public static void main(String[] args) {
2         int a[] = {0, 16, 24, 35, 47, 59, 62, 73, 132};
3         int key = 132;
4         int index = fibonacciSearch(a, a.length, key);
5         System.out.println(key + " is located at " + (index+1));
6     }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
数据结构(六)查找---有序表查找(三种查找方式:折半,插值,斐波拉契查找)

前提 有序表查找要求我们的数据是有序的,是排序好的,我们只需要进行查找即可 我们下面将介绍折半查找(二分查找),插值查找,斐波那契查找 一:折半查找 (一)定义 二分查找也称折半查找...

osc_3md1xrlp
2018/08/19
3
0
有序表查找

好久没上博客园了,之前说好的一周写一个博客来记录自己的考研计划也落空了。 忙着复习,好久都没有打开电脑,计划也都是写在纸上了。最新开始数据结构的复习才打开了电脑。 开始敲代码的感觉...

osc_4g93n6bo
2018/07/17
3
0
常用的查找算法(末)

三:插值查找 插值查找类似二分查找,不同点在于二分查找是从mid中值开始,而插值查找可以从自己定义的mid处开始查找,同样达到二分查找的效果,并且效率比二分查找好一点。 (二分查找法公式...

魍宂庞
05/27
8
0
斐波那契查找算法(黄金分割查找算法)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

yimixgg
03/31
0
0
(8)《数据结构与算法》之查找算法

在java中,我们常见的查找有四种 顺序查找,也叫线性查找 二分查找,也叫折半查找 插值查找 斐波那契查找 我们将一一介绍着四种查找方式的思想以及程序的实现。 1.顺序查找 顺序查找 的查找过...

行走在代码边缘
2019/06/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

实战梯子游戏多年技巧心得回米必看

梯子游戏技巧交流回雪威【X3364FF】梯子游戏最起码是要学会找出它的规律,简单点我们要从低倍入手,这个有充足的考虑时间。 梯子游戏大概的走势可以分为长龙路、单跳路、对子路、房厅路。长龙...

风清杨啊
8分钟前
0
0
09VulKan——图像视图 采样器 组合图像取样器

整体思想: 使用一个纹理贴图到应用程序的流程: 注意: 在交换链和帧缓冲区中,图像不是直接访问,而是通过图像视图。这里借助图像视图来访问纹理图像 顶点着色器 #version 450#extensi...

黑白双键
9分钟前
0
0
等待收录

静态网站 https://dinghaobaojie.com/

张宏亮
21分钟前
18
0
UEditor富文本编辑

听很多人说百度推出的UEditor框架很实用,但是自己从来没有实践过,这一次有项目中用到,所以记录一下。(感觉一个东西会的人不难,没有做过掌握不到诀窍,就不太好弄) 主要可以分为三步: ...

axj_cfc
28分钟前
28
0
分布式事务

分布式事务处理机制共有四种: 两阶段提交 TCC事务(事务补偿) 本地消息表(异步确保), MQ事务消息。 两阶段提交: 与数据库XA事务一样,两阶段提交使用XA协议。 两阶段提交这种方案属于牺...

九分石人
29分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部