# 算法导论第四版

|

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】

# 简介

《Introduction to Algorithm》是由 Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein 编写，MIT 出版的一本介绍、分析当代计算机算法的图书。一般用四位作者姓的首字母组成的 CLRS 代表此书。

• 新增了van Emde Boas树和多线程算法，并且将矩阵基础移至附录。
• 修订了递归式（现在称为“分治策略”）那一章的内容，更广泛地覆盖分治法。
• 移除两章很少讲授的内容：二项堆和排序网络。
• 修订了动态规划和贪心算法相关内容。
• 流网络相关材料现在基于边上的全部流。
• 由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容所占篇幅更小。
• 修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。
• 新增100道练习和28道思考题，还更新并补充了参考文献。

# 第四版中被删除的第三版内容

• Fibonacci heaps(第3版 $19) • van Emde Boas trees(第3版$20)
• computational geometry(第3版 $33) • the maximum-subarray problem • implementing pointers and objects(第3版$10-3)
• perfect hashing(第3版 $11-5) • randomly built binary search trees(第3版$12-4)
• matroids(第3版 $15-4) • push-relabel algorithms for maximum flow(第3版$26-4)
• the iterative fast Fourier transform method
• the details of the simplex algorithm for linear programming(第3版 \$29-3)
• integer factorization

# 第四版中更新的第三版内容和新增内容

• Chap3:
• giving an overview of asymptotic notation before delving into the formal definitions
• Chap4:
• underwent substantial changes to improve its mathematical foundation and make it more robust and intuitive.
• The notion of an algorithmic recurrence was introduced
• the topic of ignoring floors and ceilings in recurrences was addressed more rigorously
• The second case of the master theorem incorporates polylogarithmic factors
• a rigorous proof of a “continuous” version of the master theorem is now provided
• present the powerful and general Akra-Bazzi method (without proof).
• Chap9:
• The deterministic order-statistic algorithm is slightly different
• the analyses of both the randomized and deterministic order-statistic algorithms have been revamped.
• Chap10:
• In addition to stacks and queues, discusses ways to store arrays and matrices.
• Chap11:
• a modern treatment of hash functions
• linear probing as an efficient method for resolving collisions when the underlying hardware implements caching to favor local searches.
• Chap15:
• To offline caching into a full section.
• Chap16:
• a more intuitive explanation of the potential functions to analyze table doubling and halving.
• Chap17:
• augmenting data structures was relocated from Part III to Part V.
• Chap25:
• a new chapter about matchings in bipartite graphs.
• It presents algorithms to find a matching of maximum cardinality
• solve the stable-marriage problem
• find a maximum-weight matching (known as the “assignment problem”).
• Chap26:
• task-parallel computing has been updated with modern terminology
• Chap27:
• online algorithms, is another new chapter.
• In an online algorithm, the input arrives over time, rather than being available in its entirety at the start of the algorithm.
• describes several examples of online algorithms
• determining how long to wait for an elevator before taking the stairs
• maintaining a linked list via the move-to-front heuristic
• evaluating replacement policies for caches.
• Chap29:
• we removed the detailed presentation of the simplex algorithm, as it was math heavy without really conveying many algorithmic ideas.
• The chapter now focuses on the key aspect of how to model problems as linear programs
• the essential duality property of linear programming.
• chap32:
• adds structure of suffix arrays.
• Chap33:
• machine learning, is the third new chapter.
• several basic methods used in machine learning:
• clustering to group similar items together
• weighted-majority algorithms
• gradient descent to find the minimizer of a function
• Chap34:
• summarizes strategies for reductions to show that problems are NP-hard.
• Chap35:
• polynomial-time The proof of the approximation algorithm for the set-covering problem.

# Part1 基础知识

• 1 算法在计算中的作用
• 2 算法基础
• 2.1 插入排序
• 2.2 分析算法
• 2.3 设计算法
• 2.3.1 分治法
• 2.3.2 分析分治算法
• 3 函数的增长
• 3.1 渐近记号
• 3.2 标准记号与常用函数
• 4 分治策略
• 4.1 最大子数组问题
• 4.2 矩阵乘法的Strasse
• 4.3 用代入法求解递归式
• 4.4 用递归树方法求解递归式
• 4.5 用主方法求解递归式
• 4.6 证明主定理
• 4.6.1 对b的幂证明主定理
• 4.6.2 向下取整和向
• (新增)4.7 Akra-Bazzi recurrences
• 5 概率分析和随机算法
• 5.1 雇用问题
• 5.2 指示器随机变量
• 5.3 随机算法
• 5.4 概率分析和指示器随机变量的进一步使用
• 5.4.1 生日悖论
• 5.4.2 球与箱子
• 5.4.3 特征序列
• 5.4.4 在线雇用问题

# Part2 排序和顺序统计量

• 6 堆排序
• 6.1 堆
• 6.2 维护堆的性质
• 6.3 建堆
• 6.4 堆排序算法
• 6.5 优先队列
• 7 快速排序
• 7.1 快速排序的描述
• 7.2 快速排序的性能
• 7.3 快速排序的随机化
• 7.4 快速排序分析
• 7.4.1 最坏情况分析
• 7.4.2 期望运行时间
• 8 线性时间排序
• 8.1 排序算法的下界
• 8.2 计数排序
• 8.3 基数排序
• 8.4 桶排序
• 9 中位数和顺序统计量
• 9.1 最小值和最大值
• 9.2 期望为线性时间的选择算法
• 9.3 最坏情况为线性时间的选择算法

# Part3 数据结构

