01 / 导读
导读
引用
Roughgarden, T. (2022). Algorithms Illuminated: Omnibus Edition. Soundlikeyourself Publishing (distributed by Cambridge University Press).
章节概要
合订本（2022年9月）把分别出版的 Algorithms Illuminated 四个分册汇为一册约690页的精装书，并删去了重复内容。全书分四部分共24章，另有两个附录、一篇后记（"算法设计实地指南"）以及提示与解答。序言把本书比作一位资深辅导老师在一年一对一授课中所讲内容的记录，它基于作者自2012年起开设的在线课程和他在斯坦福大学讲授的本科课程。带星号的小节最为高深，初读时可以跳过而不影响连贯性；每章以"Upshot"（要点）小结和习题结束。
第一部分 第1–2章：引言；渐近记号
全书从整数乘法和Karatsuba算法讲起，接着是归并排序及其分析，并以算法分析的指导原则结束第1章。第2章讲大O、大Ω和大Θ记号；序言解释说，这是刻意忽略常数因子和低阶项的一种建模选择。
第一部分 第3–6章：分治算法；主定理；快速排序；线性时间选择
把分治法用于计算逆序对、Strassen矩阵乘法和最近点对；用主定理分析这类递推式，给出六个例子和带星号的证明；随机化快速排序，包括好的枢轴为何重要，以及排序需要Ω(n log n)次比较的带星号证明；最后是用随机化的RSelect和确定性的DSelect实现线性时间选择。
第二部分 第7–9章：图的基础；图搜索及其应用；Dijkstra最短路径算法
讲图的术语、应用、规模和表示方法；广度优先搜索与最短路径、连通分量、深度优先搜索、拓扑排序、强连通分量以及网络（Web）的结构；然后是Dijkstra算法，附带星号的正确性证明及其运行时间分析。
第二部分 第10–12章：堆；搜索树；散列表与布隆过滤器
序言说这一部分的目标是让读者成为数据结构的"内行用户"，实现细节放在可选的带星号小节中。堆的部分包括用它加速Dijkstra算法；搜索树从有序数组讲到平衡搜索树；散列表之后是布隆过滤器以及对其错误率的启发式分析。
第三部分 第13–15章：贪心算法入门；哈夫曼编码；最小生成树
通过一个调度问题及其正确性证明介绍贪心范式；把最优前缀码看作树的哈夫曼算法；以及Prim算法和Kruskal算法求最小生成树，分别借助堆和并查集加速，并给出单链接聚类的应用。
第三部分 第16–18章：动态规划入门；高级动态规划；再论最短路径
通过路径上的加权独立集问题引入动态规划，配以重构算法、方法的原理和背包问题；接着是序列比对和最优二叉搜索树；最后是处理负边长的Bellman-Ford算法和求全源最短路径的Floyd-Warshall算法。
第四部分 第19–21章：什么是NP困难性？；在正确性上妥协：高效的非精确算法；在速度上妥协：精确但低效的算法
第四部分从最小生成树与旅行商问题的对比出发，讲解容易与困难的问题、应对NP困难问题的策略、证明NP困难性的简单方法以及常见的"新手错误"。第20章讲快速的非精确算法：最小化完工时间、最大覆盖、影响力最大化、2-OPT启发式算法以及局部搜索的原理。第21章讲精确但缓慢的方法：Bellman-Held-Karp算法、用颜色编码寻找长路径，以及何时使用混合整数规划求解器和可满足性（SAT）求解器。
第四部分 第22–24章：证明问题是NP困难的；P、NP及其他；案例研究：FCC激励拍卖
讲归约、3-SAT与Cook-Levin定理、归约模板，以及独立集、有向哈密顿路径、旅行商问题和子集和问题的NP困难性证明；全部小节带星号的一章讨论P、NP、P≠NP猜想、指数时间假设和NP完全性；最后是美国频谱拍卖的案例研究，展示贪心启发式和借助求解器的可行性检验如何在实践中使用。
附录、后记与提示
数学归纳法证明和离散概率的简要回顾、算法设计实地指南，以及章末习题的提示或解答。
核心概念
第一部分：基础
- 渐近记号：大O、大Ω和大Θ，描述运行时间如何随输入规模增长。
- 分治法：分成子问题、递归求解、快速合并。
- 主定理：给出许多分治递推式运行时间的公式。
- 随机化算法：运行中"抛硬币"的算法，如随机化快速排序和RSelect。
第二部分：图算法与数据结构
- 线性时间的图搜索：广度优先和深度优先搜索及其在连通性和排序上的应用。
- Dijkstra算法：边长非负时的单源最短路径。
- 堆、搜索树和散列表：根据应用所需的操作来选择的结构；布隆过滤器以偶尔出错为代价节省空间。
第三部分：贪心算法与动态规划
- 贪心范式与正确性证明：短视且不可撤销的决策，只对特定问题是最优的。
- 最小生成树与并查集：Prim和Kruskal算法，以及加速Kruskal算法的数据结构。
- 动态规划：系统地求解重叠子问题，如背包问题、序列比对和Bellman-Ford算法。
第四部分：NP困难问题的算法
- NP困难性与归约：识别那些不太可能有总是正确又总是快速的算法的问题。
- 启发式与局部搜索：在正确性上妥协的快速算法。
- 精确的指数时间算法与求解器：用动态规划、MIP和SAT求解器改进穷举搜索。
评析
优点
- 为教学而设计。 序言介绍，正文中穿插了100多道附有解答和说明的小测验；章末习题从简单的检查题到开放性的挑战题都有，全部附有提示或解答；配套网站还提供带测试用例的编程题。
- 大部头中有清晰的路线。 星号标出可以跳过的高深内容，每章以"Upshot"结束，序言还说明了哪些章节组彼此独立（分治、贪心和动态规划可以按任意顺序讲授）。
- 免费视频课程。 作者录制了200多个视频，覆盖每一小节，另有Karger收缩算法、Johnson算法等额外主题，适合翻转课堂或自学。
- 对NP困难性的实用处理。 第四部分不止于证明困难性，还讲接下来该怎么办：启发式、局部搜索、精确的指数时间算法、MIP和SAT求解器，以及一个真实案例。
局限
- 只有伪代码，没有代码。 本书用伪代码描述算法，实现留给编程题；想要某种语言现成代码的读者需要其他资料。
- 数学先修要求。 序言假定读者有一定编程经验，并熟悉数学归纳法和反证法；附录只是简要回顾。缺乏这些基础的读者能跟上算法设计，但跟不上分析。
- 内容有所取舍。 网络流和线性规划等主题没有出现在目录中，一些高级主题只在在线视频里。
- 篇幅大。 约690页的合订本超出一门课的容量；序言本身就建议把它分给本科课程（第一至三部分）和硕士课程（第三至四部分）。
在课程中的定位
本书是本课程第一门算法课的主教材。Cormen的 Algorithms Unlocked 篇幅短、数学少，面向尚未准备好读教科书的读者，可作为第一、二部分的预习。Skiena的 The Algorithm Design Manual 以实践的角度讲解类似的技术，并附有算法问题目录，在应用算法时可与Roughgarden同时或之后使用。Cormen、Leiserson、Rivest和Stein的 Introduction to Algorithms 是全面的教科书和参考书，适合想要严格论述和更广覆盖面的学生，其中包括本书没有涉及的主题。
第四部分通向课程中的专门著作。Vazirani的 Approximation Algorithms 以及Williamson和Shmoys的 The Design of Approximation Algorithms 接续第20章"在正确性上妥协"的主题，讨论有保证的近似比；Mitzenmacher和Upfal的 Probability and Computing 则展开随机化快速排序、RSelect和布隆过滤器背后的概率论。
如何使用本书
本书适合二、三年级前后的计算机科学本科生、会编程并能读懂证明的自学者，以及准备面试的软件工程师。如有需要，先用附录A和B复习归纳法和概率。
实用阅读计划：
- 第一门课（核心）： 第一至三部分，即第1–18章，初读时跳过带星号的小节。序言指出，数据结构各章（第10–12章）可以放在图的各章（第7–9章）之前或之后，10.4节除外。
- 第二门课或自学： 第四部分，从第19章开始，再读讲实用技术的第20–21章和讲归约的第22章。第23章全部带星号，可选读；第24章是激发兴趣的案例研究。
- 带星号的小节： 掌握主要思想后，再回来读其中的证明（主定理、快速排序的分析、Dijkstra算法的正确性）。
遇到小测验就停下来，先作答再往下读。先做章末习题，之后再查看提示和解答。每章至少借助配套网站的测试用例实现一个算法，书面难懂的小节可以看视频。考前阅读各章的"Upshot"和实地指南。
