书 · 1990 · 托马斯·科尔曼、查尔斯·莱瑟森、罗纳德·李维斯特(1990 年初版为这三位作者,克利福德·斯坦自 2001 年第 2 版起加入)

《算法导论》

计算机与 AI书单第 7 名

一句话结论

这本书把“算法”变成一门可以证明的学问:用增长阶比较效率,用分治、动态规划、贪心、图和数据结构这几套通用套路解题,再用 NP 完全理论告诉你什么时候该停手。

值不值得读完整本？

不值得从头到尾读完,值得当主干教材精读一半、当参考书留着查。它是一本厚重的教科书和工具书,读的人要有数学耐心。读完后你得到的是一套分析和证明算法的语言,不是一份能直接抄用的代码。

先读第 1–4 章(算法在计算中的作用、入门、函数增长、分治与递归式)。这几章把全书的分析语言讲清楚,后面都用得上。
接着精读动态规划、贪心、摊还分析,再读图算法(基本图算法、最小生成树、最短路、最大流),最后读 NP 完全性。这几块是全书的核心。
排序、堆、哈希表、二叉搜索树和红黑树是经典数据结构,值得读,但红黑树的细节第一遍可以只看性质、不抠旋转的全部分情况。
最后的专题部分(数论、字符串匹配、计算几何、线性规划等)按需查阅即可。
要配合习题。书里每章后面的思考题和练习才是真正的训练,只看不做很快就忘。
章节号以第 3 版为准,第 4 版有重新编号,查阅时留意。

核心观点

1. 用增长阶而不是具体秒数来衡量算法

比较算法时,看运行时间随输入规模 n 增长的速度(用 Θ、O、Ω 记号表示),而不是在某台机器上跑出的具体时间。

为什么：具体秒数取决于机器、语言和代码细节,换个环境就变了,没法拿来做一般性的比较。作者把算法抽象成一个关于 n 的函数,只保留增长最快的那一项,这样结论不依赖具体机器。输入够大时,增长阶更低的算法一定会赢过增长阶更高的,常数因子再大也追不上。所以选对算法比把代码优化得更快更重要。

2. 分治:拆成同类小问题,用递归式算账

把问题拆成规模更小的同类子问题,分别解决后再合并。耗时用递归式描述,再用递归树或主定理求解。

为什么：递归算法的耗时本身依赖子问题的耗时,所以天然写成递归式。递归树把它摊开:每一层要做多少拆分和合并工作,一共有几层。归并排序每层总代价是线性的,每次对半拆分,一共约 lg n 层,所以总代价是 n lg n。主定理把这类“每层工作量如何随层数变化”的几种典型情形做成现成公式,不用每次重新推。

3. 动态规划与贪心:利用最优子结构避免暴力枚举

若问题的最优解由子问题的最优解组成,且子问题会反复出现,就把子问题的答案存起来(动态规划)。若每一步都能证明局部最优选择不会毁掉全局最优,就直接贪心。

为什么：暴力枚举所有方案往往是指数级的。动态规划成立的两个条件是最优子结构和重叠子问题:最优解里的每一块本身也是最优的,而且同样的子问题会被重复遇到,所以把答案存进表里,每个子问题只算一次,指数变成多项式。贪心更省事,但它需要额外证明“贪心选择性质”,也就是第一步这样选,后面仍能走到最优。作者特别强调这个证明不能省,因为看上去合理的贪心经常是错的。

4. 数据结构的选择决定算法的上限

算法需要的操作(取最小、查找、插入)有多快,取决于背后用什么数据结构,选对结构本身就是算法设计的一部分。

为什么：每个算法由若干基本操作组成,总代价是这些操作代价的叠加。二叉堆让“取最大并维护”只要对数时间;哈希表在合理的散列假设下查找期望是常数时间;普通二叉搜索树遇到有序输入会退化成链,所以要用红黑树这类平衡结构,靠性质保证高度是对数级。对于代价不均匀的操作序列,作者还提出摊还分析:偶尔很贵的操作被前面很多便宜的操作“预付”了,按整个序列平均,单次仍是常数。

5. 图是通用的建模语言,常见问题有统一的解法

很多现实问题都可以画成点和边的图,最小生成树、最短路、最大流都有成熟的算法。

为什么：这些问题大多具有最优子结构:最短路径的任何一段子路径也是最短的,所以可以用“松弛”不断改进估计值,直到不能再改进。有了这个性质,Dijkstra 和 Bellman-Ford 这些看上去不同的算法其实是同一套松弥思路的不同变体。最大流则靠“最大流等于最小割”的定理,把一个优化问题变成可以验证的条件。把问题归结成图,就能直接调用已有的算法和证明。

6. NP 完全性:有些问题大概没有高效精确解,要学会识别并绕开

一大类问题(NP 完全问题)要么都有多项式时间的算法,要么都没有,而大家普遍相信是后者。证明一个问题属于此类,就是在告诉你别再找快速精确算法了。

为什么：通过多项式时间归约,可以把一个已知很难的问题转化成新问题:如果新问题能高效解决,已知难题也能。所以一个问题一旦被证明 NP 完全,就等于它和一大批研究了几十年都没攻克的问题绑在一起。这对实践的意义是:不要再花时间找快速精确算法,转而做近似算法、启发式,或只解特殊情形。书里也如实说明 P 是否等于 NP 仍是未解难题。

反对意见

最坏情况分析太悲观,解释不了很多算法在实践中的好表现(Spielman 与 Teng;Roughgarden 主编的论文集)

Spielman 和 Teng 在 2004 年《Smoothed Analysis of Algorithms》里指出,单纯形法在最坏情况下是指数级的,但实践中表现很好,用“平滑分析”(在最坏输入上加一点随机扰动再取平均)能解释这一点。Roughgarden 主编的《Beyond the Worst-Case Analysis of Algorithms》(2021)汇集了一批超越最坏情况的分析方法。这个批评针对的是,以最坏情况为中心的分析框架会误导人。

渐近分析忽略了缓存等硬件细节,操作次数不等于真实速度(LaMarca 与 Ladner)

LaMarca 和 Ladner 在《The Influence of Caches on the Performance of Sorting》(Journal of Algorithms,1999)中通过实验和分析表明,缓存未命中会显著影响排序的真实耗时。他们重新组织了堆排序、归并排序和快速排序,让它们更适合缓存,总耗时因此下降。这提醒读者,书里的计算模型只数基本操作,忽略了内存层次。

用真实可运行的代码教算法,比伪代码加数学证明更贴近工程(Sedgewick 与 Wayne)

Sedgewick 和 Wayne 的《Algorithms》第 4 版(2011)用 Java 实现全部算法,而不是伪代码,并强调实现、测试和性能实测。它代表的是一条偏工程的路线,与本书偏数学证明的写法形成对照。这里是教学路线的差异,并非他们直接批评本书。

按真实问题和设计技法组织,更利于学会建模(Kleinberg 与 Tardos 的路线)

Kleinberg 和 Tardos 的《Algorithm Design》(2005)从有现实动机的问题出发,按设计技法组织内容,帮助读者学会如何把问题转化成算法。这也是教学结构上的另一种选择,不是对本书的直接批评。