斐波那契数列 http://en.wikipedia.org/wiki/Fibonacci_number已经成为计算机科学专业学生对递归的流行介绍，并且有一个强有力的论据表明它们在自然界中持续存在。由于这些原因，我们许多人都熟悉它们。
它们也存在于计算机科学的其他地方；基于序列的令人惊讶的高效数据结构和算法。
我想到了两个主要例子：
-
斐波那契堆 http://en.wikipedia.org/wiki/Fibonacci_heap哪些有更好的
摊销运行时间比二项式
堆。
-
斐波那契搜索 http://en.wikipedia.org/wiki/Fibonacci_search_technique哪些共享
O(log N) 二进制运行时间
在有序数组上搜索。
这些数字是否有一些特殊属性使它们比其他数字序列更具优势？这是空间质量吗？它们还有哪些其他可能的应用？
这对我来说似乎很奇怪，因为在其他递归问题中出现了许多自然数序列，但我从未见过Catalan http://en.wikipedia.org/wiki/Catalan_number heap.
斐波那契数具有各种非常好的数学特性，这使得它们在计算机科学中非常出色。这里有一些：
-
它们呈指数级快速增长。斐波那契数列出现的一个有趣的数据结构是 AVL 树，它是一种自平衡二叉树形式。这棵树背后的直觉是每个节点维护一个平衡因子，以便左右子树的高度最多相差一。因此，您可以认为获得高度为 h 的 AVL 树所需的最小节点数是由看起来像 N(h + 2) ~= N(h) + N(h + 1) 的递归定义的，这看起来很像斐波那契数列。如果你计算一下数学，你可以证明获得高度为 h 的 AVL 树所需的节点数为 F(h + 2) - 1。由于斐波那契数列呈指数增长，这意味着 AVL 的高度树的节点数量最多是对数，因此我们知道并喜欢平衡二叉树，因此查找时间为 O(lg n)。事实上，如果您可以使用斐波那契数来限制某些结构的大小，那么您可能会在某些操作上获得 O(lg n) 运行时间。这就是斐波那契堆被称为斐波那契堆的真正原因 - 证明出队最小值后的堆数量涉及使用斐波那契数限制在一定深度内可以拥有的节点数量。
-
Any number can be written as the sum of unique Fibonacci numbers. This property of the Fibonacci numbers is critical to getting Fibonacci search working at all; if you couldn't add together unique Fibonacci numbers into any possible number, this search wouldn't work. Contrast this with a lot of other series, like 3n or the Catalan numbers. This is also partially why a lot of algorithms like powers of two, I think.
-
斐波那契数列是可以有效计算的。事实上，级数可以非常高效地生成（您可以在 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) 结合使用，将数字分解为斐波那契数之和。例如，斐波那契搜索使用它来定位内存中的值，而类似的算法可用于快速有效地计算对数。
-
它们在教学上很有用。教学递归是很棘手的，斐波那契数列是介绍它的好方法。在介绍本系列时，您可以谈论直接递归、记忆或动态编程。此外，令人惊叹的斐波那契数列的封闭形式 http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression通常作为归纳法或无穷级数分析的练习来教授，以及相关的斐波那契数列的矩阵方程 http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form通常在线性代数中作为特征向量和特征值背后的动机引入。我认为这是他们在入门课程中如此引人注目的原因之一。
我确信还有更多原因，但我确信其中一些原因是主要因素。希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
