斐波拉契数列二分查找再回顾

 

在斐波拉契数列二分查找的分析中

https://blog.****.net/aaajj/article/details/44182737

 

比如ABCDE 5个节点，通过以下斐波拉契数列二分方式组织起来，

找A需要3次，即从5开始到A的路径

找B需要3次

找C需要2次

找D需要2次

找E需要2次

 

平均期望次数E=总次数 / 节点数 = (3+3+2+2+2) / 5 = 2.4

看到一篇期望分析

https://www.cnblogs.com/ranjiewen/p/6597692.html

似乎还不是很清楚

 

这里，设斐波拉契数列Tn 为 1 1 2 3 5 8 13 21 ……

设总次数为F

 

可以发现，随着层次的增加，存在着递推关系

F0 = 0

F1 = 0

F2 = F1 + t(2) + F0 + t(1)

 

Fn = Fn-1 + t(n) + Fn-2 + t(n-1)

 

F其实是所有子节点的深度和。

 

Fn = Fn-1 + Fn-2 + t(n+1)

 

F3 = F2 + t(4)

F4 = 2F2 + t(4) + t(5)

F5 = 3F2 + 2(t4) + t(5) + t(6)

F6 = 5F2 + 3t(4) + 2t(5) + t6 + t7

 

其中F2 = t(3)

所以

F5 = 3t3 + 2(t4) + t(5) + t(6)

F6 = 5t3 + 3t(4) + 2t(5) + t6 + t7

F7 = 8t3 + 5t(4) + 3t(5) + 2t(6) + t7 + t8

 

可以看到，系数 8 5 3 2 1 1 也是斐波拉契数列

越来越奇妙，是否可以求出通项公式呢？