algorithm - 为什么斐波那契数列在计算机科学中很重要？

Question

Fibonacci numbers已经成为计算机科学专业学生对递归的流行介绍，并且有一个强有力的论据认为它们在自然界中存在。由于这些原因，我们中的许多人都熟悉它们。

它们也存在于其他地方的计算机科学中；在基于序列的惊人高效的数据结构和算法中。

我想到了两个主要示例:

• Fibonacci heaps哪个有更好的摊销运行时间比二项式堆。
• Fibonacci search哪个股O(log N) 二进制运行时间在有序数组上搜索。

这些数字是否有一些特殊的属性使它们比其他数字序列更具优势？是空间质量吗？他们还有哪些其他可能的应用？

这对我来说似乎很奇怪，因为在其他递归问题中出现了许多自然数序列，但我从未见过 Catalan堆。

Answer 1

Fibonacci 数具有各种非常好的数学特性，使它们在计算机科学中表现出色。这里有一些:

1. 它们以指数方式快速增长。斐波那契数列在其中出现的一个有趣的数据结构是 AVL 树，这是一种自平衡二叉树形式。这棵树背后的直觉是每个节点都维护一个平衡因子，使得左右子树的高度最多相差一个。因此，您可以认为获得高度为 h 的 AVL 树所需的最小节点数由看起来像 N(h + 2) ~= N(h) + N(h + 1) 的递归定义，看起来很像斐波那契数列。如果你算出数学，你可以证明获得高度为 h 的 AVL 树所需的节点数是 F(h + 2) - 1。因为斐波那契数列呈指数增长，这意味着 AVL 的高度树的节点数至多为对数，为您提供我们所了解和喜爱的平衡二叉树的 O(lg n) 查找时间。事实上，如果您可以使用 Fibonacci 数来限制某个结构的大小，那么您可能会在某些操作上获得 O(lg n) 运行时间。这是 Fibonacci 堆被称为 Fibonacci 堆的真正原因 - 证明在 dequeue min 之后堆的数量涉及使用斐波那契数来限制您在特定深度中可以拥有的节点数量。
2. 任何数字都可以写成唯一斐波那契数的总和。斐波那契数的这一属性对于斐波那契搜索的工作至关重要；如果您不能将唯一的斐波那契数加在一起成为任何可能的数，则此搜索将不起作用。将此与许多其他系列进行对比，例如 3ⁿ 或加泰罗尼亚数字。我认为，这也是许多算法喜欢 2 的幂的部分原因。
3. 斐波那契数列可以高效计算。可以非常高效地生成数列这一事实(您可以在 O(n) 中获得前 n 项或在 O(lg n) 中获得任意项)，那么很多使用它们的算法都不实用。生成加泰罗尼亚数字在计算上非常棘手，IIRC。最重要的是，斐波那契数有一个很好的属性，给定任意两个连续的斐波那契数，比如说 F(k) 和 F(k + 1)，我们可以通过将这两个值相加轻松计算出下一个或上一个斐波那契数(F(k) + F(k + 1) = F(k + 2)) 或减去它们 (F(k + 1) - F(k) = F(k - 1))。这个属性在几个算法中被利用，连同属性 (2)，将数字分解为斐波那契数的总和。例如，斐波那契搜索使用它来定位内存中的值，而类似的算法可用于快速高效地计算对数。
4. 它们在教学上很有用。教授递归很棘手，而斐波那契数列是介绍递归的好方法。在介绍该系列时，您可以谈论直接递归、记忆化或动态编程。此外，惊人的closed-form for the Fibonacci numbers通常作为归纳练习或无限级数分析中的练习进行教授，以及相关的 matrix equation for Fibonacci numbers通常在线性代数中作为特征向量和特征值背后的动机引入。我认为这是他们在入门类(class)中如此引人注目的原因之一。

我敢肯定还有更多原因，但我敢肯定其中一些原因是主要因素。希望这对您有所帮助!