斐波那契数的一个渐近下界 | Dijkstra算法+斐波那契堆的基础

摘要: 斐波那契堆时间复杂度推导的基础

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，关注算法的学生和工程师最近可能刷到了一篇关于 Dijkstra 算法的文章。我是在量子位上首先刷到的，后来看到很多号都转发了，热度还是挺高的：

这篇文章的主要工作是针对单源最短路问题的 Dijkstra 算法，优化了一下实现的数据结构，并把时间复杂度分析的理论做了一些完善。

论文的名称是《Universal Optimality of Dijkstra via Beyond-Worst-Case Heap》，要看懂这篇文章在干什么，首先得弄清楚两个问题，它们也都体现在标题里。

首先是什么叫“普遍最优”（Universal Optimality），按照我们在 Leetcode 上的理解，如果有两个算法 $A$ 和 $B$，对于输入规模为 $N$ 的数据，在最坏情况下的时间复杂度分别为 $O(f_{A}(N))$，$O(f_{B}(N))$，如果 $A$ 的渐进增长的阶更低，那 $A$ 算法就更好。比如我们知道归并排序在最坏情况是 $O(N\log N)$，插入排序在最坏情况是 $O(N^{2})$，按照这个标准，我们说归并排序比插入排序更好。

从工程师的角度还有一种很直观的理解就是对于规模为 $N$ 的任意一种输入 $A$ 算法都比 $B$ 算法的消耗要低，我们就说 $A$ 算法优于 $B$ 算法，当然这个条件更苛刻，无法通过大 $O$ 符号来判断。很多情况都无法通过这种方法比较算法优劣，比如虽然归并排序比插入排序在最坏情况的时间复杂度要好，但是有一些输入实例插入排序是比归并排序要好的，按照这个标准就没法说归并排序比插入排序更好。

那“普遍最优”（Universal Optimality）是什么意思，这是第一个问题。

第二个问题是 “Beyond-Worst-Case” 是什么意思，“Worst Case” 比较好理解就是我们在最坏情况分析中，输入规模为 $N$ 的输入中，使得算法性能最坏的那个输入实例，那加了一个 “Beyond”，含义有什么变化。

要弄懂这两个问题并不容易，这需要一些偏理论的前置知识，这方面我是完全没学过，不过还是可以给感兴趣的朋友推荐一个相关资料，即 Tim Roughgarden 的一门课，名称就叫 Beyond Worst-Case Analysis：

CS264: Beyond Worst-Case Analysis
链接：https://www.timroughgarden.org/w17/w17.html
作者：Tim Roughgarden

这门课程的动机是针对那些传统最坏情况算法分析无法明确区分不同解决方案，或者直观上推荐“错误”解决方案而不是“正确”解决方案的问题。本课程系统地研究了传统最坏情况分析的替代方法，这些方法仍然能够对算法的性能提供严格和稳健的保证。主题包括：实例最优性；平滑分析；参数化分析和条件数；数据模型（伪随机性、局部性、分散对手等）；平均情况分析；鲁棒分布分析；资源增强；以及半随机图模型。为了说明前面这些工具的动机，我们将从在线算法、在线学习、约束满足问题、图划分、调度、线性规划、哈希、机器学习和拍卖理论中选取案例。

Tim Roughgarden 的书和课篇幅还是很大的，以后有闲了或者有需要了可以跟大家分享一些精彩的案例。

本文就分享个比较简单，同时跟这篇论文也有关系的内容，即斐波那契数 $F_{n}$ 的一个渐近下界，即 $F_{k+2} \geq \phi^{k}$，其中 $\phi$ 为 $x^{2} = x + 1$ 的正根。这关系到 Dijkstra 算法在实现时的一个重要优化，即斐波那契堆的时间复杂度，而这篇火出圈的论文就是在斐波那契堆的基础上做的，本文我们推导一下这个下界，算是对这篇高热度论文的致敬。

---

Dijkstra 算法回顾