• 10 基本数据结构
• 10.1 栈和队列
• 10.2 链表
• 10.3 有根树的表示
• 11 散列表
• 11.1 直接寻址表
• 11.2 散列表
• 11.3 散列函数
• 11.3.1 除法散列法
• 11.3.2 乘法散列法
• 11.3.3 全域散列法
• 11.4 开放寻址法
• (新增)11.5 Practical considerations
• 12 二叉搜索树
• 12.1 什么是二叉搜索树
• 12.2 查询二叉搜索树
• 12.3 插入和删除
• 13 红黑树
• 13.1 红黑树的性质
• 13.2 旋转
• 13.3 插入
• 13.4 删除

# Part4 高级设计和分析技术

• 14 动态规划
• 14.1 钢条切割
• 14.2 矩阵链乘法
• 14.3 动态规划原理
• 14.4 最长公共子序列
• 14.5 最优二叉搜索树
• 15 贪心算法
• 15.1 活动选择问题
• 15.2 贪心算法原理
• 15.3 赫夫曼编码
• (新增)15.4 Offline caching
• 16 摊还分析
• 16.1 聚合分析
• 16.2 核算法
• 16.3 势能法
• 16.4 动态表
• 16.4.1 表扩张
• 16.4.2 表扩张和收缩

# Part5 高级数据结构

• 17 数据结构的扩张
• 17.1 动态顺序统计
• 17.2 如何扩张数据结构
• 17.3 区间树
• 18 B树
• 18.1 B树的定义
• 18.2 B树上的基本操作
• 18.3 从B树中删除关键字
• 19 用于不相交集合的数据结构
• 19.1 不相交集合的操作
• 19.2 不相交集合的链表表示
• 19.3 不相交集合森林
• 19.4 带路径压缩的按秩合并的分析

# Part6 图算法

• 20 基本的图算法
• 20.1 图的表示
• 20.2 广度优先搜索
• 20.3 深度优先搜索
• 20.4 拓扑排序
• 20.5 强连通分量
• 21 最小生成树
• 21.1 最小生成树的形成
• 21.2 Kruskal算法和Prim算法
• 22 单源最短路径
• 22.1 Bellman-Ford算法
• 22.2 有向无环图中的单源最短路径问题
• 22.3 Dijkstra算法
• 22.4 差分约束和最短路径
• 22.5 最短路径性质的证明
• 23 所有结点对的最短路径问题
• 23.1 最短路径和矩阵乘法
• 23.2 Floyd-Warshall算法
• 23.3 用于稀疏图的Johnson算法
• 24 最大流
• 24.1 流网络
• 24.2 Ford-Fulkerson方法
• 24.3 最大二分匹配
• (新增)25 Matchings in Bipartite Graphs
• (新增)25.1 Maximum bipartite matching (revisited)
• (新增)25.2 The stable-marriage problem
• (新增)25.3 The Hungarian algorithm for the assignment problem

# Part7 专题

• 26 多线程算法
• 26.1 动态多线程基础
• 26.2 多线程矩阵乘法
• 26.3 多线程归并排序
• (新增)27 Online Algorithms
• (新增)27.1 Waiting for an elevator
• (新增)27.2 Maintaining a search list
• (新增)27.3 Online caching
• 28 矩阵运算
• 28.1 求解线性方程组
• 28.2 矩阵求逆
• 28.3 对称正定矩阵和最小二乘逼近
• 29 线性规划
• 29.1 标准型和松弛型
• 29.2 将问题表达为线性规划
• 29.3 对偶性
• 30 多项式与快速傅里叶变换
• 30.1 多项式的表示
• 30.2 DFT与FFT
• 30.3 高效FFT实现
• 31 数论算法
• 31.1 基础数论概念
• 31.2 最大公约数
• 31.3 模运算
• 31.4 求解模线性方程
• 31.5 中国余数定理
• 31.6 元素的幂
• 31.7 RSA公钥加密系统
• 31.8 素数的测试
• (新增)31.9 整数的因子分解
• 32 字符串匹配
• 32.1 朴素字符串匹配算法
• 32.2 Rabin-Karp算法
• 32.3 利用有限自动机进行字符串匹配
• 32.4 Knuth-Morris-Pratt算法
• (新增)32.5 Suffix arrays
• (新增)33 Machine-Learning Algorithms
• (新增)33.1 Clustering
• (新增)33.2 Multiplicative-weights algorithms
• 34 NP完全性
• 34.1 多项式时间
• 34.2 多项式时间的验证
• 34.3 NP完全性与可归约性
• 34.4 NP完全性的证明
• 34.5 NP完全问题
• 34.5.1 团问题
• 34.5.2 顶点覆盖问题
• 34.5.3 哈密顿回路问题
• 34.5.4 旅行商问题
• 34.5.5 子集和问题
• 35 近似算法
• 35.1 顶点覆盖问题
• 35.2 旅行商问题
• 35.2.1 满足三角不等式的旅行商问题
• 35.2.2 一般旅行商问题
• 35.3 集合覆盖问题
• 35.4 随机化和线性规划
• 35.5 子集和问题

# Part8 附录：数学基础知识

• A 求和
• A.1 求和公式及其性质
• A.2 确定求和时间的界
• B 集合等离散数学内容
• B.1 集合
• B.2 关系
• B.3 函数
• B.4 图
• B.5 树
• B.5.1 自由树
• B.5.2 有根树和有序树
• B.5.3 二叉树和位置树
• C 计数与概率
• C.1 计数
• C.2 概率
• C.3 离散随机变量
• C.4 几何分布与二项分布
• C.5 二项分布的尾部
• D 矩阵
• D.1 矩阵与矩阵运算
• D.2 矩阵基本性质

Share