书 · 1968 · 唐纳德·E. 高德纳（Donald E. Knuth）

《计算机程序设计艺术》

计算机与 AI书单第 25 名

一句话结论

把程序写出来只是开始：还要解释它为什么正确、花费多少资源，以及什么条件下值得采用。

值不值得读完整本？

值得长期研读，但对大多数读者，不值得把整套逐页读完作为目标。它是算法分析的深厚基础；按主题读透、配合练习，比追求通读更有收获。1968 年是第一卷首版年份，本导读覆盖这一持续出版的多卷系列的主要内容。

先读第一卷第1章“基本概念”，重点掌握算法的定义、数学归纳法和算法分析；数学工具遇到障碍时再回查，不必先把全部公式背熟。
接着读第一卷第2章“信息结构”，再读第三卷第5章“排序”、第6章“查找”，把数据结构、操作成本和使用条件连起来理解。
第二卷第3章“随机数”、第4章“算术”至少各选一条主线读透：随机数生成与检验，以及数的表示、舍入与多精度计算。这两章也是本书的核心，不能因为偏数学就全部略过。
第四卷的4A、4B部分围绕第7章“组合搜索”展开，可依次接触组合对象生成、布尔表示、回溯、舞蹈链和可满足性问题，理解怎样组织巨大的候选空间。
初读可跳过逐条机器指令推演、暂时用不到的专门算法和高难研究题；但要理解MIX这类机器模型为何能把隐含成本显露出来。
必须配合练习：每个主题至少亲手追踪一个算法、解释一次正确性、估算一次成本，再用熟悉的语言实现。书中的习题承载了不少正文之外的内容。

核心观点

1. 算法必须说清步骤、适用范围与停止条件

算法不能依赖执行者猜测意思；每一步都要明确、可执行，并对规定范围内的输入在有限步骤后结束。说明它能得到所需结果，还需要正确性论证。

为什么：计算机只执行规定的操作，不会替我们补上遗漏的条件。输入范围不清，就可能遇到除以零或没有定义的操作。正确性论证要找出步骤之间保持的关系，说明中间变化没有改变要求解决的问题。终止性则需要另作说明，例如证明某个非负整数不断减小；仅仅发现循环中的关系始终成立，还不能保证程序会停。

2. 评价算法，要把资源消耗变成可分析的数量

高德纳关心特定算法究竟执行多少次操作、占用多少存储，而不只问它能不能运行。比较优劣必须说明输入条件、成本模型和评价目标。

为什么：输入规模增加时，循环和分支的执行次数会以不同方式增长，所以小样本上的速度不能直接代表大规模表现。求平均成本需要规定输入怎样出现，否则“平均”没有明确含义。渐近分析帮助我们看清增长趋势，精确计数和机器实现则补充常数与具体操作的代价。把这些层次结合起来，才能解释一种方法为什么在某些条件下更合适，而不是宣布它处处最好。

3. 数据怎样表示，会改变问题怎样被解决

数据结构不是算法外面的包装：数组、链表、树和散列表提供的操作不同，会直接改变算法的成本与适用场景。

为什么：表示方式决定程序可以直接取得什么信息，以及取得这些信息需要经过多少步骤。连续存储便于按位置访问，但插入时可能需要移动元素；链接表示便于局部修改，却可能要沿链接寻找位置。树通过组织比较关系缩小查找范围，散列则借助地址计算寻找记录，同时引入冲突处理。选择结构因此要从实际操作组合出发，把查找、更新和存储开销一起计算。

4. 随机数的质量必须靠理论和检验判断

一串数字看起来杂乱，或生成过程很复杂，都不能证明它适合随机模拟。伪随机数生成器需要分析周期、相关性和统计表现。

为什么：有限状态的确定性生成器一旦再次进入同一个状态，后续就会重复。周期长也不能单独保证质量，因为连续输出之间仍可能存在影响应用的规律。理论分析能揭示结构性缺陷，统计检验则从不同角度寻找偏离预期的表现。两者相互补充，而通过有限检验也不能证明序列具备一切随机性质。

5. 机器上的算术，需要同时考虑表示、误差与成本

数学公式不能不加分析地变成可靠的机器计算。数怎样存储、运算怎样舍入，以及整数有多少位，都会影响结果或成本。

为什么：浮点系统只能表示有限的一部分数，运算结果经常需要舍入。等价的数学表达式若改变运算顺序，中间误差的传播也可能改变，因此代数等价不保证机器结果相同。需要精确处理大整数时，又必须把数拆成多个机器字，管理进位和各部分运算。这样一来，乘法等操作的成本就随位数和算法变化，不能总当作一步。

6. 组合爆炸要靠表示、生成顺序和剪枝来应对

面对大量候选，关键是有组织地生成和搜索，并利用约束排除不可能的分支。提高效率通常依靠减少重复劳动和无效探索，而非消除所有困难。

为什么：组合对象的数量可能增长得极快，逐一从头构造并检查会浪费大量工作。合适的生成顺序可以复用相邻对象之间的信息，布尔表示和按位操作则能压缩部分处理过程。回溯在部分解已经违反约束时停止扩展，从而排除整棵无效子树。若修改还能低成本撤销，探索其他分支就不必反复重建状态；这些改进很有力，但不能据此保证所有实例都容易求解。

反对意见

程序设计不必从逐字操作机器出发（约翰·巴克斯）

巴克斯在《Can Programming Be Liberated from the von Neumann Style?》中认为，围绕赋值和状态变化组织程序，会把人的思考限制在逐字处理上，也妨碍用代数规律组合与变换程序。他提出函数式组合的替代方向。这与本书重视机器级实现的教学路线形成张力；这里是方法比较，并非声称该论文专门批评本书。见[论文原文](https://www.hinkali.com/Education/BackusTuringLecture1977.pdf)。

操作次数不足以单独预测现代机器性能（Frigo等）

Frigo、Leiserson、Prokop和Ramachandran在《Cache-Oblivious Algorithms》中把存储层次的数据传输纳入分析，研究无需预先知道缓存参数也能有效利用缓存的算法。它提醒我们：运算次数相近的程序，可能因数据访问方式而有不同表现。这补充和扩展了成本模型，并不推翻高德纳要求明确模型的原则，也不是对本书的直接书评。见[论文原文](https://ocw.mit.edu/courses/6-895-theory-of-parallel-systems-sma-5509-fall-2003/7e5331aae765482e87251ba75d9aeabe_cach_oblivs_focs.pdf)。

算法功底不能包办软件开发的困难（弗雷德里克·布鲁克斯）

布鲁克斯在《没有银弹》中把软件的本质困难放在复杂概念结构、外部约束、持续变化和不可见性上，强调需求与设计的难度。因此，读透算法也不能自动解决大型软件的需求判断、协作和演化问题。这是在限定本书能解决的问题范围，不是说高德纳曾宣称算法可以包办软件工程。见[文章原文重印本](https://worrydream.com/refs/Brooks_1986_-_No_Silver_Bullet.pdf)。