关于图上的最短路径问题，在本科的算法课以及leetcode上我们的经验是，如果两两之间的最短路径都要求出来，就用 Floyd 算法，如果是单源最短路，就看有没有负权，如果有负权就用 Bellman Ford 算法，如果没有负权，就用 Dijkstra 算法。

在时间复杂度上，我们通过简略的分析给出最坏情况的时间复杂度，Floyd 算法是 $O(n^{3})$，Bellman Ford 算法是 $O(nm)$，Dijkstra 算法如果用普通的二叉堆的话是 $O((m+n)\log m)$，其中 $n$ 为顶点数，$m$ 为边数，它的含义是算法流程中要做 $O(n)$ 次堆的 extract-min 操作，以及 $O(m)$ 次 insert 操作，而这两种操作的时间复杂度均为 $O(\log m)$。这些也都是本科教科书中的结论，此前我们也写过很多相关的算法讲解和题目。

由于在谈图算法时，讨论范围一般是简单图，因此边数 $m$ 最多为 $n^{2}$，那么 $\log m \leq \log n^{2} = 2\log n$，因此有的文章中也会见到把 Dijkstra 算法的时间复杂度写成 $O((m + n)\log n)$ 的，或者进一步假定 $m \geq n$ 从而直接写成 $O(m\log n)$，不如 $O((m + n)\log m)$ 严谨不过问题不大。

到这里就是我们大多数人对图的最短路径算法的了解程度了，就是大致有个印象各个算法的最坏时间复杂度是多少，适用的场景是什么，然后就是编程实现，解决问题了。

如果从算法分析的角度看的话，最短路径算法还是有很多故事的。一方面，毕竟 $O$ 符号内是有 $m$ 和 $n$ 两个变量，涉及到二元渐近性的问题，对于不同的图的形态，$m$ 和 $n$ 的关系不同，真要细究 $O(mn)$ 和 $O((m + n)\log m)$ 谁大谁小的话一时说不清楚。即使能说清楚最坏情况的时间复杂度是 Dijkstra 更好，但也很难确定是不是有某些特殊构造的图上 Dijkstra 并不是最优的，这篇论文谈的就是这个事。

另一方面，将二叉堆进行改进，可以把维护堆操作的 $O(\log m)$ 进行优化，这条线比较主要的成果是 1987 年提出了斐波那契堆，这个数据结构非常复杂，细节可以参考《算法导论》第三版第 19 章，可以在公众号内回复 【CLRS3】下载。

上面关于 Dijkstra 算法的算法分析的两条线具有一些理论价值，但是并不实用，因此一般情况我们不会专门去研究它，遇到最短路径的问题就根据情况套经验解决问题就非常有效了。

在斐波那契堆的分析过程中用到了摊销分析，这是一种很常见的思想，此前我们写过很多相关的文章：

• 可清空表的摊销分析
• 摊销分析：基于财务模型的记账法
• 摊销分析：基于统计力学的势函数法

摊销分析的最后会转化为斐波那契数相关的递推公式，并用到了它的一个下界，这也是将该数据结构称为斐波那契堆的原因。本文我们不讨论斐波那契堆的算法，因为比较复杂而且特别难实现，我们就来推导一下分析过程中用到的斐波那契数 $F_{n}$ 的一个渐近下界：

$$F_{n} \geq \phi^{n-2}$$

其中 $\phi$ 为 $x^{2} = x + 1$ 的正根。这是推导斐波那契堆的时间复杂度的关键一步。

斐波那契数列

斐波那契数列在工程领域以及数论、组合数学等其它数学分支中都有广泛应用，有些延伸很有理论深度，比如希尔伯特第十问题的解决就与斐波那契数列有关、比如求最大公约数的欧几里得算法的时间复杂度可以从斐波那契数列导出。这里也给大家一本讲述了斐波那契数列方方面面的参考书，可以在公众号内回复【Fibo】下载。

这里直接给出斐波那契数列的定义，是以下递归式：

