算法导论

引用

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). The MIT Press.

章节概要

第四版共有 35 章，分为七个部分，之后是数学背景附录，全书约 1,300 页。每一部分都以一篇简短的导言开头。

第一部分，第1–5章：基础

第1章“算法在计算中的角色”（The Role of Algorithms in Computing）和第2章“入门”（Getting Started）介绍算法及其分析。第3章“刻画运行时间”（Characterizing Running Times）讲渐近记号；第4章“分治”（Divide-and-Conquer）是这一部分中篇幅最长的章节之一；第5章“概率分析与随机算法”（Probabilistic Analysis and Randomized Algorithms）为后文的随机化方法打下基础。

第二部分，第6–9章：排序与顺序统计量

堆排序、快速排序、线性时间排序，以及中位数与顺序统计量。这几章合起来涵盖比较排序、非比较排序和选择问题。

第三部分，第10–13章：数据结构

基本数据结构、散列表、二叉搜索树和红黑树。散列表有一章约四十页的篇幅，本版的更新说明中也列出了散列表的新增内容。

第四部分，第14–16章：高级设计与分析技术

动态规划、贪心算法和摊还分析。动态规划是全书较长的章节之一（约55页）。这一部分介绍了两种主要的优化问题设计策略，以及分析操作序列的主要工具。

第五部分，第17–19章：高级数据结构

数据结构的扩张、B 树和不相交集合的数据结构。

第六部分，第20–25章：图算法

基本图算法、最小生成树、单源最短路径、所有结点对最短路径、最大流，以及二分图中的匹配。最后一章是本版新增的。

第七部分，第26–35章：专题选讲

并行算法、在线算法、矩阵运算、线性规划、多项式与快速傅里叶变换、数论算法、字符串匹配、机器学习算法、NP 完全性和近似算法。在线算法和机器学习算法是本版新增的章节。NP 完全性和近似算法为这一部分收尾。

附录：数学背景

求和、集合等、计数与概率、矩阵（附录 A–D），之后是参考文献和索引。

核心概念

第1–5章

• 渐近记号与运行时间：不依赖具体机器、用来比较算法的一套词汇，在第3章展开。
• 分治与递归式：第4章把递归式设计与求解由此产生的递归方程的方法放在一起讲。
• 随机算法：第5章引入对算法的概率分析。

第6–19章

• 排序下界与选择：第6–9章区分比较排序与线性时间排序，并讲授顺序统计量。
• 动态规划、贪心算法、摊还分析：第四部分的三种技术。
• 平衡与扩张的搜索结构：红黑树、B 树及数据结构的扩张（第13、17、18章）。

第20–35章

• 最短路径、生成树、流与匹配：第六部分的图算法各章。
• NP 完全性与近似：第34、35章，讨论被认为没有高效精确算法的问题及其近似。
• 专题选讲：并行与在线算法、线性规划、快速傅里叶变换、数论、字符串匹配和机器学习，各为简短而自足的一章。

评析

优点

• 严谨而全面。 出版社称本书兼具严谨性与全面性，各章自成体系，算法用伪代码书写，读者可以从许多地方切入。
• 附有数学背景。 附录 A–D 涵盖求和、集合、计数与概率、矩阵，大部分预备知识可以在书中自行复习。
• 习题与思考题。 第四版新增 140 道习题和 22 道思考题，并根据读者反馈改进了原有的题目。
• 内容较新。 本版新增了二分图匹配、在线算法和机器学习三章，并在递归式、散列表、势函数和后缀数组方面增加了新内容。

局限

• 篇幅庞大。 全书 35 章、一千多页，既是教材也是参考书；没有哪一门课程能覆盖全部内容，读者必须取舍。
• 只有伪代码。 算法以伪代码给出，想要可运行程序的读者需要自行实现。
• 专题部分较简略。 线性规划（约27页）和机器学习（约39页）等主题各只有一章，更像入门介绍，而不是完整论述。
• 对初学者要求较高。 数学化的写法和篇幅使它作为算法的第一本书比较吃力；配合课堂讲授或作为第二遍阅读效果更好。

在课程中的定位

在算法课程中，这是一本综合性的参考书。Cormen 自己的 Algorithms Unlocked 是一本讲解算法如何工作的简短入门书，写给尚未准备好读本书的读者；Roughgarden 的 Algorithms Illuminated 用对话式的风格讲解标准的设计范式，并配有视频讲座。两者都适合作为第一遍阅读。Skiena 的 The Algorithm Design Manual 是识别问题、选择设计方案的实用指南，并附有问题目录，当目标是实现时，与本书搭配很合适。

在专门方向上，本书第35章是对近似算法的简短介绍，Vazirani 的 Approximation Algorithms 与 Williamson 和 Shmoys 的 The Design of Approximation Algorithms 则作了完整展开。Mitzenmacher 等人的 Probability and Computing 扩展了第5章开始的随机化内容。

如何使用本书

本书适合高年级本科生和研究生，也可以作为长期的参考书。熟悉证明、求和与基本概率会有帮助，附录 A–D 可以用来复习。

典型的第一门课程读第一、二部分，再选读第三、四部分的若干章节（散列表、二叉搜索树、动态规划、贪心算法），然后读第六部分的基本图算法、生成树和最短路径。摊还分析、B 树、最大流和 NP 完全性是自然的第二学期主题。第七部分各章大多相互独立，可按兴趣任意顺序阅读。

阅读每一章时请配合习题和思考题。伪代码最好先用手逐步跟踪，再用自己选择的语言写出来。