摘要: 算法导论第四版介绍

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在这里插入图片描述

本文介绍一下算法导论第四版。本书的第四版是去年出来的，新增了机器学习算法等内容，还是有不少更新的。本书完整下载链接如下：

第三版中文版以及习题答案，第四版英文版

本文首先简要介绍一下这本书，然后对目录做一些记录，以后有需要的时候可以快速找到需要的章节。

简介

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

本书将严谨性和全面性融为一体，深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。

全书各章自成体系，可以作为独立的学习单元。算法以伪代码的形式描述；说明和解释力求浅显易懂，不失深度和数学严谨性。

本书在 2012 年出了第三版，当时第3版的主要变化为：

新增了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
- (新增)33.3 Gradient descent
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 矩阵基本性质