$$\begin{align} &F_{n} = F_{n-1} + F_{n-2}, n\geq 2 \\ &F_{0} = 0, F_{1} = 1 \end{align}$$

每个数都是前两个数之和，序列的前几项为：

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \cdots$$

通项公式以及特征根

$F_{n}$ 的通项公式的求法可以参考组合数学中关于生成函数的内容，当然也有别的求法，这里我们直接给出结论。

定理(斐波那契数列的通项)

$$F_{n} = \frac{\phi^{n} - \hat{\phi}^{n}}{\sqrt{5}}$$

其中 $\phi$ 和 $\hat{\phi}$ 为方程 $x^{2} = x + 1$ 的两个根：

$$\phi = \frac{1 + \sqrt{5}}{2}, \quad \hat{\phi} = \frac{1 - \sqrt{5}}{2}$$

---

给出上述结论的情况下，很容易用数学归纳法证明。但没任何提示直接推导出或者猜出上面的公式还是不容易，历史上比内首先给出了上述公式的证明，因此也称为比内公式。

指数增长

由于 $|\hat{\phi}| < 1$，因此有 $\frac{|\hat{\phi}|}{\sqrt{5}} < \frac{1}{\sqrt{5}} < \frac{1}{2}$，因此有：

$$F_{n} = \left\lfloor\frac{\phi^{n}}{\sqrt{5}} + \frac{1}{2}\right\rfloor$$

也就是说，第 $n$ 个斐波那契数 $F_{n}$ 等于 $\frac{\phi^{n}}{\sqrt{5}}$ 舍入到的最近的整数。因此我们得到关键结论，斐波那契数是以指数形式增长的。

一个渐近下界

下面我们讨论本文的最终结论，也就是斐波那契数的一个下界，这个下界在比内公式的基础上很容易推导出来。

定理

对于所有整数 $k \geq 0$，第 $k+2$ 个斐波那契数 $F_{k+2}$ 满足 $F_{k+2} \geq \phi^{k}$。

证明（数学归纳法）

对 $k$ 进行归纳。

当 $k = 0$ 时，$F_{2} = 1 = \phi^{0}$；当 $k = 1$ 时，$F_{3} = 2 > \phi^{1}$。

假设对于 $i = 0,1,\cdots,k-1$ 时，$F_{i+2} \geq \phi^{i}$ 成立。

下面考虑 $i=k$ 的情况。将归纳假设代入到 $F_{k+1}, F_{k}$ 中，有：

$$\begin{align} F_{k+2} &= F_{k+1} + F_{k} \\ &\geq \phi^{k-1} + \phi^{k-2} \\ &= \phi^{k-2}(\phi + 1) \end{align}$$

由于 $\phi$ 为 $x^{2} = x + 1$ 的正根，因此 $\phi + 1 = \phi^{2}$，于是：

$$\begin{align} F_{k+2} &\geq \phi^{k-2}(\phi + 1) \\ &= \phi^{k-2}\phi^{2} \\ &= \phi^{k} \end{align}$$

$\Box$

总结

本文我们简要介绍了一下近期火出圈的一篇算法方面的论文，大致说了一下这篇论文在干什么，其中涉及到一些算法理论中比较深入的一些工具，以便提供除了常规的最坏情况时间复杂度之外的分析。

然后我们回顾了一下 Dijkstra 算法及其算法分析方面的经典内容，斐波那契堆是 Dijkstra 算法在实现时的一个重要优化，但它过于复杂且实现很困难，因此它并不实用，只有一些理论价值，那篇论文也是在斐波那契堆的基础上做的。

斐波那契堆之所以称为斐波那契堆，是因为在摊销分析时，经过巧妙的势函数的定义以及复杂的推导，最终会归结到斐波那契数，通过一个下界我们就可以给出关于斐波那契堆时间复杂度的分析结果，

之后我简要介绍了斐波那契数的递推和通项公式，并说明了这个数列是指数增长的，之后我们证明了算法分析时需要用到的斐波那契数的一个下界。

---