知识库

算法导论——Introduction to Algorithms（第3版）

25分钟阅读

《算法导论》——Introduction to Algorithms（第3版）

CLRS — 算法领域的”圣经”。MIT Press 出版，四位作者均为算法领域顶尖学者（Rivest 为 RSA 共同发明人、图灵奖得主）。第三版 1313 页，涵盖算法设计与分析的完整知识体系，从基础到高级主题，兼具数学严谨性与工程实用性。

一、全书架构

全书分为 8 大部分 + 4 个数学附录，共 35 章。内容循序渐进：基础 → 排序 → 数据结构 → 设计技术 → 高级数据结构 → 图算法 → 精选主题 → 数学背景。

部分主题章节范围核心内容
I基础 Foundations第1-5章算法角色、插入排序、渐近分析、分治、概率分析
II排序与顺序统计第6-9章堆排序、快速排序、线性时间排序、顺序统计
III数据结构第10-14章栈/队列/链表、哈希表、二叉搜索树、红黑树、扩充数据结构
IV高级设计与分析技术第15-17章动态规划、贪心算法、摊还分析
V高级数据结构第18-21章B树、斐波那契堆、van Emde Boas树、不相交集合
VI图算法第22-26章基本图算法、最小生成树、最短路径、最大流
VII精选主题第27-35章多线程算法、矩阵运算、线性规划、FFT、数论算法、字符串匹配、计算几何、NP完全、近似算法
VIII数学背景（附录）附录A-D求和、集合/关系/函数/图/树、计数与概率、矩阵

二、核心内容详解

Part I — 基础（第1-5章）

第1章 算法在计算中的角色

  • 算法定义：将输入转化为输出的计算步骤序列
  • 算法作为技术：效率是软件的基础能力，即使硬件无限进步，算法效率仍决定问题可解边界
  • 典型问题：排序、最短路径、密码学、调度、优化

第2章 入门：插入排序

  • 插入排序：增量式算法，时间 Θ(n²)
  • 算法分析框架：RAM 模型、运行时间、最好/最坏/平均情况
  • 算法设计范式：增量法（插入排序）vs 分治法（归并排序）
  • 归并排序：分治 + 合并，时间 Θ(n log n)

第3章 函数增长

  • 渐近记号（核心概念）：
    • Θ 记号：渐近紧确界（上界+下界）——等价于”同阶”
    • O 记号：渐近上界——“不超过”
    • Ω 记号：渐近下界——“不少于”
    • o 记号 / ω 记号：非紧确的上界/下界
  • 标准函数：多项式、指数、对数、阶乘、多重对数

