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

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

---

introduction-to-algorithm-4th

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

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

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

简介

《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 矩阵基本性质