《算法导论》（Introduction to Algorithms）第二版 · 英文版
CLRS 经典的承上启下之作 —— 第一版（1990）奠定圣经地位，第二版（2001）全面更新并加入第四位作者 Clifford Stein，第三版（2009）进一步扩展。第二版是 CLRS 从”经典”走向”现代”的关键版本。
基本信息
| 项目 | 内容 |
|---|
| 书名 | Introduction to Algorithms, Second Edition |
| 作者 | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein |
| 出版社 | The MIT Press / McGraw-Hill Book Company |
| 出版年 | 2001（第三印刷 2002） |
| 页数 | 1203 页 |
| ISBN | 0-262-03293-7 (MIT Press) / 0-07-013151-1 (McGraw-Hill) |
| 版本定位 | 第一版（1990）→ 第二版（2001）→ 第三版（2009） |
| 配套资源 | mitpress.mit.edu/algorithms/ 官网 |
💡 文件名标注有误：文件名写的是”2001”和”第一版”，实际内容是第二版（封面/版权页明确标注 Second Edition，2001 年版权）。
一、第一版 → 第二版：重大变化
第二版的改动远超目录层面的调整。以下是官方列出的主要变化：
新增内容
| 类型 | 内容 |
|---|
| 新作者 | Clifford Stein 加入，成为第四位作者 |
| 新章节（3章） | 第1章（算法在计算中的角色）、第5章（概率分析与随机算法）、第29章（线性规划） |
| 新节（4节） | 11.5 完美哈希、15.1 流水线调度（DP新例）、15.5 最优二叉搜索树（DP新例）、35.4 随机化+线性规划的近似算法 |
| 新习题 | 185+ 道新练习题 |
| 新问题 | 40+ 个新问题 |
| 新参考文献 | 参考书目增长 50%+，新增大量第一版之后的研究成果 |
方法学革新
- 循环不变式（Loop Invariants）显性化：首次在第2章就引入循环不变式证明正确性，全书使用约 24 次，成为贯穿全书的证明方法论
- 指示器随机变量（Indicator Random Variables）：全书 12+ 处使用，大幅简化概率分析（特别是随机变量相关的情况）
- 递归树法升级：从”迭代法”改为”递归树法”作为独立方法（第4.2节），更直观不易出错，但强调仅用于生成猜测、需代入法验证
- 势函数方法更广泛应用：如第21.4节并查集复杂度证明改用势方法得到更紧的界
核心算法调整
| 章节 | 变化 |
|---|
| 快速排序（7.1） | 划分方法从 Hoare 版本改为 Lomuto 版本（配合指示器变量分析更简洁），Hoare 版本降为章末习题 |
| 顺序统计（9.2） | 同样改用 Lomuto 划分 |
| 通用哈希（11.3.3） | 重写，与完美哈希的呈现更整合 |
| 随机构建BST高度（12.4） | 分析大幅简化 |
| DP核心思想（15.3） | 显著扩充 |
| 贪心核心思想（16.2） | 显著扩充，以活动选择问题引导，阐明DP与贪心的关系 |
| 强连通分量（22.5） | 正确性证明更简洁直接 |
| 单源最短路径（24章） | 重组结构，将性质证明独立为一节，算法部分更早呈现 |
| NP完全性（34.5） | 扩充概述，新增哈密顿回路和子集和问题的NP完全性证明 |
删除内容
- 删除 2 章（从第一版移出）和若干小节
- 数学背景章节从第一部分移到附录（第八部分），让算法内容更早出现
- 删除了”迭代法”求解递归式（替换为递归树法）
二、第二版完整知识体系
全书共 7 大部分 + 附录（第八部分），35 章，1203 页。
与第三版（8大部分、35章、1313页）相比：第二版没有独立的”第八部分：算法设计中使用的数学技术”，相关内容合并在第一部分和附录中。
Part I: Foundations（基础）— 5章
| 章 | 标题 | 核心内容 |
|---|
| 1 | The Role of Algorithms in Computing | 算法定义、算法作为技术（🆕 第二版新增） |
| 2 | Getting Started | 插入排序、归并排序、分治法、循环不变式 |
| 3 | Growth of Functions | 渐近记号（Θ/O/Ω/o/ω）、标准函数 |
| 4 | Recurrences | 代入法、递归树法、主定理、主定理证明 |
| 5 | Probabilistic Analysis and Randomized Algorithms | 雇佣问题、指示器随机变量、随机化算法（🆕 第二版新增章） |
Part II: Sorting and Order Statistics（排序与顺序统计）— 4章
| 章 | 标题 | 核心内容 |
|---|
| 6 | Heapsort | 堆、维护堆性质、建堆、堆排序、优先队列 |
| 7 | Quicksort | Lomuto划分、性能分析、随机化版本、分析 |
| 8 | Sorting in Linear Time | 排序下界、计数排序、基数排序、桶排序 |
| 9 | Medians and Order Statistics | 最小最大值、期望线性时间选择、最坏情况线性时间选择 |
Part III: Data Structures（数据结构）— 5章
| 章 | 标题 | 核心内容 |
|---|
| 10 | Elementary Data Structures | 栈队列、链表、指针与对象实现、有根树表示 |
| 11 | Hash Tables | 直接寻址表、哈希表、哈希函数、开放寻址、完美哈希⭐ |
| 12 | Binary Search Trees | BST定义、查询、插入删除、随机构建BST高度 |
| 13 | Red-Black Trees | 性质、旋转、插入、删除 |
| 14 | Augmenting Data Structures | 动态顺序统计、数据结构扩充分两步走、区间树 |
⭐ = 第二版新增节
Part IV: Advanced Design and Analysis Techniques（高级设计与分析技术）— 3章
| 章 | 标题 | 核心内容 |
|---|
| 15 | Dynamic Programming | 流水线调度⭐、矩阵链乘、DP四要素、LCS、最优BST⭐ |
| 16 | Greedy Algorithms | 活动选择问题、贪心策略要素、哈夫曼编码、贪心理论基础、任务调度 |
| 17 | Amortized Analysis | 聚合分析、记账法、势方法、动态表 |
Part V: Advanced Data Structures（高级数据结构）— 4章
| 章 | 标题 | 核心内容 |
|---|
| 18 | B-Trees | B树定义、基本操作、删除 |
| 19 | Binomial Heaps | 二项树与二项堆、操作 |
| 20 | Fibonacci Heaps | 结构、可合并堆操作、减小关键字与删除、最大度界 |
| 21 | Data Structures for Disjoint Sets | 操作、链表表示、并查集森林、按秩合并+路径压缩分析 |
Part VI: Graph Algorithms（图算法）— 5章
| 章 | 标题 | 核心内容 |
|---|
| 22 | Elementary Graph Algorithms | 图表示、BFS、DFS、拓扑排序、强连通分量 |
| 23 | Minimum Spanning Trees | 生成MST、Kruskal与Prim算法 |
| 24 | Single-Source Shortest Paths | Bellman-Ford、DAG最短路径、Dijkstra、差分约束、最短路径性质证明 |
| 25 | All-Pairs Shortest Paths | 最短路径与矩阵乘法、Floyd-Warshall、Johnson算法 |
| 26 | Maximum Flow | 流网络、Ford-Fulkerson方法、最大二分匹配、推送-重贴标签、重贴标签前置算法 |
Part VII: Selected Topics（精选主题）— 9章
| 章 | 标题 | 核心内容 |
|---|
| 27 | Sorting Networks | 比较网络、零一原则、双调排序网络、合并网络、排序网络 |
| 28 | Matrix Operations | 矩阵性质、Strassen矩阵乘法、线性方程组求解、矩阵求逆、对称正定矩阵与最小二乘 |
| 29 | Linear Programming | 标准型/松弛型、问题建模、单纯形算法、对偶性、初始基本可行解（🆕 第二版新增章） |
| 30 | Polynomials and the FFT | 多项式表示、DFT与FFT、高效FFT实现 |
| 31 | Number-Theoretic Algorithms | 初等数论、GCD、模运算、模线性方程、中国剩余定理、元素的幂、RSA、素性测试、整数分解 |
| 32 | String Matching | 朴素算法、Rabin-Karp、有限自动机、KMP算法 |
| 33 | Computational Geometry | 线段性质、线段相交检测、凸包、最近点对 |
| 34 | NP-Completeness | 多项式时间、多项式时间验证、NP完全性与归约、NP完全性证明、NP完全问题 |
| 35 | Approximation Algorithms | 顶点覆盖、TSP、集合覆盖、随机化与LP⭐、子集和 |
Part VIII: Appendix — Mathematical Background（数学背景附录）
| 章 | 标题 |
|---|
| A | Summations（求和） |
| B | Sets, Etc.（集合等） |
| C | Counting and Probability（计数与概率） |
- Bibliography（参考书目）+ Index（索引）
三、第二版 vs 第三版：主要差异
已有第三版笔记（《算法导论》-Introduction to Algorithms-第3版-CLRS），此处重点梳理差异。
| 维度 | 第二版（2001） | 第三版（2009） |
|---|
| 总页数 | 1203 页 | 1313 页 |
| Part 数量 | 7 + 附录 | 8 大部分 |
| 章节数 | 35 章 | 35 章（但内容大幅扩充） |
| 新 Part VIII | — | Algorithm Design Techniques 中的数学内容独立成第八部分 |
| Van Emde Boas 树 | ❌ 无 | ✅ 第20章（原二项堆/斐波那契调整） |
| 多线程算法 | ❌ 无 | ✅ 第27章（排序网络移到其他位置） |
| 矩阵运算 | 第28章 | 第28章（内容扩充） |
| 线性规划 | 第29章（新增） | 第29章（进一步扩充） |
| 斐波那契堆 | 第20章 | 第19章（调整） |
| 二项堆 | 第19章 | 第19章（调整） |
| 排序网络 | 第27章 | 移到问题/练习中 |
| 习题问题 | 920+ 练习 / 140+ 问题 | 更多（未统计具体数量） |
| 参考文献 | 约 50% 多于第一版 | 进一步更新至 2009 年 |
阅读建议：如果已有第三版，第二版可作为补充参考——特别是对比算法呈现方式的演变。但如果只读一本，优先第三版。
四、第二版 vs 中文版（原书第2版）
已有中文版笔记（《算法导论》-中文版-原书第2版-CLRS）
| 维度 | 英文第二版 | 中文第二版（潘金贵等译） |
|---|
| 页数 | 1203 页 | 761 页（排版更紧凑） |
| 文本质量 | 文字版 PDF，可搜索复制 | 扫描版 PDF，需 OCR |
| 翻译质量 | — | 潘金贵等译，机械工业出版社，国内经典译本 |
| 公式清晰度 | 矢量公式，清晰 | 扫描公式，部分偏小 |
| 使用场景 | 适合精读、术语对照、查阅英文原文 | 适合快速通读、中文理解 |
五、第二版的独特价值
为什么有了第三版还要看第二版？
- 历史文献价值：第二版是 CLRS 走向成熟的关键版本，许多人的算法入门就是第二版（包括大量国内高校教材参考的是第二版）
- 排序网络：第二版有完整的第27章排序网络，第三版大幅压缩（这部分内容在并行计算课程中仍很重要）
- 二项堆：第二版第19章完整的二项堆，第三版大幅压缩（斐波那契堆的前置知识）
- Lomuto vs Hoare 划分：第二版用 Lomuto（配合指示器变量分析简洁），第三版也延续了这一选择
- 算法演进对照：对比第一版→第二版→第三版的变化，可以看到算法领域 20 年间的研究热点迁移
六、使用建议
学习路径
入门 → 第1-3章（基础+渐近记号）
↓
排序 → 第6-9章（堆排序/快排/线性时间排序/顺序统计）
↓
数据结构 → 第10-14章（基础结构/哈希/BST/红黑树/扩充数据结构）
↓
设计方法 → 第15-17章（DP/贪心/摊还分析）
↓
高级数据结构 → 第18-21章（B树/二项堆/斐波那契/并查集）
↓
图算法 → 第22-26章（基础图/MST/最短路径/最大流）
↓
高级主题 → 第27-35章（按需选读）
配合已有笔记的阅读方式
- 系统学习算法：直接读第三版笔记（内容最新最全）
- 对照中文理解：参考中文第二版笔记（术语对照+版本差异）
- 研究排序网络/二项堆：回到本笔记（第二版有完整章节，第三版已删减）
关联笔记