第4章 分治法

  • 分治三步：分解 → 解决 → 合并
  • 经典例子：
    • 最大子数组问题（股票买卖）
    • Strassen 矩阵乘法：将 O(n³) 降到 O(n
  • 递归式求解方法：
    1. 代入法（猜测 + 数学归纳证明）
    2. 递归树法（画出递归树估算代价）
    3. 主方法（Master Theorem）：T(n) = aT(n/b) + f(n)，三种情况比较 f(n) 与 n^(log_b a)

第5章 概率分析与随机算法

  • 雇用问题：平均代价分析
  • 指示随机变量（Indicator Random Variables）：强大的概率分析工具
  • 随机算法：随机排列、随机化快速排序
  • 概率分析 vs 随机算法：前者假设输入随机分布，后者主动引入随机性

Part II — 排序与顺序统计（第6-9章）

第6章 堆排序 Heapsort

  • 堆数据结构：完全二叉树，大顶堆 / 小顶堆
  • 基本操作：
    • MAX-HEAPIFY：维护堆性质，O(log n)
    • BUILD-MAX-HEAP：建堆，O(n)（关键：并非直观的 O(n log n)）
    • HEAPSORT：堆排序，O(n log n)，原地排序
  • 优先队列：堆的应用，支持 INSERT / MAXIMUM / EXTRACT-MAX / INCREASE-KEY

第7章 快速排序 Quicksort

  • 核心思想：分治 + 划分（Partition）
  • 性能分析：
    • 最坏情况：已排序输入 → O(n²)
    • 最好情况：平衡划分 → O(n log n)
    • 平均情况：接近最好情况
  • 随机化快速排序：随机选择主元，避免最坏情况
  • 与归并排序对比：快排原地排序、常数因子小，实际更快

第8章 线性时间排序

  • 排序下界：比较排序模型下，下界为 Ω(n log n)——归并/快排/堆排序都是最优的比较排序
  • 非比较排序（突破下界）：
    • 计数排序 Counting Sort：已知输入范围 [0,k]，时间 Θ(n+k)，稳定
    • 基数排序 Radix Sort：按位排序，d 位数时间 Θ(d(n+k))
    • 桶排序 Bucket Sort：假设输入均匀分布，平均 O(n)

第9章 中位数与顺序统计

  • 问题：找第 i 小的元素
  • 最小值/最大值：n-1 次比较
  • 同时找最大最小：⌈3n/2⌉ - 2 次比较（成对比较优化）
  • 随机选择算法：期望 O(n)，基于快速排序划分思想
  • 最坏情况线性时间选择：BFPRT 算法（五数中值法），确定性 O(n)

Part III — 数据结构（第10-14章）

第10章 基本数据结构

  • 栈（LIFO）、队列（FIFO）
  • 链表：单链表 / 双链表 / 循环链表
  • 指针与对象的实现：数组模拟指针
  • 有根树的表示：左孩子右兄弟表示法

第11章 哈希表 Hash Tables

  • 直接寻址表：U 不大时 O(1)
  • 哈希表：通过哈希函数 h(k) 将关键字映射到槽位
  • 哈希函数：
    • 除法散列：h(k) = k mod m
    • 乘法散列：h(k) = ⌊m(kA mod 1)⌋
    • 全域哈希：随机选择哈希函数，对抗最坏输入
  • 冲突解决：
    • 链接法（Chaining）：每个槽位一个链表
    • 开放寻址法 Open Addressing：线性探查 / 二次探查 / 双重散列
  • 完美哈希：静态集合上 O(1) 最坏情况查找

第12章 二叉搜索树 BST

  • BST 性质：左子树所有节点 ≤ 根 ≤ 右子树所有节点
  • 基本操作：查询（SEARCH / MINIMUM / MAXIMUM / SUCCESSOR / PREDECESSOR）、插入、删除
  • 随机构建的 BST：期望高度 O(log n)
  • 最坏情况：退化为链表 O(n)

第13章 红黑树 Red-Black Trees

  • 红黑性质（5条）：
    1. 每个节点红或黑
    2. 根节点黑
    3. 每个叶节点（NIL）黑
    4. 红节点的两个子节点都是黑的（不能有连续红节点）
    5. 从任一节点到其后代叶节点的所有路径包含相同数目的黑节点
  • 旋转操作：左旋 / 右旋，O(1)
  • 插入与删除：通过旋转 + 重新着色维持红黑性质，均为 O(log n)
  • 保证高度 O(log n)——最广泛使用的平衡 BST 之一

第14章 扩充数据结构

  • 思想：在基本数据结构上附加额外信息，支持更多操作
  • 动态顺序统计：在红黑树上维护子树大小，支持 O(log n) 排名查询与按秩选择
  • 扩充数据结构的四步法：
    1. 选择基础数据结构
    2. 确定附加信息
    3. 验证附加信息可在修改时高效维护
    4. 开发新操作
  • 区间树 Interval Tree：红黑树扩充，支持区间查询

Part IV — 高级设计与分析技术（第15-17章）

第15章 动态规划 Dynamic Programming

  • 适用条件：最优子结构 + 重叠子问题
  • 设计步骤：
    1. 刻画最优解结构
    2. 递归定义最优解值
    3. 自底向上计算最优解值
    4. 构造最优解
  • 经典问题：
    • 钢条切割：最简单的 DP 入门
    • 矩阵链乘法：加括号顺序，O(n³)
    • 最长公共子序列 LCS：O(mn)
    • 最优二叉搜索树
  • 实现方式：自顶向下带备忘（memoization）vs 自底向上（bottom-up）

第16章 贪心算法 Greedy Algorithms

  • 核心思想：每步做出局部最优选择，期望得到全局最优
  • 适用条件：最优子结构 + 贪心选择性质（局部最优→全局最优）
  • 经典问题：
    • 活动选择问题
    • Huffman 编码：最优前缀码
    • 拟阵 Matroid 与贪心方法的一般理论
  • 贪心 vs 动态规划：0-1背包（只能DP）vs 分数背包（可以贪心）

第17章 摊还分析 Amortized Analysis

  • 目的：分析一系列操作的平均代价（即使单个操作代价高）
  • 三种方法：
    1. 聚合分析：总代价 / n → 摊还代价
    2. 核算法 Accounting Method：给每个操作存”信用”，早期操作的信用支付后期高代价操作
    3. 势能法 Potential Method：定义势能函数 Φ，摊还代价 = 实际代价 + ΔΦ
  • 动态表：表扩容与缩容的摊还分析——插入摊还 O(1)

Part V — 高级数据结构（第18-21章）

第18章 B 树 B-Trees

  • 特点：多路平衡搜索树，为磁盘等辅助存储设计，降低 I/O 次数
  • 性质：每个节点最多 t 个孩子（t 为最小度数），所有叶子在同一层
  • 基本操作：查找、插入（分裂节点）、删除（合并/借位）
  • 应用：数据库索引、文件系统

第19章 斐波那契堆 Fibonacci Heaps

  • 理论上极优的数据结构：合并操作 O(1) 摊还
  • 操作代价对比：
    • MAKE-HEAP: O(1)
    • INSERT: O(1) 摊还
    • MINIMUM: O(1)
    • EXTRACT-MIN: O(log n) 摊还
    • UNION: O(1) 摊还 ← 关键优势
    • DECREASE-KEY: O(1) 摊还
  • 实际中常数因子大，使用较少，但理论意义重大

第20章 van Emde Boas 树

  • 适用于关键字在 {0, 1, …, u-1} 范围内的情况
  • 操作时间：O(log log u)，优于平衡树的 O(log n)
  • 递归结构：每层将问题规模缩小到平方根
  • 应用：IP 路由查找等

第21章 不相交集合 Data Structures for Disjoint Sets

  • 操作：MAKE-SET / UNION / FIND-SET
  • 表示：链表表示（低效）→ 不相交集合森林（高效）
  • 优化技巧：
    • 按秩合并 Union by Rank：小树合并到大树上
    • 路径压缩 Path Compression：查找时将节点直接指向根
  • 两个优化结合后，摊还时间接近常数：α(n)（阿克曼函数的反函数，增长极慢，实用中 ≤ 5）
  • 应用：Kruskal 最小生成树算法、连通分量

Part VI — 图算法（第22-26章）

第22章 基本图算法

  • 图的表示：邻接链表（稀疏图最优）/ 邻接矩阵（稠密图）
  • 广度优先搜索 BFS：
    • 从源节点出发，按层次遍历
    • 计算最短路径（无权图）
    • 时间 O(V + E)
  • 深度优先搜索 DFS：
    • 尽可能深入，回溯后继续
    • 发现时间 / 完成时间（括号化结构）
    • 边的分类：树边 / 回边 / 前向边 / 交叉边
    • 时间 O(V + E)
  • 拓扑排序：DAG 的线性序，基于 DFS
  • 强连通分量：Kosaraju 算法（两次 DFS）

第23章 最小生成树 MST

  • 问题：连接所有顶点的最小权值生成树
  • 通用策略：安全边（横跨割的最小权边）
  • Kruskal 算法：
    • 按权排序，依次加边，用不相交集合检测环
    • 时间 O(E log E)
  • Prim 算法：
    • 从一个顶点出发，每次加最小权连接边
    • 二叉堆实现 O(E log V)，斐波那契堆 O(E + V log V)

第24章 单源最短路径

  • 问题：从源点 s 到所有其他顶点的最短路径
  • 核心操作：松弛 Relaxation——d[v] = min(d[v], d[u] + w(u,v))
  • Bellman-Ford 算法：
    • 可处理负权边，可检测负权环
    • 时间 O(VE)
  • DAG 最短路径：拓扑排序后线性松弛，O(V + E)
  • Dijkstra 算法：
    • 贪心，要求非负权边
    • 二叉堆 O(E log V)，斐波那契堆 O(E + V log V)
  • 差分约束系统：线性不等式组 ↔ 最短路径问题

第25章 所有点对最短路径

  • 问题：每对顶点间的最短路径
  • 方法：
    • 矩阵乘法（动态规划）：O(V³ log V)
    • Floyd-Warshall 算法：
      • 三层循环，动态规划
      • 时间 Θ(V³)，允许负权边
      • 可检测负权环
    • Johnson 算法：
      • 重赋权 + Dijkstra
      • 稀疏图最优：O(V² log V + VE)

第26章 最大流 Maximum Flow

  • 问题：从源点到汇点的最大流量
  • 核心概念：残留网络、增广路径、割
  • Ford-Fulkerson 方法：不断找增广路径，时间 O(E |f*|)
  • Edmonds-Karp 算法：BFS 找增广路径，O(VE²)
  • 最大二分匹配：最大流的特殊情况
  • 推送-重贴标签算法：更高效，O(V²E)
  • 重贴标签前移算法：O(V³)
  • 最大流-最小割定理：最大流 = 最小割容量

Part VII — 精选主题（第27-35章）

第27章 多线程算法 Multithreaded Algorithms

  • 动态多线程模型：spawn / sync / parallel for
  • 性能度量：
    • 工作量 Work（T₁）：单处理器总时间
    • 持续时间 Span（T∞）：关键路径长度
    • 加速比：T₁ / T_P
    • 并行度：T₁ / T∞
  • 例子：多线程矩阵乘法、多线程归并排序
  • Greedy 调度器：任意 P 处理器下 T_P ≤ T₁/P + T∞

第28章 矩阵运算

  • 线性方程组求解：LU 分解
  • 矩阵求逆
  • 对称正定矩阵与最小二乘近似

第29章 线性规划 Linear Programming

  • 标准型 / 松弛型
  • 单纯形算法 Simplex：经典 LP 算法
  • 对偶理论 Duality：原问题 ↔ 对偶问题
  • 应用：最大流、多商品流、资源分配

第30章 多项式与 FFT

  • 多项式表示：系数表示 / 点值表示
  • 快速傅里叶变换 FFT：
    • 基于分治，利用单位复数根
    • 时间 O(n log n)
    • 应用：快速多项式乘法、信号处理
  • 高效 FFT 实现：Cooley-Tukey 算法

第31章 数论算法 Number-Theoretic Algorithms

  • 基础：模运算、GCD、中国剩余定理
  • 欧几里得算法：GCD，递归公式 gcd(a,b) = gcd(b, a mod b)
  • 扩展欧几里得：求模逆元
  • RSA 公钥密码系统：大素数乘积难以分解
  • 素性测试：Miller-Rabin 随机算法
  • 整数分解：Pollard’s rho 启发式

第32章 字符串匹配 String Matching

  • 朴素算法：O(nm)
  • Rabin-Karp 算法：滚动哈希，期望 O(n+m)
  • 有限自动机：基于状态转移，O(n) 匹配
  • KMP 算法：前缀函数避免回溯，O(n+m)

第33章 计算几何 Computational Geometry

  • 线段性质：叉积判断方向
  • 线段相交检测
  • 凸包 Convex Hull：Graham 扫描 / Jarvis 步进
  • 最近点对：分治法 O(n log n)

第34章 NP 完全性 NP-Completeness

  • P 类：多项式时间可解
  • NP 类：多项式时间可验证（给定证书可快速验证）
  • NPC 类：NP 中最难的问题，任何 NP 问题可多项式归约到它
  • 核心 NPC 问题：
    • 电路可满足性 CIRCUIT-SAT（第一个 NPC 问题，Cook 定理）
    • 合取范式可满足性 SAT / 3-CNF-SAT
    • 团问题 CLIQUE
    • 顶点覆盖 VERTEX-COVER
    • 哈密顿回路 HAM-CYCLE
    • 旅行商问题 TSP
    • 子集和 SUBSET-SUM
  • 证明 NPC 的方法：归约——已知 NPC 问题 → 目标问题

第35章 近似算法 Approximation Algorithms

  • 动机：NPC 问题难以精确求解，寻找多项式时间近似解
  • 近似比：近似解 / 最优解 的比值
  • 经典问题的近似算法：
    • 顶点覆盖：2-近似（匹配算法）
    • 旅行商问题：
      • 满足三角不等式：2-近似（MST + 前序遍历）
      • 一般情况：无常数近似比（除非 P=NP）
    • 集合覆盖：贪心 H(n)-近似（ln n 近似比）
    • 子集和：完全多项式时间近似模式 FPTAS

Part VIII — 数学背景（附录 A-D）

附录A 求和 Summations

  • 求和公式：等差、等比、调和级数等
  • 求和界估计：积分法、拆分法

附录B 集合、关系、函数、图、树

  • 集合运算、关系性质（自反/对称/传递）
  • 函数：单射 / 满射 / 双射
  • 图的基本概念、有根树

附录C 计数与概率

  • 计数原理、排列组合
  • 概率空间、条件概率、独立性
  • 离散随机变量、期望、方差
  • 几何分布、二项分布
  • Chernoff 界：尾概率估计

附录D 矩阵

  • 矩阵运算、逆矩阵、秩、行列式
  • 正定矩阵

三、关键思想与方法总结

1. 算法设计范式

范式核心思想典型应用
分治 Divide and Conquer分解→解决→合并归并排序、快速排序、Strassen矩阵乘法、FFT
动态规划 DP最优子结构+重叠子问题，记忆化避免重复计算钢条切割、LCS、矩阵链乘、Floyd-Warshall、0-1背包
贪心 Greedy每步局部最优→全局最优（需证明贪心选择性质）活动选择、Huffman编码、Kruskal/Prim、Dijkstra
随机化 Randomized引入随机性避免最坏情况随机快排、随机选择、全域哈希、Miller-Rabin
回溯 Backtracking深度搜索+剪枝N皇后、子集和（穷举型）
分支限界 Branch and Bound广度/最佳优先+上下界剪枝TSP、整数规划

2. 算法分析工具

  • 渐近记号：Θ / O / Ω / o / ω——描述增长阶
  • 递归式求解：代入法 / 递归树 / 主方法
  • 概率分析：指示随机变量、期望、Chernoff 界
  • 摊还分析：聚合法 / 核算法 / 势能法
  • 下界证明：比较排序的 Ω(n log n) 下界、敌手论证

3. 数据结构权衡

数据结构查找插入删除空间特点
数组O(n)O(n)O(n)O(n)随机访问 O(1)
链表O(n)O(1)*O(1)*O(n)*已知位置时
栈/队列-O(1)O(1)O(n)LIFO/FIFO
哈希表O(1)期望O(1)期望O(1)期望O(n)最坏 O(n)
BSTO(h)O(h)O(h)O(n)h=高度，最坏O(n)
红黑树O(log n)O(log n)O(log n)O(n)平衡BST
B树O(log_t n)O(log_t n)O(log_t n)O(n)磁盘友好
堆O(1)最值O(log n)O(log n)O(n)优先队列
不相交集α(n)α(n)-O(n)α≈常数

4. 图算法速查

问题算法时间复杂度约束
最短路径（无权）BFSO(V+E)无权
单源最短路径DijkstraO(E log V)非负权
单源最短路径Bellman-FordO(VE)允许负权，检测负环
DAG最短路径拓扑排序+松弛O(V+E)DAG
所有点对最短路径Floyd-WarshallO(V³)允许负权
所有点对最短路径JohnsonO(V² log V + VE)稀疏图最优
最小生成树KruskalO(E log E)-
最小生成树PrimO(E log V)-
最大流Edmonds-KarpO(VE²)-
最大流Push-RelabelO(V²E)稠密图更优
二分匹配最大流规约O(VE)-

5. NP 完全问题谱系

CIRCUIT-SAT → SAT → 3-CNF-SAT
                 ↓
              CLIQUE ←→ VERTEX-COVER ←→ HAM-CYCLE → TSP
                 ↓
           SET-COVER → SUBSET-SUM

所有 NPC 问题在多项式时间归约下等价——一个有多项式解，则全部有。

四、第三版新增内容

相比第二版，第三版主要更新：

  1. 新增多线程算法章节（第27章）——反映多核时代需求
  2. ** van Emde Boas 树**独立成章（原散见于习题）
  3. 动态规划章节增加最优二叉搜索树
  4. 红黑树删除算法重写，更清晰
  5. 伪代码更简洁，写作风格更主动
  6. 新增/修订大量习题

五、学习建议

  1. 渐进学习：先掌握 Part I-II（基础+排序），这是所有算法课的核心
  2. 动手实现：每个关键算法至少实现一次——光看不够
  3. 做习题：CLRS 的习题质量极高，特别是带 ⋆ 的难题
  4. 掌握证明：算法不仅要会用，更要理解为什么正确、为什么高效
  5. 建立直觉：理解每种算法/数据结构解决什么问题、为什么这样设计
  6. 对比学习：同类问题的多种解法放在一起比较（排序算法对比、最短路径算法对比）

六、相关链接

本书是算法领域最权威、最全面的教材，MIT、斯坦福等顶尖高校算法课的标准教材。建议作为案头书常备，遇到算法问题时查阅。

关系图谱

反向链接