《算法导论》中文版（原书第2版）
经典算法教材 Introduction to Algorithms 的中文第二版。CLRS 四位作者经典之作，7大部分35章，全面覆盖算法设计与分析。
基本信息
- 书名：算法导论（原书第2版）
- 作者：Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein
- 译者：潘金贵、顾铁成、李成法、叶懋 等
- 出版社：机械工业出版社
- 页数：761页
- 版本特征：第二版（共7大部分、35章），与第三版章节结构有差异
- 来源说明：扫描版 PDF，带 bbs.theithome.com 论坛水印，前17页为论坛序言文章，非原书内容
第二版 vs 第三版 主要差异
| 维度 | 第二版（中文版） | 第三版（英文版） |
|---|---|---|
| 总章节数 | 35章 | 35章（但内容扩充） |
| 大部分数 | 7大部分 | 8大部分 |
| 新增内容（第三版比第二版多） | — | 多线程算法（第27章）、van Emde Boas树（第20章） |
| 章编号差异 | 第27章：排序网络 第28章：矩阵运算 第29章：线性规划 第30章：多项式与FFT 第31章：数论算法 第32章：字符串匹配 第33章：计算几何 第34章：NP完全性 第35章：近似算法 | 第27章：多线程算法（新增） 后续章节编号相应后移 |
| 数据结构部分 | 第18章B树、第19章斐波那契堆、第20章？（待确认，第二版第20章可能是不相交集合） | 第18章B树、第19章斐波那契堆、第20章van Emde Boas树（新增）、第21章不相交集合 |
| 递归式章节 | 第4章：递归式（代换法、递归树、主方法） | 第4章：分治策略（主方法+主定理更多情形） |
注：第三版新增的”多线程算法”和”van Emde Boas树”在第二版中没有。第二版的”排序网络”（第27章）在第三版中移至第27章多线程算法之后的不同位置。
全书结构（7大部分35章）
第一部分 基础知识（第1-5章）
- 第1章 算法在计算中的作用
- 1.1 算法
- 1.2 作为一种技术的算法
- 第2章 算法入门
- 2.1 插入排序
- 2.2 算法分析
- 2.3 算法设计（分治法）
- 第3章 函数的增长
- 3.1 渐近记号（Θ, O, Ω, o, ω）
- 3.2 标准记号和常用函数
- 第4章 递归式
- 4.1 代换法
- 4.2 递归树方法
- 4.3 主方法
- *4.4 主定理的证明
- 第5章 概率分析和随机算法
- 5.1 雇用问题
- 5.2 指示器随机变量
- 5.3 随机算法
- *5.4 概率分析的进一步使用（生日悖论、球与盒子、序列、在线雇用问题）
第二部分 排序和顺序统计学（第6-9章）
- 第6章 堆排序（堆、保持堆性质、建堆、堆排序算法、优先级队列）
- 第7章 快速排序（描述、性能、随机化版本、分析）
- 第8章 线性时间排序（下界、计数排序、基数排序、桶排序）
- 第9章 中位数和顺序统计学（最小最大值、期望线性时间选择、最坏情况线性时间选择）
第三部分 数据结构（第10-14章）
- 第10章 基本数据结构（栈和队列、链表、指针和对象的实现、有根树的表示）
- 第11章 散列表（直接寻址、散列表、散列函数、开放寻址法、完全散列）
- 第12章 二叉搜索树
- 第13章 红黑树
- 第14章 数据结构的扩张
第四部分 高级设计和分析技术（第15-17章）
- 第15章 动态规划
- 第16章 贪心算法
- 第17章 摊还分析
第五部分 高级数据结构（第18-21章）
- 第18章 B树
- 第19章 斐波那契堆
- 第20章（待确认具体章名，第二版可能为”二项堆”或结构不同）
- 第21章 用于不相交集合的数据结构
第六部分 图算法（第22-26章）
- 第22章 图的基本算法
- 第23章 最小生成树
- 第24章 单源最短路径
- 24.1 Bellman-Ford算法
- 24.2 有向无回路图中的单源最短路径
- 24.3 Dijkstra算法
- 24.4 差分约束与最短路径
- 24.5 最短路径性质的证明
- 第25章 每对顶点间的最短路径
- 25.1 最短路径与矩阵乘法
- 25.2 Floyd-Warshall算法
- 25.3 稀疏图上的Johnson算法
- 第26章 最大流
- 26.1 流网络
- 26.2 Ford-Fulkerson方法
- 26.3 最大二分匹配
- *26.4 压入与重标记算法
- *26.5 重标记与前移算法
第七部分 算法研究问题选编（第27-35章）
这是第二版的特色命名，第三版改为”第八部分 算法问题选编”且前置了多线程算法
- 第27章 排序网络（比较网络、0-1原理、双调排序网络、合并网络、排序网络）
- 第28章 矩阵运算（矩阵性质、Strassen算法、线性方程组、矩阵求逆、对称正定矩阵与最小二乘）
- 第29章 线性规划（标准型和松弛型、问题表达、单纯形算法、对偶性、初始基本可行解）
- 第30章 多项式与快速傅里叶变换（多项式表示、DFT与FFT、有效FFT实现）
- 第31章 有关数论的算法（初等数论、最大公约数、模运算、模线性方程、中国余数定理、元素的幂、RSA公钥加密、*素数测试、*因子分解）
- 第32章 字符串匹配（朴素算法、Rabin-Karp、有限自动机、*KMP算法）
- 第33章 计算几何学（线段性质、相交、凸包、最近点对）
- 第34章 NP完全性（多项式时间、验证、NP完全性与可归约性、证明方法、NP完全问题：团/顶点覆盖/哈密顿回路/旅行商/子集和）
- 第35章 近似算法（顶点覆盖、旅行商问题、集合覆盖、随机化和线性规划、子集和）
中英文术语对照表（核心概念）
| 英文 | 中文（本书译法） |
|---|---|
| Algorithm | 算法 |
| Asymptotic notation | 渐近记号 |
| Θ (Theta) | Θ（西塔） |
| O (Big O) | O（大O） |
| Ω (Omega) | Ω（欧米伽） |
| Divide and conquer | 分治法 |
| Recurrence | 递归式 |
| Substitution method | 代换法 |
| Recursion-tree method | 递归树方法 |
| Master method | 主方法 |
| Master theorem | 主定理 |
| Probabilistic analysis | 概率分析 |
| Randomized algorithm | 随机算法 |
| Indicator random variable | 指示器随机变量 |
| Heap sort | 堆排序 |
| Priority queue | 优先级队列 |
| Quick sort | 快速排序 |
| Counting sort | 计数排序 |
| Radix sort | 基数排序 |
| Bucket sort | 桶排序 |
| Order statistic | 顺序统计学 |
| Hash table | 散列表（哈希表） |
| Open addressing | 开放寻址法 |
| Perfect hashing | 完全散列 |
| Binary search tree | 二叉搜索树 |
| Red-black tree | 红黑树 |
| Augmenting data structures | 数据结构的扩张 |
| Dynamic programming | 动态规划 |
| Greedy algorithm | 贪心算法 |
| Amortized analysis | 摊还分析 |
| B-tree | B树 |
| Fibonacci heap | 斐波那契堆 |
| Disjoint set | 不相交集合 |
| Minimum spanning tree | 最小生成树 |
| Shortest path | 最短路径 |
| Bellman-Ford algorithm | Bellman-Ford算法 |
| Dijkstra algorithm | Dijkstra算法 |
| Floyd-Warshall algorithm | Floyd-Warshall算法 |
| Johnson algorithm | Johnson算法 |
| Maximum flow | 最大流 |
| Ford-Fulkerson method | Ford-Fulkerson方法 |
| Bipartite matching | 二分匹配 |
| Push-relabel | 压入与重标记 |
| Sorting network | 排序网络 |
| Bitonic sorter | 双调排序网络 |
| 0-1 principle | 0-1原理 |
| Strassen algorithm | Strassen算法 |
| Linear programming | 线性规划 |
| Simplex algorithm | 单纯形算法 |
| Duality | 对偶性 |
| Fast Fourier Transform (FFT) | 快速傅里叶变换 |
| Number-theoretic algorithm | 数论算法 |
| Greatest common divisor (GCD) | 最大公约数 |
| Modular arithmetic | 模运算 |
| Chinese remainder theorem | 中国余数定理 |
| RSA | RSA公钥加密系统 |
| Primality test | 素数测试 |
| String matching | 字符串匹配 |
| Rabin-Karp algorithm | Rabin-Karp算法 |
| KMP algorithm | KMP算法（Knuth-Morris-Pratt） |
| Computational geometry | 计算几何学 |
| Convex hull | 凸包 |
| NP-completeness | NP完全性 |
| Polynomial time | 多项式时间 |
| Reducibility | 可归约性 |
| Clique | 团 |
| Vertex cover | 顶点覆盖 |
| Hamiltonian cycle | 哈密顿回路 |
| Traveling salesman problem | 旅行商问题 |
| Subset sum | 子集和 |
| Approximation algorithm | 近似算法 |
| Set cover | 集合覆盖 |
中文版阅读建议
- 与英文版对照使用：中文术语翻译总体规范，但部分术语（如”摊还分析”对应 amortized analysis、“散列表”对应 hash table）在不同文献中有不同译法，建议中英文术语对照记忆
- 第二版与第三版的选择：
- 初学者：第三版内容更新更全，推荐优先
- 论文/代码引用第二版算法的：可参考第二版章节编号
- 第二版的”排序网络”一章位置更靠前（第27章），第三版移至更后
- 学习路径（推荐）：
- 基础：第1-5章（算法基础+数学工具）
- 核心：第6-9章（排序）+ 第10-14章（数据结构）
- 进阶：第15-17章（设计技术）+ 第22-26章（图算法）
- 高级：第18-21章（高级数据结构）+ 第27-35章（专题）
- 学习方法：
- 每章配合练习（exercises）和思考题（problems）
- 带
*的章节为选学/进阶内容 - 伪代码是核心，务必理解每一步
相关笔记
- 《算法导论》-Introduction to Algorithms-第3版-CLRS — 英文第三版详细笔记（1313页，8大部分35章+4附录）
- 《数据结构与算法》-Rust实现-Shieber — Rust 语言视角的数据结构与算法
- 《程序设计实践》-The-Practice-of-Programming-Kernighan-Pike — 算法与编程实践的结合
备注
- 本笔记基于扫描版中文 PDF 整理，通过目录页 OCR 确认全书结构
- 部分章节的具体小节标题可能与实际有细微出入，以原书为准
- 第二版与第三版的差异是本笔记重点，详细算法知识请参考第三版笔记