为什么斐波那契数字在计算机科学中具有重要意义？

Question

Fibonacci数字已经成为计算机科学学生递归的一个流行的介绍,并且有一个强烈的论据,即它们在自然界中存在.出于这些原因,我们很多人都熟悉它们.

它们也存在于其他地方的计算机科学中; 在基于序列的令人惊讶的有效数据结构和算法中.

我想到了两个主要的例子:

• 斐波那契堆比二项式堆具有更好的摊销运行时间.
• Fibonacci搜索在有序数组上与二进制搜索共享O(log N)运行时间.

这些数字是否有某些特殊属性可以使它们优于其他数字序列？这是空间质量吗？他们还有哪些其他可能的应用程序？

这对我来说似乎很奇怪,因为在其他递归问题中有许多自然数字序列,但我从未见过加泰罗尼亚语堆.

Answer 1

Fibonacci数字具有各种非常好的数学特性,使它们在计算机科学中表现出色.这里有几个:

1. 它们以指数级增长. Fibonacci系列出现的一个有趣的数据结构是AVL树,一种自平衡二叉树.这棵树背后的直觉是每个节点都保持一个平衡因子,这样左右子树的高度最多相差一个.因此,你可以想到获得高度为h的AVL树所需的最小节点数由一个看起来像N(h + 2)〜= N(h)+ N(h + 1)的重现来定义,看起来很像Fibonacci系列.如果你计算出数学,你可以证明获得高度为h的AVL树所需的节点数是F(h + 2) - 1.因为Fibonacci系列呈指数级增长,这意味着AVL的高度树在节点数量上最多是对数,给你O(lg n)查询时间,我们知道并喜欢平衡二叉树.实际上,如果您可以使用Fibonacci数绑定某个结构的大小,则可能会在某些操作上获得O(lg n)运行时.这就是Fibonacci堆称为Fibonacci堆的真正原因 - 证明了出队时间之后堆的数量涉及使用Fibonacci数限制一定深度的节点数.
2. 任何数字都可以写成唯一斐波纳契数的总和. Fibonacci数的这个属性对于让Fibonacci搜索工作至关重要; 如果你不能将唯一的Fibonacci数字加到任何可能的数字中,那么这个搜索将不起作用.与许多其他系列形成对比,例如3 ⁿ或加泰罗尼亚语数字.这也是部分原因,我认为很多算法都像2的幂.
3. Fibonacci数是有效可计算的. 系列可以非常高效地生成(你可以在O(n)中获得前n个项或在O(lg n)中获得任意项),然后很多使用它们的算法都不实用.生成加泰罗尼亚语的数字在计算上非常棘手,IIRC.除此之外,Fibonacci数具有一个很好的属性,给定任意两个连续的Fibonacci数,假设F(k)和F(k + 1),我们可以通过添加两个值来轻松计算下一个或前一个Fibonacci数. (F(k)+ F(k + 1)= F(k + 2))或减去它们(F(k + 1)-F(k)= F(k-1)).该属性在几个算法中被利用,与property(2)一起使用,将数字分成Fibonacci数的总和.例如,Fibonacci搜索使用它来定位内存中的值,而类似的算法可用于快速有效地计算对数.
4. 他们在教学上很有用. 教学递归很棘手,Fibonacci系列是介绍它的好方法.在介绍该系列时,您可以谈论直接递归,关于memoization或动态编程.此外,Fibonacci数的惊人封闭形式通常被教导为归纳或无限级数分析中的运动,而Fibonacci数的相关矩阵方程通常在线性代数中作为特征向量和特征值背后的动机引入.我认为这是他们在入门课程中如此高调的原因之一.

我确信有更多的理由而不仅仅是这个,但我确信其中一些原因是主要因素.希望这可以帮助!