美的同一性和神秘的算法分析
2014-05-06
1977 年法国人 Philippe Flajolet 发表了一篇评估计算机展开算术表达式平均所需寄存器数量的论文 [1]。同年，普林斯顿的 Rebert Sedgewick 向 SIAM 投递了一篇讨论奇偶归并排序的文章 [2]，其中给出了数据在排序过程中平均交换次数的简洁表达式。Sedgewick 通过渐进分析获得的这个表达式后来被发现和 Flajolet 用于评估寄存器数量的式子具有同一性。Flajolet 后来给 Sedgewick 写信说：
> I believe that we have a formula in common!
这让我想到了杨振宁的杨-米尔斯规范场论与陈省身早前所做的纤维丛中的联络论之间美妙的同一性。同样的巧合发生在了理论计算机领域，而这一次则表征着渐进分析法的胜利。这一经典的数学分析工具早在18世纪就由欧拉和迈克劳伦初步建立，直到20世纪50年代末趋于完善，目前依然是算法分析最有效的系统方法之一。即便现今任何一台小型计算机的处理器都能轻松胜任大数值计算（例如 2^10000 的阶乘），但渐进分析所提供的极高精度的表达式依然具有极高的效率和简洁性。经典数学分析所提供的信息量和对问题的深入洞见是无法被强力计算所替代的。
后来 Sedgewick 成为了算法分析领域的大牛，沿着他的导师高德纳的足迹越走越远。而 Flajolet 在法兰西的另一边走火入魔般地使用分析方法研究组合数学。和所有狗血的基友故事一样，他俩的渊源远没有就在一则公式上打住，1980 年两人决定合写一本有关算法分析的教材，1986 年 Sedgewick 开始在普林斯顿计算机学院开设算法分析课程，十余年间积累了大量的课程讲义和技术报告材料，1992 年，Flajolet 在组合数学上的研究取得系统性成果，两人决定将写作计划由原来的一本拆分为两本不同侧重的专著。1995 年两人合著的第一本书《算法分析导论》（以下简称 AoA）出版，以生成函数（Generating Functions）为核心，系统地介绍了自伯努利、欧拉以来被广泛使用的算法分析工具，其中包含了一些高德纳在《计算机编程艺术》前三卷中所涵盖的主题，主要是递归、生成函数和渐进分析。这些主题完整地定义了算法分析的科学基础，也从数学上证明了人们可以准确地估计和比较算法的运行效率。AoA 还给出了大量的分析应用，包括二叉树、森林、排序、字符串、分词和映射的边界统计分析。除此之外，AoA 最精彩的部分莫过于对分析组合学浅尝辄止的介绍，这部分内容为传统的算法分析和组合学架起了桥梁，使得计算机科学家能够将组合数学的简洁性移植到算法分析过程中去。Flajolet 和 Sedgewick 将这部分内容在 2009 年出版的《分析组合学》中进行了完整、系统化地阐释，史无前例地将数学分析工具大规模地应用到符号化的组合数学上，并获得了一些异常简洁而令人惊叹的结论，而这些结论不仅相容于传统的算法分析，而且更进一步地揭示了一些用传统方法很难解释或证明的现象。Flajolet 和 Sedgewick 开创性地使用数学分析方法获得了巨大的成功，又一次带来这个世界的一切都存在着奇妙而神秘的联系的既视感。而人类伟大的数学家们用至上的智商不停地挑战造物主的权威，在学科的边界处绞尽脑汁顶破一个又一个的牛角尖，所发现的奇妙现象看起来依然只像是冰山一角而已。
第一次阅读 AoA 的时候确实被其中铺天盖地的数学公式所吓到，同时也看到有人吐槽 Sedgewick 这本书写得太过「理论」和「不实用」。最主流的观点就是将这本书和麻省理工 CLRS 的《算法导论》相比较，从而得出一些对前者的负面评价。在这学期修完以《分析导论》为蓝本的 Analysis of Computing and Systems 后，我能够更加具体地为这本写得十分漂亮而引人入胜的书正名。
学计算机的人都知道 CLRS 的《算法导论》，这本书早已成为 CSer 们面试攻坚的圣经，提到算法和数据结构，没有人会跳过这本书。同样也没有人能够否认《算法导论》可能是算法设计领域最有影响力的一本教材。然而作为一个捣腾计算机科学的家伙，你得明白算法分析和算法设计是截然不同的两个领域，即便他们都涉及核心主题「算法」，但研究方法和思路都相差甚远。简单点说，CLRS 试图解决的问题是，为每一个类别的代表性算法提供设计细节和可用性分析，同时涉及一些高级数据结构和少量渐进分析符号；而 AoA 则提供泛型的数学分析工具，并不特别针对某一类别的问题。你很可能在本科的时候修过离散数学、算法设计、形式语言与自动机、数据结构，但缺乏系统知识结构和背景让大部分人很难理清其中的联系。在认真阅读 AoA 之前，我可能并没有好好思考过我们为什么需要研究离散数学。而意外的是，正是这本充溢着连篇累牍的数学公式和推算的「理论」书，串联起了计算机科学的主轴。
我们的世界本质上是连续的，从 0 到两端的无穷，数值没有最小刻度。然而人类认识到这个事实花了上千年，直到无理数和极限出现。高等数学主要针对连续和极限进行推演，发展出一套精巧高效的微积分系统，20世纪的数学继续在几何学上发展微分思想，获得开创性的成功。20世纪中叶计算机的出现使理论科学家开始调转注意力到离散世界，事实上这部分数学在19世纪以前也被研究的相当透彻（欧拉的数论，伯努利的猜度术），但以高德纳为首的计算机科学家第一次将这些材料针对计算机问题进行归纳。于是人们开始重新审视那些老旧的离散分析工具——递归、生成函数、渐进分析以及欧拉-迈克劳伦公式，本质上都是试图将离散问题转换为连续问题来研究，因为我们面对后者拥有丰富的经验和强大的武器库。
掌握 AoA 中讨论的工具，使得我们可以快速地对一个问题进行数学的估计，得出问题规模的增长率、变化趋势和极限。这些结论只能通过数学分析获取，而不能单纯依赖经验和硬性计算性能。而一旦获得这些结论，我们对问题本身就有了具象、俯瞰式的把握，解决起来也就更加游刃有余了。这里举一个最简单的例子，假设我们需要用 BitString 存储有 N 个节点的二叉树，这样的二叉树可以呈现出任意合法的形态，那么我们至少需要定义多长的 BitString 来表达这些二叉树而不会溢出？
最简单的考虑是去计算不同 $N$ 节点二叉树的数目，这里设为 $M$，那么用 BitString 来存储就至少需要 $log(M)$ 长度。好吧，那么，如何得到这个 $M$ 的值？比较传统的方法是使用递归，考虑二叉树在跟节点处的情况，假设左子树有 $K$ 节点，根节点一个，所以右子树 $(N-K-1)$ 节点。 设 $T_i$ 表示 $i$ 节点二叉树的数目，那么我们可以得到递归式如下
$$SS{T}{K} = sum_{K=0}^{N} Ss{T}{K} Ss{T}{NSUBx{-}subx{K}subx{-}subx{1}} + Ss{delta}{Nsubx{0}} $$
用任意方法解这个递归都可以得到 $T_N = frac{1}{N+1} binom{2N}{N}$ ，所以我们只需要对这个数求对数就可以得到所需的 BitString 最小长度了。这个结果是准确的，但依然有一个小瑕疵，对于比较大的 $N$ 值，计算组合数不是一件容易的事，如何能够让程序员快速地知道对于任意大的 $N$ 值，这个 $T_N$ 大概是多少呢？（通常情况下我们不需要特别精确的结果）这个时候利用渐进分析我们可以得到 $T_N$ 其实就是 $frac{4^N}{sqrt{pi N^3}}$，而再求一下对数，则大概是 $2N-1.5 log (N)$，对于程序员来说可能后面减去的 $1.5 log(N)$ 也不重要，特别是对于足够大的 $N$。至此我们确信，对于 $N$ 节点的 二叉树，我们使用 $2N$ 长度的 BitString 是绝对安全的，这是一个十分优雅、绝对正确的结果。它证明算法分析不仅是有效的，更是优秀的。
***
[1] Flajolet, Philippe, Jean-Claude Raoult, and Jean Vuillemin. "On the average number of registers required for evaluating arithmetic expressions." Foundations of Computer Science, 1977., 18th Annual Symposium on. IEEE, 1977.
[2] Sedgewick, Robert. "Data movement in odd-even merging." SIAM Journal on Computing 7.3 (1978): 239-272.
查字典图书网
