美文网首页
Fibonacci查找

Fibonacci查找

作者: 邝健强 | 来源:发表于2017-09-10 18:51 被阅读0次

Fibonacci查找跟二分查找一样都是使用分治思想,其实都是每次查找的时候都是分两部分查找,二分查找使用的方式是分成等分的两部分,而Fibonacci查找使用的是Fibonacci数列划分。

为什么要按照Fibonacci数列划分呢?

下面先看看一个普通的二分查找:

未经优化的二分查找

可以证明二分查找的时间复杂度是o(logn),考虑前面系数的话,大约是o(1.5logn)

我们观察到进入右边区间的经过一次判断,而进入左边区间的经过两次判断,也就是进入左侧和右侧区间的比较次数不一样。

我们进行优化的思路是什么?

1.使进入左侧和右侧的比较次数一样

2.尽量进入右侧判断

第一种方式后面再说,顺着第二种方式,我们使用Fibonacci数列进行分割,这就是Fibonacci查找。利用斐波那契数来对传入的数组进行黄金分割,这样前半部分较多而后半部分较少。如此一来,我们人为造成的这种不平衡,反倒是助长了搜索成本的平衡。

Fibonacci查找

对于任何A[0,n],总是选取A[λn]为轴点,0<=λ<1

对于二分查找λ=0.5,对于Fibonacci查找λ=0.6108...

λ如何选值能达到最优,平均查找长度为a(λ)*log2

a(λ)*log2n = λ*[1+a(λ)*log2(λn)]*(1-λ)[2+a(λ)*log2(1-λ)n]

最后整理得出,a(λ)=1.4404...达到最优

相关文章

  • Fibonacci查找

    Fibonacci查找跟二分查找一样都是使用分治思想,其实都是每次查找的时候都是分两部分查找,二分查找使用的方式是...

  • <图解算法>读后笔记

    1. 二分查找 2. 选择排序 3. 快速排序 4. fibonacci 5. 广度优先算法 查找最短路径, 无向...

  • 分治法 1

    归并排序 二分查找 乘方问题 Fibonacci 数 朴素算法 其它解法(利用缓存) 在上面那个朴素算法中,当计算...

  • Fibonacci

    题目链接:Fibonacci In mathematics, the Fibonacci numbers are ...

  • 二分之求Fibonacci

    Fibonacci介绍 Fibonacci定义: 二分矩阵求Fibonacci 项目地址:github/Divid...

  • 有趣的斐波那契数列

    Math day 5:Fibonacci Sequence Fibonacci Sequence and Musi...

  • Fibonacci-不死神兔

    Fibonacci-不死神兔 class Fibonacci(object):def init(self, all...

  • C++ 模板元编程计算Fibonacci

    Leetcode 509 ( Fibonacci Number ) 是一道计算Fibonacci数列的简单题,解决...

  • fibonacci

  • Fibonacci

    001

网友评论

      本文标题:Fibonacci查找

      本文链接:https://www.haomeiwen.com/subject/wztbjxtx.html