算法导论

引用

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

章节概要

第四版共有 35 章，分为七个部分，之后是数学背景附录，全书约 1,300 页（MIT Press 列出的精装本于 2022 年 4 月 5 日出版，共 1,312 页）。每一部分都以一篇简短的导言开头。

第一部分，第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章把递归式设计与求解由此产生的递归方程的方法放在一起讲。MIT Press 将递归方程的新增内容列为第四版的改动之一。
• 随机算法：第5章引入对算法的概率分析。

第6–19章

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

第20–35章

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

评析

优点

• 严谨而全面。 出版社称本书兼具严谨性与全面性，各章自成体系，算法用伪代码书写，读者可以从许多地方切入。
• 附有数学背景。 附录 A–D 涵盖求和、集合、计数与概率、矩阵，大部分预备知识可以在书中自行复习。
• 习题与思考题。 第四版新增 140 道习题和 22 道思考题，并根据读者反馈改进了原有的题目。
• 内容较新。 本版新增了二分图匹配、在线算法和机器学习三章，并在递归式、散列表、势函数和后缀数组方面增加了新内容。
• 呈现方式经过修订。 据 MIT Press 介绍，第四版增加了彩色印刷，并修订了文字，使其更清晰、更具个人色彩且性别中立。
• 长期的教学积累。 几十年来课程持续指定本书，下文“常见课程指定阅读”中的近年课表与存档大纲都按章模块化选读。注意版次：第二版 2001 年，第三版 2009 年，第四版 2022 年，因此 2005 年的课程用的是第二版，而不是第三版。

局限

• 篇幅庞大。 全书 35 章、一千多页，既是教材也是参考书；没有哪一门课程能覆盖全部内容，读者必须取舍。下文列出的课程都没有指定阅读全书，例如 Stanford 2016 年春季的课程指定的是 2.3、3.1、4.3–4.5 和 8.1–8.2 等单独小节，而不是整个部分。
• 只有伪代码。 算法以伪代码给出，想要可运行程序的读者需要自行实现。
• 专题部分较简略。 线性规划（约27页）和机器学习（约39页）等主题各只有一章，更像入门介绍，而不是完整论述。
• 对初学者要求较高。 数学化的写法和篇幅使它作为算法的第一本书比较吃力；配合课堂讲授或作为第二遍阅读效果更好。
• 课程材料与版本不匹配。 若干可免费获取的大纲按旧版编号：下文的 Stanford 2016 与 MIT 2011 课程用第三版章节，MIT 2020 课程仅把第三版列为可选参考，而 2005 年的 MIT 与 Berkeley 清单早于第三版。第四版对部分章节重新编号（尤其是图算法部分），并新增章节，因此阅读清单不能直接套用。

在课程中的定位

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

Kleinberg 和 Tardos 的 Algorithm Design 在下文 Stanford 2016 年春季的课程中被列为替代教材。

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

如何使用本书

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

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

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

常见课程指定阅读

公开的阅读清单展示了各课程如何有选择地使用本书。章节编号以各大纲所标明的版次为准——并不都与第四版一致。第四版对大量图算法材料重新编号（例如基本图算法在第四版课表中为第 20 章，在第三版课表中为第 22 章），并新增章节，因此在套用旧清单前，请用 MIT Press 的第三版到第四版过渡指南对应主题。

近年（约八年内）：

• Johns Hopkins 601.433/633，2024 年秋季（要求第3版；第4版也可）： 课表阅读覆盖第1–9、11–13、15–18、21–26、29、34–35章，末尾还有在线算法与算法学习讲座。内容从渐近分析与排序一直延伸到图、流、线性规划、NP 完全性与近似算法，面向本科生和研究生。(课表)
• MIT OCW 6.006，2020 年春季（第3版作可选参考）： 书面材料以讲义与习题课笔记为主；第三版 CLRS 列为有用但非必读的参考。(大纲)

第四版课表（页面未标明开课年份）：

• UC Denver CSCI 5451（第4版，2022 年教材）： 第1、3–4、6–7、9、12–15、19–24、28–29、32、34–35章。明确使用第四版编号（基本图算法第20章，最小生成树第21章，最大流第24章）。(课程页)

较早存档清单：

• Stanford CS 161，2016 年春季（第3版）： 第1章；2.3、3.1；4.3–4.5；第9章；第7章和第5章；8.1–8.2；第12章；第11章；第22章；第24章和第6章；24.3；24.1 和 24.3；25.2 和 15.4；第16章和第23章；26.1–26.3。
• MIT OCW 6.006，2011 年秋季（第3版）： 第1章和第3章；2.1–2.3、4.3–4.6；6.1–6.4；12.1–12.3；8.1–8.3；11.1–11.4；17；22.1–22.4；24.；15.；34.1–34.3。
• MIT OCW 6.046J，2005 年秋季（第2版，2001）： 第1–9、11–17、22–25章。早于 2009 年第三版；章节编号按第二版理解。
• UC Berkeley CS 170，2005 年秋季（第2版）： 第1–5、11、15章，16.3，第21–24、26、29–30、34–35章。同样注意：是第二版，不是第三版。

在这些清单中，基础、排序、散列、基本图算法和动态规划构成共同核心；后面的“专题选讲”各章只出现在部分课程中。

版别说明

MIT Press 2022 年第四版精装 ISBN 为 9780262046305（电子版另有标识）。套用任何大纲前，先把节名和伪代码与手中的版本对照。用上面的过渡指南把第三版阅读对应到第四版章节编号，而不要凭标题猜测。