00:00
同学们,我们给大家介绍一下菲波纳契查找算法,也叫黄金分割法。那么首先呢,我们给大家介绍一下什么叫黄金分割点,黄金分割点呢,它是指的把如果我们把一条把一个线段呢,分割成两个部分,是其中的一部分与全长之比等于另外一部分与这一部分之比,取其前三位呢,它的近似值是0.618。据说这个数字很神奇,为什么呢?因为在很多这个做设计的人的眼里,黄金分割点是一个特别神奇的点,你比如说我们在画画的时候,如果你整体人的比例按照黄金分割比例来画呢?整体比这个画看上去就非常的和谐,非常漂亮,就好像一个人一样,我们这个人的上下身比例如果接近黄金分割,那么。整体来说哈,这个人即使长得个子不高,也看上去非常的漂亮,就是这样一个点,因此呢,有人就利用这个黄金分割点这一个神奇的特性呢,它设计了一个查找算法,称之为黄金分割查找算法。
01:13
那么为什么又叫斐波纳契呢?好,我们就来看看黄金分割点和菲波拉契有什么关系。斐波拉契这个数列,我相信同学们在前面学Java基础的时候呢,已然学过了,它的特点是它的第一,呃,就是第一个数为一,第二个数也为一。那么以后后面数呢?就是在前面这个数相加,比如说二怎么来的呢?是一加一等于二,那这个三怎么来的呢?是前面两个数一加二来的,五怎么来的呢?五是前面两个数相加,八呢?是前面两个数相加得到结果。大家有没有发现这个菲波纳奇数列,它相邻两个数的比例无限的接近于分黄金分割值。那这样子呢?这个在设计黄金分割法查找的时候,他就利用斐波纳气的这个特性来设计的这个查找算法,我们来看一下是不是这样子的啊,来,我们打开一个计算器。
02:12
同学们可以看一下,同学们可以看一下,比如说这个一和二相除,是不是这个是等于0.5啊,那么我们再看往后边走21,大家看这个21和34相除。21除以34,大家有没有发现它等于0.167,已经很接近黄金分割了,我们再来看后面这两个数,34和55相相除34。除以我们的55,同学们有有注意观察到,是不是它是0.618。是不是00.618已经很接近我们黄金分割这个点了。所以说。那么我们这个斐波纳气这个数列呢,它可以帮助我们去在查找的时候找到我们这个黄金分割点。
03:05
就是这个这个有序树立的黄金分割点,那么我们来看一下斐波纳气它的一个工作原理,它的工作原理呢,其实也特别简单,我们来看一下。非波拉器查找原理和前面两种,就是我们所说的二分一差值差值查找算法很相似,仅仅也是改变中间节点的位置,就是mid。这个求值呢,它发生变化,那么密的呢,不再是中间或者是差值得到的。而是位于黄金分割点的附近。它怎么求的呢?大家看密的。这个索引等于no,就是后面就是就是前面那个索引加上FK减一,再减一。这样来的,就它是这个公式推导的,下面呢,我们重点是要理解这个FK减一减再减一这个值是什么意思,因为前面这个no我就不讲了,No就是我们数组的最前面的索引,这个很好理解是不是,关键是FK减一。
04:10
他再减一,这个是什么含义,我们来理解一下,我这里总结了三句话,大家看我一共总结了三句话,首先。大家看到这个F,这个F代表的是什么呢?代表的是非波纳器数列,这个K代表的是非波纳气的第几个元素?就这这个意思,明白意思吧,那么我们看斐波拉奇数列是不是这样推导着FK等于FK减一加上FK减二是不是特性,因为呃,诶到当这个K大于二大于二以后呢,就是从第三个数开始,大家有发现它其实是两个数的相和,呃,两个数的和得到了。这这个字对不对,那所以说这个公式大家应该很好理解,就是前面斐波那契数列的特点。
05:03
那么如果我们把这个FK减掉一个一是不是等价于FK减一,再加一个FK减一,括起来再加一,因为你看这个这个式子大家有没有发现。这个公式实际上就就是上面这个公式,你看啊,我这减了一个一。你这减一再减一,再加一,是不是整体加起来再减一是不是还是相等的,相当于说这边减了一个一,这边减了一相等吧,那么这要相等,我们就推出幂的就等于no加FK减一,那么就让出这个K。K这个值就是我们的黄金分割点。的一个求值的算法。好,那么类似的每一个字段也可以用相应的方式进行分割,那这样就形成了一个递归,咱们就可以递归下去,或者是啊不停的找,不一定用递归啊,可能用非递归,也可以,就是不停的这样去切换它的前后值,得到黄金分割点。
06:02
但是这边有个问题,大家知道有什么问题吗?就说我们上面这种假设是有一个问题的,就是你这个顺序表,就是你要查找这个数列里面这个N呢,不一定刚好等于FK减一。是有这种可能性的,它不等于,它不等于的话呢,就需要将原来顺顺序表的长度N增加至FK减一,后面呢,我们从代码里面可以看到这个特性里面K的这个值呢,只要能使FK减一恰好大于或等于N就可以了,这样呢我们就可以拿到。拿到这个这个黄金分割点,那么这边有有一个算法就这样子的,就只要N大于。F,呃,这这是非波拉七啊,这非波拉7K减一,只要满满足这个条件,我这个K不停的加,直到N小于等于它就可以了,这样我就可以根据菲波拉契的特性找到我们这个黄金分割点。好,那么这个就是给同学们说的斐波纳气或者叫黄金分割法的原理,不太好理解,不太好理解,没有关系,一会儿呢,我们用代码给大家写,写一遍大家就很清晰的知道了,啊,很清晰知道了。再强调一点,就是我们这个非波纳器查找算法呢,它在某些情况下需要对原来的数组进行扩扩容。
07:25
什么意思呢,就是说要让他满足,可以去找到,要要把这个我们这个原始的这个查找数组呢,增加到FK点一,这样才能使用我们这个公式去套用,这点大家一定要清晰,不然的话,待会你听听我这个算法呢,会有点蒙圈,这点大家再再说一遍啊,就说。我们这个数组有可能刚不不一定刚好等于这个点,因为你刚好要找他嘛,找不到。没有这个值啊,没有这个值,那没有这个值怎么办呢?我们要先把它增长到这么多,再去用黄金,再去用这个公式,再去用这个公式,得到我们这个黄金,就黄金分割点也是得到我们这个密,明白这意思吧,好了,那关于。
08:12
这个斐波纳奇的查找算法先给大家介绍到这里,一会呢,我们用代码将其实现。
我来说两句