当前位置:   article > 正文

python贝塞尔插值公式_斐波那契查找原理——附python和C++实现

贝塞尔公式什么时候用n-2

5cabb06a288cd4fd960bc894e7d187f8.png

在正式介绍斐波那契查找之前,首先要知道什么是斐波那契数列:

机器学习入坑者:面试被问到斐波那契数列怎么办?——附python和C++实现​zhuanlan.zhihu.com
60e5121c0909402ae8f2d419717181e1.png

前面的文章分析了顺序查找、二分查找和插值查找,其中顺序查找的思想最简单,只需要将目标值和数据中每一个值进行比较即可;二分查找每次将区间长度缩减一半;插值查找按照目标值和边界值的关系确定区间分割方式。

斐波那契查找同样是查找算法家族中的一员,它要求数据是有序的(升序或降序)。斐波那契查找采用和二分查找/插值查找相似的区间分割策略,都是通过不断的分割区间缩小搜索的范围

要点:斐波那契数和数据有什么关系?

4e16512ffad977fc58b18225804f3c88.png

斐波那契数列中(上表来自维基百科),从第三项开始,每一项都等于前两项之和

ba8940329df511cb4f3b17095324e6bd.png

上述性质可以用于数据区间分割,将一个长度为F(n)数组看做前后两半,前面一半长度是F(n-1),后面一半的长度是F(n-1)。正是这个想法将斐波那契数列和数组联系到一起,也是后面分析的基础:

947fcdbc7d05f08a3a7d9c1757cf8485.png

其中n的取值是任意长度的,即对任意长度的数组都能找到对应的斐波那契数,下面将具体介绍斐波那契查找的步骤。

1、原理分析

斐波那契查找的整个过程可以分为:

  • 构建斐波那契数列;
  • 计算数组长度对应的斐波那契数列元素个数;
  • 对数组进行填充;
  • 循环进行区间分割,查找中间值;
  • 判断中间值和目标值的关系,确定更新策略;

1.1 构建斐波那契数列

这一步骤见前面的文章,构建斐波那契数列如下:

[

1.2 计算数组长度对应的斐波那契数列元素个数

假设手中的数据如下:

[

可知上述数据共25个元素,不对应1.1节中的斐波那契数列中任何F(n),这种情况是很常见的。此时,策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前数组长度为25,斐波那契数列中大于25的最近元素为34。

1.3 对数组进行填充

确定了斐波那契数值后,就要进行数值填充,即将数组从25个元素填充到34个。填充时,将第26到34个元素均采用第25个元素值进行填充,即最大值填充。

1.4 循环进行区间分割,查找中间值

这一个步骤与前面介绍的二分查找和插值查找相似,都是不断的缩小搜索区间,进而确定目标值的位置。区间分割公式如“要点”所述,每次分割中间位置的计算如下:

d7213d55495469240bbbb44edf7f8428.png

此时数组被分割为左右两个区间,左边区间含有F(n-1)个元素,-1是因为下标从0开始(比如F(1)表示两个元素)。

1.5 判断中间值和目标值的关系,确定更新策略

中间值和目标值有三种大小关系,分别对应三种处理方式:

  • 相等,则查找成功,返回中间位置即可;
  • 中间值小于目标值,则说明目标值位于中间值到右边界之间(即右区间),右区间含有F(n-2)个元素,所以n应该更新为n=n-2;
  • 中间值大于目标值,这说明目标值位于左边界和中间值之间(即左区间),左区间含有F(n-1)个元素,所以n应更新为n=n-1;

2、python实现

(1)实现过程中,如果数据是列表,则必须首先进行深度复制,因为填充过程会更改原始数据;

(2)因为预先不知道需要多少个斐波那契数值,所以使用max_size先构造一个较多斐波那契数值;

import 

3、C++实现

int 

4、总结

折半查找需要进行除法,插值查找需要进行更复杂的乘法和除法,而斐波那契查找只需要使用加法和减法,在数据量较大时优势更明显。

参考:

【1】https://github.com/el1ven/Fibonacci_Search

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号