《算法导论》第三版笔记
来源: /books/算法导论/Intro to Algorithm 3rd.pdf
作者: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
页数: 1313页
文件大小: 4.84MB
处理日期: 2026-09-02
处理方法: pdf-inspector文本提取
核心概述
《算法导论》（Introduction to Algorithms，简称CLRS）是算法领域的”圣经级”教材，由麻省理工学院出版社出版。本书系统、严谨地介绍了计算机算法的设计与分析方法，是大学本科至研究生算法课程的标准教材，也是工程师的权威参考书。
核心特点：
- 强调算法的严谨数学分析
- 提供伪代码实现，易于转化为实际代码
- 涵盖算法设计与分析的广泛主题
- 每章包含957个练习题和188个问题（case studies）
内容结构
Part I: 基础 (Foundations)
第1章 - 算法在计算中的作用
- 算法的定义与表示
- 算法作为一种技术：效率、正确性、可读性
- 选择排序 vs 插入排序
第2章 - 算法基础
- 插入排序（Insertion Sort）
- 分析算法：最坏情况、平均情况
- 分治法设计思路
第3章 - 渐进符号
- O符号（上界）、Ω符号（下界）、Θ符号（紧界）
- 标准记法和常用函数
- 渐近记法的性质
第4章 - 分治法
- 最大子数组问题
- Strassen矩阵乘法算法
- 递推式的三种解法：代入法、递归树法、主方法
- 主定理（Master Theorem）详解
第5章 - 概率分析与随机算法
- 雇佣问题与指示器随机变量
- 随机算法设计
- 期望线性时间排序
Part II: 排序与顺序统计 (Sorting and Order Statistics)
第6章 - 堆排序
- 堆数据结构（完全二叉树）
- 维护堆性质
- 建堆与堆排序算法
第7章 - 快速排序
- 快速排序算法描述
- 性能分析（平均情况、最坏情况）
- 随机化版本
第8章 - 线性时间排序
- 排序的下界证明（比较排序）
- 计数排序、基数排序、桶排序
第9章 - 中位数与顺序统计量
- 最小最大值
- 期望线性时间选择算法
- 最坏情况线性时间选择
Part III: 数据结构 (Data Structures)
第10章 - 基本数据结构
- 栈、队列、链表
- 指针和对象的实现
- 有根树的表示
第11章 - 哈希表
- 直接寻址表
- 哈希函数设计
- 链地址法、开放寻址法
- 完美哈希
第12章 - 二叉搜索树
- BST的基本操作
- 随机构建BST的分析
- 时间复杂度：O(h)，h为树高
第13章 - 红黑树
- 红黑树的性质（自平衡）
- 旋转操作（左旋、右旋）
- 插入、删除操作详解
- 高度保证：O(log n)
第14章 - 数据结构的扩张
- 动态顺序统计量
- 如何扩张数据结构
- 区间树
Part IV: 高级设计与分析技术 (Advanced Design and Analysis Techniques)
第15章 - 动态规划
- Rod Cutting问题
- 矩阵链乘法
- 动态规划要素：最优子结构、重叠子问题
- 最长公共子序列（LCS）
- 最优二叉搜索树
第16章 - 贪心算法
- 活动选择问题
- 贪心策略要素：贪心选择性质、最优子结构
- Huffman编码
- 拟阵与贪心方法
第17章 - 摊还分析
- 聚合分析
- 会计方法
- 势能方法
- 动态表格的摊还分析
Part V: 高级数据结构 (Advanced Data Structures)
第18章 - B树
- B树的定义与性质
- B树的基本操作（查找、插入、删除）
- 应用于数据库和文件系统
第19章 - 斐波那契堆
- 斐波那契堆的结构
- 可合并堆操作
- decrease-key 和 delete 操作
- 最大度数的界限
第20章 - van Emde Boas树
- 原型结构
- 递归结构
- vEB树实现
- 时间复杂度：O(log log U)
第21章 - 不相交集合的数据结构
- 不相交集合操作
- 链表表示
- 不相交集合森林
- 按秩合并与路径压缩分析
Part VI: 图算法 (Graph Algorithms)
第22章 - 基本图算法
- 图的表示（邻接表、邻接矩阵）
- BFS（广度优先搜索）
- DFS（深度优先搜索）
- 拓扑排序
- 强连通分量
第23章 - 最小生成树
- 安全边概念
- Kruskal算法和Prim算法
- 逆图过程分析
第24章 - 单源最短路径
- Bellman-Ford算法（处理负权重）
- DAG中的最短路径
- Dijkstra算法（非负权重）
- 差分约束系统
第25章 - 全源最短路径
- 矩阵乘法方法
- Floyd-Warshall算法
- Johnson算法（稀疏图优化）
第26章 - 最大流
- 流网络与流性质
- Ford-Fulkerson方法
- 增广路径
- 最大流最小割定理
- Push-relabel算法
- 二分图最大匹配
Part VII: Selected Topics（选讲专题）
第27章 - 多线程算法
- 动态多线程基础
- 多线程矩阵乘法
- 多线程归并排序
- Work law、Span law
第28章 - 矩阵运算
- 线性方程组求解
- 矩阵求逆
- 对称正定矩阵与最小二乘
第29章 - 线性规划
- 标准形式与松弛形式
- 单纯形算法
- 对偶理论
- 初始基本可行解
第30章 - 多项式与FFT
- 多项式表示
- DFT与FFT
- 高效FFT实现
第31章 - 数论算法
- 模运算
- GCD与扩展GCD
- RSA公钥密码系统
- 素性测试（Miller-Rabin）
- 整数分解（Pollard’s rho）
第32章 - 字符串匹配
- 朴素算法
- Rabin-Karp算法
- 有限自动机匹配
- KMP算法
第33章 - 计算几何
- 线段性质
- 凸包算法
- 最近点对问题
第34章 - NP完全性
- 多项式时间
- NP完备性与归约
- NP完备性证明技巧
- 经典NP完全问题（顶点覆盖、旅行商、集合覆盖等）
第35章 - 近似算法
- 顶点覆盖问题的近似算法
- 旅行商问题的近似算法
- 集合覆盖问题的近似算法
- 随机化与线性规划舍入
Appendix: 数学背景
附录A - 求和 附录B - 集合等基础知识 附录C - 计数与概率 附录D - 矩阵
核心算法思想
1. 分治法 (Divide and Conquer)
- 将问题分解为若干规模更小的子问题
- 递归地解决子问题
- 合并子问题的解
- 典型应用：归并排序、快速排序、Strassen矩阵乘法
2. 动态规划 (Dynamic Programming)
- 适用于具有最优子结构和重叠子问题的情况
- 自底向上填表或带备忘录的自顶向下
- 典型应用：矩阵链乘法、最长公共子序列、背包问题
3. 贪心算法 (Greedy Algorithm)
- 每一步选择当前最优解
- 适用于具有贪心选择性质和最优子结构的问题
- 典型应用：Huffman编码、Prim/Kruskal最小生成树
4. 摊还分析 (Amortized Analysis)
- 分析数据结构操作的平均性能
- 聚合分析、会计方法、势能方法
- 典型应用：动态数组、红黑树操作
5. 随机化算法 (Randomized Algorithms)
- 引入随机性来避免最坏情况
- 随机化快排、随机化选择
- 概率分析估计期望性能
关键概念总结
| 概念 | 说明 |
|---|---|
| 渐进符号 | O、Ω、Θ用于分析算法的时间复杂度 |
| 递归式 | T(n) = aT(n/b) + f(n)，可用主方法求解 |
| 比较排序下界 | Ω(n log n) |
| 堆 | 完全二叉树，支持O(log n)插入和删除 |
| 红黑树 | 自平衡BST，操作时间O(log n) |
| 动态规划 | 最优子结构 + 重叠子问题 |
| 图遍历 | BFS和DFS是图算法的基础 |
| 最大流 | 增广路径、残量网络、最小割定理 |
| NP完全性 | 多项式时间归约、Cook-Levin定理 |
与其他知识的关联
- The C++ Programming Language 4th Edition - C++实现算法
- A Tour of C++ - Bjarne Stroustrup - C++标准库中的算法
- C++ Concurrency in Action 2nd Edition - 多线程算法实现
- 《Effective Modern C++》- 42条改善C++11与C++14的具体方法 - 高效算法实现技巧
- 深入理解计算机系统第2版-CS-APP - 底层系统与算法性能
可行动点
- 学习路径: 按章节顺序学习，Part I-III是基础，Part IV-VI是进阶
- 实践建议: 每个算法用C++或Python实现一遍，理解细节
- 习题练习: 重点完成未标注星号(*)的练习题
- 算法面试: 第2-9章、第22-26章是面试高频考点
- 深入研读: 第15章（动态规划）、第16章（贪心）、第34章（NP完全）需要反复理解
笔记摘要
本书全面覆盖了算法设计与分析的核心内容，从基础的排序、搜索到高级的图算法、线性规划、NP完全性理论。书中的每个算法都配有严谨的数学证明和详细的伪代码，是算法学习的经典教材。重点推荐读者掌握：分治法、动态规划、贪心算法、摊还分析、图遍历、最大流等核心思想。