20260826 153418 算法导论学习要点全 35 章

《算法导论》学习要点（全 35 章）¶

本讲义以 CLRS《算法导论》（Introduction to Algorithms，第四版）为基础，按章节提取核心学习要点，帮助学习者系统掌握算法设计与分析的完整知识体系。

教学建议：建议按”基础（1–9）→ 数据结构（10–19）→ 图算法（20–25）→ 高级专题（26–31）→ 应用与前沿（32–35）”的顺序学习；每章先掌握核心概念与算法流程，再理解正确性证明与复杂度分析，最后通过习题巩固。

目录 ¶

第一部分基础（第 1–5 章）¶

第 1 章算法在计算中的作用
第 2 章起步（插入排序与分治法入门）
第 3 章刻画运行时间（渐近记号）
第 4 章分治策略与递归式求解
第 5 章概率分析与随机化算法

第二部分排序与顺序统计（第 6–9 章）¶

第 6 章堆排序
第 7 章快速排序
第 8 章线性时间排序
第 9 章中位数与顺序统计

第三部分数据结构（第 10–13 章）¶

第 10 章基本数据结构
第 11 章散列表
第 12 章二叉搜索树
第 13 章红黑树

第四部分高级设计与分析技术（第 14–19 章）¶

第 14 章动态规划
第 15 章贪心算法
第 16 章摊还分析
第 17 章扩充的数据结构
第 18 章 B 树
第 19 章用于不相交集合的数据结构

第五部分图算法（第 20–25 章）¶

第 20 章基本的图算法
第 21 章最小生成树
第 22 章单源最短路径
第 23 章所有结点对的最短路径
第 24 章最大流
第 25 章二分图中的匹配

第六部分高级专题（第 26–31 章）¶

第 26 章并行算法
第 27 章在线算法
第 28 章矩阵运算
第 29 章线性规划
第 30 章多项式与快速傅里叶变换（FFT）
第 31 章数论算法

第七部分应用与前沿（第 32–35 章）¶

第 32 章字符串匹配
第 33 章机器学习算法
第 34 章 NP 完全性
第 35 章近似算法

第一部分：基础（第 1–5 章）¶

第 1 章算法在计算中的作用（The Role of Algorithms in Computing）¶

教学目标 ¶

理解算法的严格定义、正确性概念及其在计算中的核心地位
建立”算法即技术”的价值观，理解效率的重要性

核心学习要点 ¶

1. 算法的定义与正确性 ¶

算法：任何良定义的（well-defined）计算过程，以某个值或值的集合作为输入，在有限时间内产生输出；是”将输入变换为输出”的计算步骤序列。
问题实例（instance）：问题陈述规定了期望的输入/输出关系，一个具体输入即为一个实例。
正确算法：对每一个输入实例，在有限时间内停机并输出正确解。不正确的算法有时也有用（如可控制错误率的随机算法，第 31 章的素性测试），但通常只研究正确算法。
排序问题示例：输入 n 个数的序列，输出非递减排列——引出全书的第一个经典问题。

算法解决的实际问题类别：
- 大规模数据处理（人类基因组计划、搜索引擎）
- 路由与网络（最短路径，第 22 章）
- 信息安全（公钥密码学与数字签名，第 31 章）
- 资源配置（线性规划，第 29 章）
- 图像识别（聚类，第 33 章）
- 数据压缩（Huffman 编码，第 15 章）

1.2 算法作为一种技术 ¶

效率：算法的增长速率（order of growth）决定了其在大输入下的可用性；硬件速度无法替代渐近效率。
算法与其他技术的关系：与快速硬件、GUI、面向对象系统、网络等技术并列，是计算的核心技术之一。

1.3 困难问题与模型 ¶

并非所有问题都有高效算法：有些问题（如 NP 完全问题，第 34 章）很可能不存在多项式时间算法。
并行计算（第 26 章）、量子计算等替代计算模型可能改变效率的图景。

必须掌握的关键词 ¶

算法、问题实例、正确性、输入/输出规格、增长速率、困难问题、数据结构、算法设计技术、计算模型

第 2 章起步：插入排序与归并排序（Getting Started）¶

教学目标 ¶

掌握插入排序（增量法）与归并排序（分治法）两个入门算法
学会用循环不变式证明算法正确性
理解算法分析的基本框架：最坏情形、平均情形、增长阶

2.1 插入排序 ¶

算法思想：增量式（incremental）——每次将一个元素插入到已排序子序列的正确位置，类似整理扑克牌。
伪代码约定：缩进表示块结构、数组下标从 1 开始、for/while/repeat 循环、A.length 等，需熟悉本书伪代码风格。
循环不变式（loop invariant）证明三要素：
1. 初始化：循环开始前不变式为真；
2. 保持：若某次迭代前为真，则迭代后仍为真；
3. 终止：循环终止时，不变式提供有用性质以证明算法正确。
对插入排序：每次迭代开始时，子数组 A[0..j-1] 已有序（其中包含原 A[0..j-1] 的元素）。
复杂度：最好 Θ(n)（已有序），最坏 Θ(n²)，平均 Θ(n²)。

2.2 分析算法 ¶

RAM 模型：随机存取机——单处理器、顺序执行、每条指令代价为常数；对算法分析是合适的抽象。
输入规模：多数问题为输入项的数目 n；也可用位数或二进制表示长度。
运行时间：基本操作步数；通常关注最坏情形运行时间 T(n)（保证上界、常出现）。
平均情形：对输入分布做假设（如等可能）；期望运行时间。
增长阶（order of growth）：忽略常数因子与低阶项，只关注主导项，如 Θ(n²) 表示运行时间随 n² 增长。

2.3 设计算法：分治策略 ¶

分治法三步骤：分解（Divide）→ 解决（Conquer，递归求解子问题）→ 合并（Combine）。
归并排序（merge sort）：分解为两个规模 n/2 的子数组，递归排序，线性时间合并（MERGE 过程，借助哨兵）。
归并排序运行时间：递归式 T(n) = 2T(n/2) + Θ(n)，解为 Θ(n log n)。
归并排序与插入排序的对比：n 很大时，Θ(n log n) 显著优于 Θ(n²)。

本章必须掌握 ¶

循环不变式、正确性证明、最坏情形与平均情形、增长阶、增量法 vs 分治法、插入排序、归并排序、MERGE 过程

第 3 章刻画运行时间（Characterizing Running Times）¶

教学目标 ¶

精确定义五大渐近记号（O、Ω、Θ、o、ω）
掌握渐近记号的运算性质与常用数学函数

3.1 渐近记号（非正式理解）¶

Θ-notation（渐近紧确界）：f(n) = Θ(g(n)) 表示 f 被 c₁g(n) 与 c₂g(n) 上下夹住（n ≥ n₀）。
O-notation（渐近上界）：f(n) = O(g(n)) 表示 f 不超过 c·g(n)（最多差常数因子）。
Ω-notation（渐近下界）：f(n) = Ω(g(n)) 表示 f 至少为 c·g(n)。
例：插入排序最坏情形运行时间 T(n) = Θ(n²)，但作为一般上界写作 O(n²)；所有情况均为 Ω(n)。

3.2 形式化定义与性质 ¶

精确数学定义（存在正常数 c、n₀ 使不等式对所有 n ≥ n₀ 成立）。
o-notation（非紧上界）与 ω-notation（非紧下界）：类比 < 与 ≤ 的区别；如 2n = o(n²) 但 n² ≠ o(n²)。
渐近记号间的关系：f = Θ(g) ⇔ f = O(g) 且 f = Ω(g)（类比 f = g 与 f ≤ g、f ≥ g）。
运算性质：传递性、自反性、对称性（仅 Θ）；渐近记号用于等式中的含义（= 为”是”关系；等式右边存在某函数属于左侧集合）。

3.3 标准记号与常用函数 ¶

单调性、下取整 ⌊x⌋ 与上取整 ⌈x⌉ 的性质。
模运算：a mod n。
多项式：P(n) 为 d 次多项式 ⇒ P(n) = Θ(n^d)。
指数：所有底数 a>1 的指数函数增长都快于任何多项式。
对数：对数函数增长慢于任何正幂多项式；换底公式；lg、ln 记号。
阶乘 n!：n! = ω(2ⁿ)，n! = o(nⁿ)；斯特林近似 n! ≈ √(2πn)(n/e)ⁿ。
函数迭代 f⁽ᵏ⁾(n) 与重对数函数 lg* n（lg* n = min{i ≥ 0 : lg⁽ⁱ⁾ n ≤ 1}）。
斐波那契数：F₀=0, F₁=1，Fₙ = Fₙ₋₁+Fₙ₋₂，与黄金比例 φ 的关系 Fₙ = φⁿ/√5（取整）。

本章小结 ¶

五个渐近记号的定义与关系、渐近记号在等式中的使用约定、常用数学函数及其增长速率排序、迭代对数、斐波那契数

第 4 章分治策略（Divide-and-Conquer）¶

教学目标 ¶

深入理解分治法，掌握三个例子：矩阵乘法（Strassen）、以及一般的递归式求解
熟练掌握三种求解递归式的方法：代换法、递归树法、主方法
进阶：Akra-Bazzi 方法

4.0 递归式基础 ¶

递归式（recurrence）：用更小规模自身描述运行时间的等式，如 T(n) = 2T(n/2) + Θ(n)。
分治递归式的一般形式：T(n) = aT(n/b) + f(n)（a 个子问题，规模 n/b，分解与合并代价 f(n)）。
关于边界条件、取整、技术细节的约定（可忽略 floor/ceil，通常不影响渐近界）。

4.1 矩阵乘法的分治算法 ¶

朴素分治：8 次 n/2 规模乘法，递归式 T(n) = 8T(n/2) + Θ(n²)，解为 Θ(n³)——与朴素三重循环相同。
说明简单的分治不一定更优，但为 Strassen 奠定基础。

4.2 Strassen 算法 ¶

核心思想：用 7 次递归乘法（而非 8 次）加 O(n²) 次加减法完成 2×2 矩阵乘法。
递归式 T(n) = 7T(n/2) + Θ(n²)，解为 Θ(n^lg7) ≈ Θ(n^2.81)。
是超越 Θ(n³) 的第一个矩阵乘法；需了解其 7 个辅助矩阵的定义与”不进则退”的常数开销（实际中通常只在 n 很大时采用）。

4.3 代换法（substitution method）¶

两步：猜测形式（如 T(n) = O(n log n)），归纳证明。
技巧：猜测时”减掉一个低阶项”（如 cn log n − dn）以规避归纳证明中的余项；
常见陷阱：错误猜测（过大/过小）、忽略渐近记号中的常数（须严格证明 T(n) ≤ cn log n）。
变量代换（如 n = 2^m 将 T(2^m) 化为 S(m)）也属于该法的变形。

4.4 递归树法（recursion-tree method）¶

把递归展开为树：每层代价相加，总代价 = 各层代价之和。
适用于产生猜测，再经代换法验证（树法本身不算严格证明，但直观）。
例子：T(n) = 3T(n/4) + Θ(n²) 的递归树——每层代价递减为等比，根为支配项。

4.5 主方法（master method）¶

主定理：若 T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1，f(n) 为渐进正函数，则：
1. 若 f(n) = O(n^{log_b a − ε})（n^ε）则 T(n) = Θ(n^{log_b a})；
2. 若 f(n) = Θ(n^{log_b a}) 则 T(n) = Θ(n^{log_b a} log n)；
3. 若 f(n) = Ω(n^{log_b a + ε}) 且存在 c<1 使 a f(n/b) ≤ c f(n)（正则条件），则 T(n) = Θ(f(n))。
三种情况反映：叶子代价支配、每层代价相等、根代价支配。
注意主方法不适用的情形（如 f(n)/n^{log_b a} 不在多项式差距：如 f(n) = n log n 与 log_b a = 1）。

★ 4.6–4.7 进阶 ¶

连续主定理（continuous master theorem）及其证明思路（积分形式）。
Akra-Bazzi 方法：处理 T(n) = Σ aᵢ T(bᵢ n) + f(n) 这类更一般的递归式，结果为 Θ(n^p (1 + ∫₀ⁿ f(x)/x^{p+1} dx))，其中 p 满足 Σ aᵢ bᵢ^p = 1。

本章小结 ¶

分治范式、矩阵乘法（朴素 vs Strassen）、递归式、代换法、递归树、主定理及其适用条件、Akra-Bazzi

第 5 章概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）¶

教学目标 ¶

区分最坏情形分析、概率分析与随机化算法
掌握指示器随机变量（indicator random variable）这一核心分析工具
通过招聘问题、生日悖论、球与盒子、掷硬币等经典例子建立概率直觉

5.1 招聘问题（the hiring problem）¶

问题描述：依次面试 n 个候选人，每次招”截至目前最好”者，成本 = 面试费 + 聘请费。
最坏情形分析：候选人按质量递增排列时，招聘 n 次，总代价 O(cₕ·n)。
概率分析：假设候选人出现顺序随机（n! 等可能），用指示变量求期望招聘次数。
随机化算法：先随机排列候选人（RANDOMIZED-HIRE-ASSISTANT），使输入分布无关——把”分布假设”从输入移到算法内部，避免”恶意输入”造成的坏情形。

5.2 指示器随机变量 ¶

定义：I{A} = 1 若事件 A 发生，否则 0；E[I{A}] = Pr{A}。
期望的线性性：E[X₁+…+Xₙ] = E[X₁]+…+E[Xₙ]（不要求独立性）——这是概率分析中最强大的工具。
应用：招聘问题期望招聘次数 = Σ 1/k = ln n + O(1)（第 k 个候选人被聘的概率为 1/k）。

5.3 随机化算法设计 ¶

随机置换数组的两种方法：给每个元素赋随机优先级后排序（PERMUTE-BY-SORTING）；原地随机置换（SWAP 逐个交换，RANDOMIZED 版本，可证明为均匀分布）。
随机化排序的效益：使期望运行时间与输入无关（为后续快速排序的随机化铺路）。

5.4 进一步的概率分析应用 ¶

生日悖论：m 个人中至少两人同生日概率 ≥ 1/2 时 m ≈ √(2n ln 2) ≈ 23（n=365）。用指示器变量求期望同生日对数 ≈ m(m−1)/(2n)。
球与盒子（balls and bins）：n 个球随机放入 n 个盒子，期望最大负载 ≈ (ln n)/(ln ln n)（Chernoff 界相关直觉）；空盒子期望数 n(1−1/n)ⁿ ≈ n/e。
抛硬币连续（streaks）：n 次硬币中连续正面最长的期望为 Θ(log n)（分块分析 + 指示变量）。
在线招聘问题：先拒绝前 k 个观察，再从 k+1 开始选第一个比观察期更好的人；最优 k ≈ n/e，成功概率约 1/e（秘书问题的变体）。

本章小结 ¶

概率分析 vs 随机化算法、指示器随机变量与线性期望、随机置换、生日悖论、球与盒子、连续与在线招聘，为后续随机化算法（快排、随机选择）与哈希分析打基础

第二部分：排序与顺序统计（第 6–9 章）¶

第 6 章堆排序（Heapsort）¶

教学目标 ¶

掌握堆（优先队列）数据结构及其基本操作
理解堆排序算法与复杂度 Θ(n log n)
理解堆如何作为优先队列使用

6.1 堆 ¶

堆：近完全二叉树（所有层除最后一层外满，最后一层从左到右填充），用数组表示：PARENT(i)=⌊i/2⌋, LEFT(i)=2i, RIGHT(i)=2i+1。
最大堆性质：A[PARENT(i)] ≥ A[i]；最小堆反之。
堆高度：Θ(log n)；堆上的基本操作代价与高度成正比。

6.2 维护堆性质：MAX-HEAPIFY ¶

输入：下标 i，假设左右子树已是最大堆；将 A[i] 与较大孩子交换并逐层下沉。
运行时间：T(n) ≤ T(2n/3) + Θ(1) = O(log n)（最坏情形为树高）。

6.3 建堆（BUILD-MAX-HEAP）¶

自底向上对 i = ⌊n/2⌋ 到 1 依次调用 MAX-HEAPIFY。
复杂度：各结点高度求和，O(n)（非 O(n log n)）——关键洞察：大多数结点高度很小。

6.4 堆排序（HEAPSORT）¶

流程：建堆 → 反复将 A[1]（最大值）与末尾交换、堆规模减 1、MAX-HEAPIFY(1)。
复杂度：O(n log n)，原地排序（in-place）。

6.5 优先队列 ¶

优先队列 = 支持插入、取最大/最小、增大/减小关键字、删除的堆应用。
操作：MAXIMUM（O(1)）、EXTRACT-MAX（O(log n)）、INCREASE-KEY（O(log n)）、INSERT（O(log n)）。
应用：事件模拟、任务调度、图算法（Dijkstra、Prim 等后续章节用到）。

本章小结 ¶

数组表示的二叉堆、MAX-HEAPIFY、BUILD-MAX-HEAP 的 O(n) 建堆、堆排序、优先队列；习题延伸：d 叉堆、Young 矩阵

第 7 章快速排序（Quicksort）¶

教学目标 ¶

掌握快速排序的分治思想与划分过程
理解其最坏/期望运行时间的分析与随机化版本的必要性

7.1 算法描述 ¶

分治：选主元（pivot，通常取 A[r]）→ PARTITION 将数组划分为”≤pivot”与”>pivot”两段 → 递归排序两段。
PARTITION 过程：一趟扫描，维护两个区间的指示器，将所有 ≤ x 的元素放到左侧；返回主元最终位置。
原地划分（in-place）是快排优势之一；不稳定但常数因子小。

7.2 性能分析 ¶

最坏情形：每次划分极端不平衡（如已有序输入取端点为 pivot），T(n) = T(n−1) + Θ(n) = Θ(n²)。
最佳情形：每次划分恰好 n/2 对半分，T(n) = 2T(n/2) + Θ(n) = Θ(n log n)。
平衡划分：即使 9:1 划分，递归树仍为 Θ(n log n)——常数比例划分即可达到 Θ(n log n)。
平均情形直觉：好的划分与坏的划分交替时，好划分主导，期望 Θ(n log n)。

7.3 随机化版本（RANDOMIZED-PARTITION）¶

随机选 pivot：使任何输入下期望运行时间为 Θ(n log n)，消除对输入分布/恶意输入的依赖。

7.4 严格分析 ¶

最坏情形 T(n) = Θ(n²)。
期望运行时间：通过指示器随机变量与比较次数计数，对每次划分中比较总次数求期望。
若按元素值排名的顺序 z₁,…,zₙ，定义 Xᵢⱼ 表示 zᵢ 与 zⱼ 是否被比较；Pr{zᵢ 与 zⱼ 比较} = 2/(j−i+1)。
E[总比较次数] = Σ 2/(j−i+1) = O(n log n)。
结论：快速排序期望 O(n log n)，常数小、原地、缓存友好，实际中常优于堆排序。

本章小结 ¶

划分过程、最坏/最佳/期望分析、随机化 pivot、比较计数法证明期望 O(n log n)；习题涉及 Hoare 划分、三数取中、栈深度优化（尾递归）等工程细节

第 8 章线性时间排序（Sorting in Linear Time）¶

教学目标 ¶

证明比较排序的下界 Ω(n log n)
掌握三种线性时间排序：计数排序、基数排序、桶排序（以及各自适用条件）

8.1 比较排序下界 ¶

决策树模型：每次比较一个分支，任何基于比较的排序算法对应一棵决策树；n! 个叶子 ⇒ 树高 ≥ ⌈lg(n!)⌉。
定理 8.1：任何比较排序在最坏情况下需要 Ω(n log n) 次比较（利用斯特林公式 lg(n!) = Θ(n log n)）。
结论：归并排序、堆排序的 O(n log n) 是渐近最优的比较排序。

8.2 计数排序（counting sort）¶

适用：元素为 0 到 k 范围内的小整数；不是比较排序，稳定（stable）。
思想：统计每个值的出现次数（C 数组）→ 前缀和 → 从后向前按稳定方式填入输出。
复杂度：O(n + k)；若 k = O(n) 则为 O(n)；需要额外空间 Θ(k)（辅助计数数组）与非比较性质。

8.3 基数排序（radix sort）¶

思想：对 d 位数字，从最低有效位到最高有效位依次做稳定排序（如计数排序）。
引理 8.3/8.4：对 b 位字、每轮 r 位、d = ⌈b/r⌉ 轮，总代价 O((b/r)(n + 2^r))；选取 r ≈ lg n 得 Θ((b/lg n)(n + 2^{lg n}))，即接近线性（当 b = O(lg n)）。
直观：稳定排序的”组合”才能保证正确性（先低后高）。

8.4 桶排序（bucket sort）¶

适用：输入在 [0,1) 区间均匀分布；将区间分为 n 个桶，元素入桶，各桶内排序（插入排序），再拼接。
期望运行时间 O(n)（若输入均匀分布，桶内元素少）；最坏情形（全落一桶）退化为 O(n²)。

本章小结 ¶

决策树下界、计数排序（O(n+k)）、基数排序（按位稳定排序）、桶排序（分布假设）、”何时线性排序可行”的判断——利用输入结构（小范围整数/有限基数/均匀分布）

第 9 章中位数与顺序统计（Medians and Order Statistics）¶

教学目标 ¶

掌握在 O(n) 内求最小/最大/第 i 小元素的方法
理解随机化选择与最坏情形线性时间选择

9.1 最小值和最大值 ¶

求最小值：n−1 次比较即可（遍历）。
同时求最大和最小：成对比较法，每次 3 次比较，共 ≤ ⌈3n/2⌉−2 次。

9.2 期望线性时间选择（RANDOMIZED-SELECT）¶

基于随机化划分：按 pivot 划分后，判断第 i 小元素落在哪个区间，递归（仅一侧）。
期望时间 O(n)：T(n) ≤ O(n) + (1/n)Σ T(max(k−1, n−k))，由指示变量与分析得 E[T(n)] = O(n)。

9.3 最坏情形线性时间选择（SELECT）¶

关键三步：分组（每组 5 个）→ 找各组中位数 → 递归找中位数的中位数作为划分主元，保证划分至少 3n/10 的规模。
递归式：T(n) ≤ T(⌈n/5⌉) + T(7n/10 + 6) + O(n)，解为 T(n) = O(n)。
意义：即使最坏输入也能在 O(n) 内完成选择；但常数较大，实践中常用随机化版本。
延伸：中位数 → 也可用于求 top-k、加权中位数等。

本章小结 ¶

成对比较、随机化选择（期望 O(n)）、最坏情形线性时间（分组 5 元素 + 中位数的中位数）、如何由选择求中位数与顺序统计

第三部分：数据结构（第 10–13 章）¶

第 10 章基本数据结构（Elementary Data Structures）¶

教学目标 ¶

掌握动态集合的基本操作（SEARCH、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR）
熟悉栈、队列、链表、树的数组/指针实现

10.1 数组、矩阵、栈、队列 ¶

栈（stack）：后进先出（LIFO）；PUSH/POP 均 O(1)；下溢/上溢处理。
队列（queue）：先进先出（FIFO）；用循环数组实现，ENQUEUE/DEQUEUE 均 O(1)。
数组与矩阵的行优先/列优先存储。

10.2 链表（linked lists）¶

单向/双向/循环链表；SEARCH/INSERT/DELETE 的代价分析（插入删除 O(1)，查找 O(n)）。
哨兵（sentinel）：哑结点简化边界处理，减少特殊分支（对某些操作使代码更简洁、常数更小）。

10.3 树的表示 ¶

二叉树：left/right/parent 指针（或数组下标）。
任意度数根树：左孩子右兄弟表示法（left-child, right-sibling）。
其他：如用父指针数组表示。

本章小结 ¶

动态集合操作、栈/队列的数组实现、双向链表与哨兵、树的多种表示，是后续所有数据结构（堆、哈希、BST、红黑树）的基础设施

第 11 章散列表（Hash Tables）¶

教学目标 ¶

理解散列思想：直接寻址表 → 散列表 → 冲突解决（链接法、开放寻址）
掌握散列函数设计（除法、乘法、乘移法、全域散列）与期望性能分析

11.1 直接寻址表 ¶

当关键字全域 U 很小时，直接以关键字为下标——O(1) 的 SEARCH/INSERT/DELETE。
局限性：全域大时空间不可行 → 用散列函数压缩到 m 个槽。

11.2 散列表与冲突解决 ¶

散列表 T[0..m−1]，散列函数 h(k) 将关键字映射到槽。
简单一致散列（simple uniform hashing）假设：每个关键字等可能散列到每个槽，且相互独立。
链接法（chaining）：每个槽放一个链表。期望查找时间 Θ(1 + α)，α = n/m 为负载因子。
定理：成功查找期望时间 Θ(1+α)，平均 1+α/2；当 n = O(m) 时 Θ(1)。

11.3 散列函数 ¶

好的散列函数：近似均匀、独立、运算快；关键字可能是整数/向量/字符串。
静态散列：
除法散列：h(k) = k mod m（避免 m 为 2 的幂等坏选择，取素数为佳）。
乘法散列：h(k) = ⌊m(k·A mod 1)⌋，常用黄金比例 A ≈ 0.618。
乘移法（multiply-shift）：h(k) = (ak mod 2^w) >> (w−r)（利用字长截断，快速）。
随机散列：从全域散列函数族中随机选一个，使任何输入下期望冲突数都有界。
数论全域族：h_{ab}(k) = ((ak+b) mod p) mod m（定理 11.4：冲突概率 ≤ 1/m）。
乘移全域族：2/m-全域（定理 11.5）。
长输入（向量/字符串）：先组合成整数再散列，或用密码学散列（如 SHA 族）。

11.4 开放寻址（open addressing）¶

所有元素存在表内，无链表；探测序列 h(k,0), h(k,1), …
线性探测：h(k,i) = (h’(k) + i) mod m——简单但有聚类（primary clustering）。
双重散列：h(k,i) = (h₁(k) + i·h₂(k)) mod m——最佳（探测序列数为 m² 量级）。
性能（独立均匀探测假设）：成功期望探测数 ≈ (1/α) ln(1/(1−α))，失败 ≈ 1/(1−α)；负载因子 α < 1。
删除问题：开放寻址中删除需用”墓碑”（deleted）标记，不能直接置空。
线性探测分析（11.5）：均匀散列假设下（定理 11.9），插入期望代价 O(1/α)（实际工程常采用线性探测因其缓存友好）。

本章小结 ¶

直接寻址 → 链接法（期望 Θ(1+α)）→ 开放寻址（线性/双重探测）→ 全域散列（对抗恶意输入）→ 字符串散列与哈希的实用考量（层次内存、wee hash）

第 12 章二叉搜索树（Binary Search Trees）¶

教学目标 ¶

掌握 BST 性质与基本操作（查询、插入、删除）
理解随机建树的高度期望

12.1 什么是二叉搜索树 ¶

BST 性质：结点 x 的左子树中所有关键字 ≤ x.key ≤ 右子树中所有关键字。
中序遍历（inorder tree walk）输出有序序列，O(n)。

12.2 查询 ¶

SEARCH（递归/迭代）、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR——均沿一条路径，O(h)。
后继（successor）：右子树非空取最左；否则向上找第一个”作为左孩子”的祖先。
定理：n 个结点的 BST，这些操作均 O(h)。

12.3 插入与删除 ¶

插入：沿搜索路径找到空位放入，O(h)。
删除三种情况：
1. 无孩子：直接删除；
2. 一个孩子：用孩子顶替；
3. 两个孩子：找后继 y（右子树最小），用 y 替换 x，再删除 y（y 至多一个孩子）。
定理 12.3：插入删除均 O(h)。
期望高度：随机插入 n 个关键字构造的 BST 期望高度 O(log n)。

本章小结 ¶

BST 性质、中序有序、搜索/后继/前驱、插入/删除、随机 BST 高度；本章为红黑树（第 13 章）与扩充数据结构（第 17 章）做铺垫

第 13 章红黑树（Red-Black Trees）¶

教学目标 ¶

掌握红黑树五条性质与”黑高”引理
理解旋转与插入/删除修复的各类情形，能手动模拟

13.1 红黑树性质 ¶

每个结点为红色或黑色；
根是黑色；
每个叶（NIL）是黑色；
红结点的两个子结点都是黑色（不能有两个连续红）；
从任一结点到其每个叶子的所有简单路径上黑结点数目相同（黑高 bh 定义）。
- 引理 13.1：n 个内结点的红黑树高度 ≤ 2 log₂(n+1)——由黑高与”红不连续”推出；故动态集合操作 O(log n)。

13.2 旋转（rotation）¶

左旋/右旋：保持 BST 性质的局部结构调整，O(1) 时间；是插入/删除修复的基本操作。

13.3 插入（RB-INSERT）¶

标准 BST 插入（新结点红）→ 逐种修复违反性质 4 的情况：
Case 1：叔结点 y 为红——变色（z 的父、叔变黑，祖父变红，z 上移两代）；
Case 2：叔为黑且 z 为右孩子——左旋转将 Case 2 变 Case 3；
Case 3：叔为黑且 z 为左孩子——右旋 + 变色，修复完成。
最多两次旋转；总时间 O(log n)。

13.4 删除（RB-DELETE）¶

用”替换/移植”（TRANSPLANT）思想；若被删结点 y 为黑色则触发修复（引入”双黑”概念）。
四种 case（以 x 的兄弟 w 的颜色/子结点颜色分类）：
Case 1：w 为红——变色 + 旋转，转为 Case 2/3/4；
Case 2：w 为黑且两孩子黑——变色，x 上移；
Case 3：w 为黑、左孩子红右孩子黑——旋转 + 变色，转 Case 4；
Case 4：w 为黑、右孩子红——变色 + 旋转，终止。
时间复杂度 O(log n)，旋转次数至多 3 次。

本章小结 ¶

五性质与黑高、旋转、插入三 Case、删除四 Case、O(log n) 保证；红黑树是平衡搜索树的代表，也是第 17 章扩充结构与后续图算法优先队列的基础

第四部分：高级设计与分析技术（第 14–19 章）¶

第 14 章动态规划（Dynamic Programming）¶

教学目标 ¶

掌握动态规划的两大要素：最优子结构与重叠子问题
掌握 DP 的四步设计流程与自顶向下（记忆化）/自底向上两种实现
通过钢条切割、矩阵链乘法、LCS、最优二叉搜索树四个经典例子深入理解

14.1 钢条切割（rod cutting）¶

问题：长度为 n 的钢条按价格表切割，求最大收益。
递归式：r_n = max(p_n, max(r_i + r_{n−i}))——最优子结构：最优解由子问题最优解组成。
朴素递归指数爆炸（重叠子问题）；记忆化（memoization） 或 自底向上（bottom-up） 均 O(n²)。
子问题图（subproblem graph）：结点为子问题，边为依赖——重叠子问题的图形刻画。

14.2 矩阵链乘法（matrix-chain multiplication）¶

问题：给定矩阵链 ⟨A₁,…,Aₙ⟩，求完全加括号方案使标量乘法次数最少。
结构：最优括号化在某个 k 处分裂为两个子链；
递归式：m[i,j] = min_{i≤k<j} { m[i,k] + m[k+1,j] + p_{i−1}p_k p_j }。
自底向上按链长填表，O(n³) 时间、O(n²) 空间；重建最优解用 s[i,j] 记录分裂点。

14.3 动态规划的原理 ¶

最优子结构（optimal substructure）：最优解包含子问题最优解；注意子问题独立。
重叠子问题（overlapping subproblems）：递归求解时反复遇到相同子问题——这是 DP 优于直接递归之处。
重构解：存储选择，最后回溯。
记忆化（memoization）：自顶向下 + 表格；与自底向上在渐近上等价。

14.4 最长公共子序列（LCS）¶

最优子结构（定理 14.1）：若 xₘ = yₙ，则 LCS 含该字符 + 前缀的 LCS；否则为两个前缀的 LCS 的较大者。
递归式与 LCS-LENGTH 表；输出 O(m+n) 空间可压缩（只存长度）。
应用：DNA 序列相似性、文件 diff。

14.5 最优二叉搜索树（optimal BST）¶

给定关键字（及失败结点的）频率，构造期望搜索代价最小的 BST。
结构：任一子树为连续关键字区间；递归式 e[i,j] = min_k { e[i,k−1] + e[k+1,j] + w(i,j) }，其中 w 为区间总概率。
运行时间 O(n³)（可优化到 O(n²) 因四边形不等式性质，习题延伸）。

本章小结 ¶

最优子结构 + 重叠子问题、自顶向下/自底向上、记忆化、子问题图；经典例题：钢切割、矩阵链、LCS、最优 BST、编辑距离、Viterbi 等（习题）

第 15 章贪心算法（Greedy Algorithms）¶

教学目标 ¶

掌握贪心策略的要素：贪心选择性质与最优子结构
理解贪心 vs 动态规划：何时贪心成立，何时必须 DP
通过活动选择、Huffman 编码、离线缓存三个经典问题掌握贪心证明

15.1 活动选择问题（activity selection）¶

问题：最大相容活动集合（按结束时间）。
贪心选择：总是选择结束时间最早的相容活动——直观合理且正确（定理 15.1）。
递归/迭代贪心算法；复杂度 O(n log n)（按结束时间排序主导）或 O(n)。

15.2 贪心策略的要素 ¶

贪心选择性质（greedy-choice property）：每步的局部最优选择最终导致全局最优——通过交换论证（exchange argument）证明。
最优子结构：剩余子问题仍为最优。
贪心 vs DP：两者都需要最优子结构；贪心多做一步”贪心选择”而不再求解全部子问题（比较：0-1 背包需 DP，部分背包贪心即可）。

15.3 Huffman 编码 ¶

前缀码（prefix-free codes）与二叉树对应；最优前缀码 = Huffman 算法：每次合并频率最小的两棵树（借助最小堆）。
正确性：最优前缀码具有最优子结构（引理 15.3）+ 贪心选择性质（频率最小的两个字符作为最深兄弟，定理 15.4）。
应用：文件压缩；编码长度 = 叶子深度 × 频率。

15.4 离线缓存（offline caching）¶

缓存替换问题：已知未来访问序列时，最优策略是最远未来使用（furthest-in-future）。
证明要素：最优子结构 + 贪心选择性质（定理 15.5）。
意义：离线最优解作为在线缓存（第 27 章）竞比的基准（competitive ratio）。

本章小结 ¶

贪心选择性质（交换论证）、最优子结构、活动选择、Huffman 树、离线缓存；”贪心何时有效”的判断能力是本章核心

第 16 章摊还分析（Amortized Analysis）¶

教学目标 ¶

掌握摊还分析的三种方法：聚合分析、记账法、势能法
理解”平均到每次操作”的含义，能分析动态表、栈、二进制计数器

16.1 聚合分析（aggregate analysis）¶

对所有操作的总代价求上界，再除以操作数得摊还代价。
例：栈的 MULTIPOP——总代价 O(n)（每个元素至多被压入/弹出一次），摊还 O(1)/操作。
例：二进制计数器 INCREMENT：总翻转次数 ≤ 2n，摊还 O(1)/操作。

16.2 记账法（accounting method）¶

给不同操作分配不同的摊还代价（可高于或低于实际代价）；”多付”的部分作为信用存储，用于支付后续”少付”操作。
栈：PUSH 记账 2，POP/MULTIPOP 记账 0（信用 = 元素存在）；计数器：置 0 记账 0，置 1 记账 2。
关键：任何操作序列的总摊还代价 ≥ 总实际代价（信用永不欠账）。

16.3 势能法（potential method）¶

定义势函数 Φ(D)：数据结构状态的函数；摊还代价 ĉ = 实际代价 + ΔΦ。
若 Φ(D₀) = 0 且 Φ 恒 ≥ 0，则总摊还代价 ≥ 总实际代价。
栈：Φ = 栈中元素数；计数器：Φ = 1 的个数（ΔΦ = 1 − t + … 推导摊还 2）。
势能法是三者中最通用、最强大，用于复杂分析（如第 19 章并查集）。

16.4 动态表（dynamic tables）¶

表扩张：满则翻倍（表扩大）；摊还代价 O(1)/插入（势 = 表大小 − 元素数）。
表收缩：元素少于 1/4 时减半（用 1/4 阈值避免抖动）。
摊还代价：插入 O(1)，删除 O(1)；摊还分析保证整体 O(n) 总代价。

本章小结 ¶

聚合、记账、势能三法等价；二进制计数器、栈、动态表的摊还 O(1)；势能法是后续并查集、树结构等分析的标准工具

第 17 章扩充的数据结构（Augmenting Data Structures）¶

教学目标 ¶

掌握”在现有数据结构上增加信息”的四步扩充法
通过动态顺序统计与区间树两个完整例子掌握扩充技巧

17.1 动态顺序统计（dynamic order statistics）¶

在红黑树结点上增加 size（子树结点数）字段。
OS-SELECT（按秩找元素）与 OS-RANK（求元素秩）均 O(log n)。
维护：旋转时 size 只需更新旋转涉及的两个结点——O(1) 局部更新保证整体 O(log n)。

17.2 扩充数据结构的四步法 ¶

选择基础数据结构（如红黑树）；
决定附加信息（如 size）；
验证维护：基础操作（插入/删除/旋转）能否在 O(log n) 内维护附加信息；
开发新操作（SELECT/RANK/INTERVAL-SEARCH）。
- 定理 17.1：若结点字段 f 只依赖结点及其子树的信息，则红黑树插入/删除后可在 O(log n) 内维护。

17.3 区间树（interval trees）¶

目标：支持”查找与给定区间重叠的区间”。
四步：
1. 基础结构：红黑树，按区间低端点排序；
2. 附加信息：子树中最大高端点 max；
3. 维护：max = max(low 自身的 low, 左右子树 max)——插入/删除 O(log n)；
4. 新操作 INTERVAL-SEARCH：沿”max ≥ low[i]”的路径寻找重叠区间，O(log n)（定理 17.2）。

本章小结 ¶

扩充四步法、顺序统计树（size）、区间树（max）；可推广到更多附加信息（如习题最大重叠点、Josephus 排列）

第 18 章 B 树（B-Trees）¶

教学目标 ¶

理解 B 树作为磁盘/二级存储上的平衡搜索树的设计动机
掌握 B 树定义、高度、插入（分裂）与删除（合并）操作

18.0 磁盘与外存 ¶

磁盘访问远慢于内存：I/O 次数是主导代价；B 树通过大扇出（fan-out）降低树高，减少磁盘访问。

18.1 B 树定义 ¶

参数 t（最小度数）：每个非根结点含 [t−1, 2t−1] 个关键字（根可更少）；所有叶子同一深度。
结点最多 2t−1 个关键字 = 2t 个孩子（满结点）。
高度：引理：n ≥ 1 时高度 h ≤ log_t((n+1)/2)；大 t 值 → 低树高，适合磁盘。

18.2 基本操作 ¶

搜索：类似 BST，多路（结点内线性/二分），O(t log_t n) I/O。
插入：自顶向下沿路径遇到满结点即分裂——单趟完成，无需回溯；O(t log_t n)。
分裂（B-TREE-SPLIT-CHILD）：满结点中间关键字上移给父，左右两半成为两兄弟。

18.3 删除 ¶

若需要，先合并/借调（借用兄弟或合并），保证路径上结点不”过少”；
删除情况：叶子直接删；内结点用前驱/后继替换后删除；必要时下放合并。
复杂度 O(t log n) I/O。

本章小结 ¶

大扇出平衡树、B 树高度与 t 的关系、分裂/合并保证最低占用、单趟插入/删除；是数据库索引的基石，与红黑树（内存）相对照（磁盘）

第 19 章用于不相交集合的数据结构（Data Structures for Disjoint Sets）¶

教学目标 ¶

掌握并查集（disjoint-set）的三种操作：MAKE-SET、FIND-SET、UNION
掌握两种实现（链表、森林）与两种启发式（按秩合并、路径压缩）
了解逆 Ackermann 函数的接近常数摊还复杂度

19.1 不相交集合操作 ¶

维护一组互不相交的集合；UNION 合并两集合（可用加权合并缩短链表）。
应用：连通分量 的动态维护（如求无向图的连通分量）。

19.2 链表表示 ¶

每个集合一个链表 + 尾指针；简单 UNION 总代价 O(n²)。
加权合并启发式（weighted-union heuristic）：总是把小集合合并进大集合——总代价 O(m log n)（定理 19.1）。

19.3 不相交集合森林（disjoint-set forests）¶

树表示集合（根为代表元素），两个启发式：
1. 按秩合并（union by rank）：秩 = 树高上界，秩小树挂到秩大树；
2. 路径压缩（path compression）：FIND-SET 时把路径上所有结点直接指向根。
两个启发式合用时，任意 m 个操作（n 个 MAKE-SET）的运行时间为 O(m α(n))，其中 α(n) 为 Ackermann 函数的逆，增长速度极慢（α(n) ≤ 4 对实际中一切 n）——实际线性。

19.4 分析（进阶）¶

引入”秩分组”与势函数，以抵消路径压缩的收益；
结论：逆 Ackermann 上界几乎线性，是现代算法分析中最精致的摊还分析。

本章小结 ¶

MAKE-SET/FIND-SET/UNION、加权合并、按秩合并、路径压缩、逆 Ackermann 界；应用于 Kruskal（21 章）、离线最小、最低公共祖先等

第五部分：图算法（第 20–25 章）¶

第 20 章基本的图算法（Elementary Graph Algorithms）¶

教学目标 ¶

掌握图的两种表示（邻接表、邻接矩阵）及适用场景
熟练掌握广度优先搜索（BFS）与深度优先搜索（DFS）
掌握拓扑排序与强连通分量（Kosaraju 算法）

20.1 图的表示 ¶

邻接表：空间 Θ(V+E)，适合稀疏图；判断边 (u,v) 需 O(degree(u))。
邻接矩阵：空间 Θ(V²)，适合稠密图；判断边 O(1)。

20.2 广度优先搜索（BFS）¶

以源 s 为根构造广度优先树；用队列，访问距离递增的层。
每个顶点至多入队一次，时间 O(V + E)。
最短路径性质：BFS 算出的距离即无权图中的最短路径长度（引理 20.1–20.3，定理 20.5 正确性）。

20.3 深度优先搜索（DFS）¶

递归/显式栈；时间戳 d[u]（发现）、f[u]（完成） 形成括号结构。
括号定理（20.7）：后代区间嵌套于祖先区间。
白色路径定理（20.9）：DFS 树中的祖先关系可由白路径刻画。
边分类（在无向/有向图）：树边、后向边、前向边、横向边；
无向图无前向边/横向边；有向图存在后向边 ⇔ 有环。
复杂度 O(V+E)。

20.4 拓扑排序（topological sort）¶

定义：DAG 上所有边从前向后；DFS 完成时间的逆序即拓扑序（定理 20.12）。
应用：课程依赖、编译依赖、任务调度；O(V+E)。

20.5 强连通分量（strongly connected components）¶

算法（Kosaraju）：① 对 G 做 DFS 得完成时间；② 在转置图 Gᵀ 上按完成时间降序做 DFS；每个 DFS 森林的树即为一个 SCC。
理论基础：分量图（condensation graph）为 DAG；引理 20.13–20.15、定理 20.16。
复杂度 O(V+E)；应用：压缩图、2-SAT、网页排名相关分析。

本章小结 ¶

邻接表/矩阵、BFS（最短路、广度优先树）、DFS（时间戳、边分类）、拓扑排序、强连通分量；是后续所有图算法的基础工具

第 21 章最小生成树（Minimum Spanning Trees）¶

教学目标 ¶

理解 MST 的安全边/割理论（生长一棵 MST 的一般方法）
掌握 Kruskal（并查集）与 Prim（优先队列）两种算法及复杂度

21.1 生长最小生成树 ¶

贪心框架 GENERIC-MST：不断加入”安全边”（安全 = 加入后仍属于某棵 MST）。
割定理（定理 21.1）：若边 (u,v) 是横跨割 (S, V−S) 的最轻边，且 A 无横跨该割的边，则 (u,v) 是安全边。
推论 21.2：森林中连接两个不同树的”最轻边”安全。

21.2 Kruskal 算法 ¶

按权排序边，用并查集判断端点是否已连通：不连通则加入（连成树）。
复杂度：O(E log E)（= O(E log V)），由排序主导；几乎线性的并查集部分使实际很快。

21.2 Prim 算法 ¶

从根出发扩展一棵树：每次选连接树与树外的最轻边（用优先队列/最小堆）。
复杂度：二叉堆 O(E log V)；斐波那契堆 O(E + V log V)（更优，但实现复杂）。

本章小结 ¶

割定理与安全边、Generic-MST、Kruskal（边视角 + 并查集）、Prim（顶点视角 + 堆）、二者均为贪心的正确性依赖”最轻边安全”

第 22 章单源最短路径（Single-Source Shortest Paths）¶

教学目标 ¶

掌握松弛（relaxation）这一核心操作与最短路径性质
掌握三种算法及其适用条件：Bellman-Ford（负权、差分约束）、DAG 最短路径、Dijkstra（非负权）
理解最短路径与线性规划/差约束的联系

0 基础概念 ¶

最优子结构（引理 22.1）；负权边与负环（无最短路径）；前驱子图。
松弛：若 d[v] > d[u] + w(u,v)，更新 d[v] = d[u] + w(u,v)。
最短路径性质：三角不等式、上界性质、无路径性质、收敛性质、路径松弛性质、前驱子图性质（22.5 节汇总）。

22.1 Bellman-Ford 算法 ¶

对所有边做 n−1 轮松弛，最后再检查一轮是否存在可松弛边（检测负环）。
复杂度 O(VE)；适用：允许负权、检测负环；在无负环时正确（定理 22.4）。

22.2 DAG 最短路径 ¶

先拓扑排序，再按拓扑序逐顶点松弛所有出边。
复杂度 O(V+E)（线性！）；可处理负权（因 DAG 无环）。

22.3 Dijkstra 算法 ¶

贪心 + 优先队列：每次选当前 d 值最小的未确定顶点，松弛其出边。
要求边权非负（否则贪心失效）；复杂度：二叉堆 O(E log V)（+ V log V），斐波那契堆 O(E + V log V)。
正确性（定理 22.6）：每次选出的 u 的 d[u] 即为真正最短距离（三角不等式 + 归纳）。

22.4 差约束与最短路径 ¶

差分约束系统：形如 x_j − x_i ≤ b_k 的不等式组；可行域为凸区域。
转化为约束图：边 i→j 权 b_k；Bellman-Ford 求单源最短路给出可行解（定理 22.9）。
应用：调度、时限约束、VLSI 布局等；”系统不可行” ⇔ 约束图含负环。

本章小结 ¶

松弛范式、Bellman-Ford（O(VE)，负权/负环检测）、DAG 线性算法、Dijkstra（非负权、堆优化）、差约束建图；最短路径性质证明是后续所有最短路算法的理论基础

第 23 章所有结点对的最短路径（All-Pairs Shortest Paths）¶

教学目标 ¶

掌握三种策略：矩阵乘法式 DP、Floyd-Warshall、Johnson（稀疏图）
理解输出矩阵与路径重构

23.1 最短路径与矩阵乘法 ¶

DP：L⁽ᵐ⁾[i,j] = 至多 m 条边的最短路径；L⁽ᵐ⁾ = L⁽ᵐ⁻¹⁾ ⊗ W（”min-plus 矩阵乘法”）。
重复平方（squaring）技巧：计算 L⁽¹⁾, L⁽²⁾, L⁽⁴⁾, …（倍增）→ O(n³ log n)。

23.2 Floyd-Warshall 算法 ¶

按中间顶点编号动态规划：d⁽ᵏ⁾[i][j] = min(d⁽ᵏ⁻¹⁾[i][j], d⁽ᵏ⁻¹⁾[i][k] + d⁽ᵏ⁻¹⁾[k][j])。
三重循环 O(n³)；可处理负权（无负环）；前驱矩阵重构路径。
传递闭包：只关心”可达性”布尔矩阵，同样 DP，O(n³)（bitset 可加速）。

23.3 Johnson 算法（稀疏图）¶

思路：重新赋予权值（reweighting）使边权非负（h(v) 势函数：w’(u,v)=w(u,v)+h(u)−h(v)，由 Bellman-Ford 求 h），再对每个顶点运行 Dijkstra。
复杂度：O(VE + V² log V)（稀疏图优于 Floyd-Warshall 的 O(n³)）。
若存在负环，重新赋权可检测（Bellman-Ford 失败）。

本章小结 ¶

min-plus 矩阵乘法（倍增）、Floyd-Warshall（O(n³)）、Johnson（稀疏图 + 重新赋权）、闭包、路径重构；选择依据：稠密 → Floyd；稀疏 → Johnson

第 24 章最大流（Maximum Flow）¶

教学目标 ¶

掌握流网络、残量网络、增广路径、割与最大流最小割定理
掌握 Ford-Fulkerson 方法与 Edmonds-Karp 改进
掌握最大二分匹配的流建模

24.1 流网络 ¶

定义：有向图 + 源 s + 汇 t + 容量 c(u,v)；流 f 满足容量约束与流量守恒。
建模技巧：多源多汇（加超级源/超级汇）；反平行边（拆结点）。

24.2 Ford-Fulkerson 方法 ¶

残量网络 G_f：剩余容量与反向边（用于”撤销/调整”流）；
增广路径：残量网络中的 s→t 路径；每次增广其瓶颈容量，直到无增广路径。
割与最小割：割的容量 = 从 S 到 T 的总容量；任意流 ≤ 任意割容量；
最大流最小割定理（定理 24.6）：以下等价——f 最大、无增广路径、存在割使 |f| = 容量。
复杂度：O(E|f*|)（依赖最大流量值；若容量为无理数甚至可能不终止）。
Edmonds-Karp：总是选最短增广路径（BFS） → O(VE²)，独立于容量。

24.3 最大二分匹配 ¶

构建流网络：源→左部、左→右（容量 1）、右→汇；
积分性定理（定理 24.10）：最大流可取整数值 → 最大流 = 最大匹配（用匹配大小 m = |f|）。
Ford-Fulkerson 在二分匹配图上复杂度 O(VE)。

本章小结 ¶

流与守恒、残量网络、增广路径、min-cut/max-flow 定理、Ford-Fulkerson、Edmonds-Karp（BFS 增广）、二分匹配转化；后续第 25 章将深化匹配

第 25 章二分图中的匹配（Matchings in Bipartite Graphs）¶

教学目标 ¶

掌握二分匹配理论与增广路径（改进路径）的充要条件
掌握 Hopcroft-Karp 算法与稳定婚姻（Gale-Shapley）算法
了解匈牙利算法（指派问题）

25.1 最大二分匹配（重访）¶

增广路径（M-augmenting path）：起止于未匹配点的交替路径——翻转它可让匹配 +1。
Berge 定理：匹配 M 最大 ⇔ 不存在 M-增广路径。
Hall 定理（推论 25.4 相关）：完美匹配存在 ⇔ 对所有 X 子集 S 有 |N(S)| ≥ |S|。
Hopcroft-Karp 算法：用 BFS 分层（最短增广路径）多路增广 + DFS 一次找出多增广路径；复杂度 O(√V · E)——显著快于朴素 O(VE)。

25.2 稳定婚姻问题（Gale-Shapley）¶

每个男人按偏好求婚，女人保留更优者（可”解除婚约”）——订婚算法。
保证：总是终止于稳定匹配（无不满意配对），且对求婚方为男优（man-optimal），对女方为最差（woman-pessimal）但仍有稳定匹配（定理 25.9–25.13）。

25.3 匈牙利算法（指派问题）¶

指派问题：完全二分图，边有权，求最小权重完美匹配。
思想：顶点标号（vertex labeling）+ 等子图（equality subgraph G_h）+ 交替树/匈牙利树；找到能扩展匹配的”临界”标号调整。
复杂度 O(n³)（本课程实现 O(n³) 进阶练习；朴素实现更高）。对稠密图实用。

25 小结 ¶

增广路径定理、Hall 定理、Hopcroft-Karp（O(√V·E)）、Gale-Shapley 稳定婚姻、匈牙利算法；匹配是网络流（24）的自然深化，也见之于调度/指派/拍卖等实际应用

第六部分：高级专题（第 26–31 章）¶

第 26 章并行算法（Parallel Algorithms）¶

教学目标 ¶

掌握 fork-join 并行模型：工作量（work）与延展度（span）
掌握并行算法的分析（Brent 定理、贪心调度）与常用并行算法
能识别竞争条件（race）

26.1 fork-join 并行基础 ¶

关键字：spawn（派生）、sync（同步）——派生任务并行执行，sync 等待完成。
执行图（DAG）：结点 = 指令，边 = 依赖。
性能度量：
工作量 T₁：串行执行总步数；
延展 T∞：无限处理器下最短时间（关键路径长度）；
并行度 T₁/T∞（= 饱和所需处理器数）。
Brent 定律：P 处理器时间 T_P ≥ max(T₁/P, T∞)；贪心调度器在 P 处理器上 T_P ≤ T₁/P + T∞（定理 26.1）。
Corollary：贪心调度达到 T_P = O(T₁/P + T∞)；并行加速比 ≤ 并行度。
分析：T₁ = 串行运行时间；T∞ 反映可并行潜力。
并行循环：并行 for 的展开（递归分治）；竞争条件：两任务读写同一变量（无同步）→ 需用原子操作/分治避免（矩阵乘法、归并排序均有例子）。

26.2 并行矩阵乘法 ¶

并行三重循环：T∞ = O(log n)（每层并行求和树），T₁ = O(n³)；并行度高。
分治并行乘法（含 Strassen 并行化）与 cache 友好设计。

26.3 并行归并排序 ¶

并行归并（并行合并两有序数组）：T∞ = O(log² n)，T₁ = O(n)（用二分选划分点并行递归）；并行归并排序 T₁ = O(n log n)，T∞ = O(log³ n)。

26 小结 ¶

fork-join 模型、T₁/T∞/并行度/Brent、贪心调度、并行归并与归并排序、竞争条件；为后续并行图算法与并行矩阵算法打基础

第 27 章在线算法（Online Algorithms）¶

教学目标 ¶

掌握竞争比（competitive ratio）这一在线算法分析框架
掌握滑雪租借（电梯等待）、搜索列表维护、在线缓存等经典问题

27.1 等待电梯（ski rental 变体）¶

在”不知何时到来”下权衡租/买：最优在线策略的竞争比为 2（买 vs 租的阈值策略）。
建立”在线决策无法回退”的直觉模型。

27.2 维护搜索列表（move-to-front）¶

线性搜索列表维护：未知访问序列；向前移动（move-to-front, MTF） 在线算法；
定理：MTF 的竞争比为 2——比”转置/频率计数”等启发式有最坏情形保证。

27.3 在线缓存 ¶

确定性缓存算法：竞争比下界 ≥ k（缓存大小）；最远未来/最少使用仅离线最优；
定理：任何确定性在线缓存算法的竞争比 ≥ k；LFU/LRU 等达到 2 竞争比？——分析见 27.3（LRU 竞争比 = k）。
随机化缓存：随机选择驱逐 → 竞争比可降为 O(log k)（如 RANDOM/Marking 类算法），说明随机化能改善最坏情形。

27 小结 ¶

在线 vs 离线、竞争比、move-to-front（2 竞争）、确定性缓存下界 k、随机化缓存的 O(log k)；在线算法是”竞比分析”的现代主题

第 28 章矩阵运算（Matrix Operations）¶

教学目标 ¶

掌握 LUP 分解与线性方程组求解（前向/回代）
掌握矩阵求逆与矩阵乘法的关系（等价难易）
了解对称正定矩阵与最小二乘

28.1 求解线性方程组（LUP 分解）¶

LUP 分解：A = LUP（下三角 L、上三角 U、置换 P），引入部分主元（数值稳定性）。
求解流程：解 Ly = Pb（前向代换）→ 解 Ux = y（回代）。
复杂度：分解 O(n³)，每次代换 O(n²)；多右端项只需分解一次。

28.2 矩阵求逆 ¶

由 LUP 分解对每列求解：求逆 O(n³)。
定理 28.1/28.2：矩阵乘法与矩阵求逆互不更难（乘法 ≥ 求逆 ≥ 乘法）——在多项式时间内等价。

28.3 对称正定矩阵与最小二乘 ¶

对称正定（SPD）：xᵀAx > 0 对所有 x≠0；性质（各主子式正定、Schur 补引理 28.5）→ 可用Cholesky 分解（LLᵀ）更高效求解。
最小二乘：解超定方程组 min ||Ax−b||²，正规方程 AᵀAx = Aᵀb（要求列满秩）。

本章小结 ¶

LUP 分解、前/回代、矩阵求逆与乘法等价性、SPD/Cholesky、最小二乘；为数值算法（线性规划内点法、机器学习梯度法）提供基础

第 29 章线性规划（Linear Programming）¶

教学目标 ¶

掌握线性规划的标准形式与几何解释
掌握把问题（最短路、最大流、最小费用流）建模为 LP
理解对偶性（duality）与基本定理

29.1 线性规划形式 ¶

标准形：max cᵀx，约束 Ax ≤ b，x ≥ 0；可行域为凸多面体。
求解算法概览：单纯形法（实际高效、指数最坏）、椭球法（多项式但实际慢）、内点法（多项式、实际高效）。

29.2 把问题建模为 LP ¶

最短路径（作为势差的约束）、最大流、最小费用流、多商品流（一般多商品流是整数规划，不可 LP 化）。
关键技巧：变量 + 线性约束描述流守恒/容量/费用；目标函数线性化。

29.3 对偶性 ¶

对偶问题：min cᵀx s.t. Ax ≤ b, x ≥ 0 的对偶为 max bᵀy s.t. Aᵀy ≥ c, y ≥ 0。
弱对偶（引理 29.1）：任何原始可行解 ≥ 任何对偶可行解——提供下界。
Farkas 引理（29.3）：不可行性由对偶刻画。
强对偶（定理 29.4）：原与对偶同最优值（若两者均可行）。
基本定理（29.5）：LP 最优解出现在极点（顶点）——单纯形在顶点间移动的理由。

29 小结 ¶

标准形、几何（多面体/极点）、单纯形与内点法、建模（流/最短路/网络）、对偶（弱/强/互补松弛）、整数规划的 NP 难概述；为后续第 34、35 章（NP 完全与近似）提供线性规划放松的工具

第 30 章多项式与快速傅里叶变换（Polynomials and the FFT）¶

教学目标 ¶

掌握多项式的两种表示（系数、点值）与互转
掌握 DFT/FFT 原理（单位复数根）与卷积
理解 FFT 的电路实现

30.1 多项式表示 ¶

系数表示：求值 O(n)，乘法卷积 O(n²)；
点值表示：乘法 O(n)（对应点相乘）；
插值唯一性（定理 30.1）：n+1 个点唯一确定 n 次多项式。
策略：系数 → 点值（求值）→ 逐点乘 → 插值回系数；用 FFT 使求值/插值均为 O(n log n)，从而多项式乘法 O(n log n)。

30.2 DFT 与 FFT ¶

n 次单位根：ωₙ = e^{2πi/n}；引理：相消引理（ω_{dn}^{dk}=ωₙᵏ）、半分引理（ωₙ^{2k}=ω_{n/2}^k）、求和引理（Σωₙ^{jk} = 0）。
DFT：y_k = Σ a_j ωₙ^{kj}；
FFT（Cooley-Tukey）：按奇偶分成 A^even/A^odd，递归 2 个 n/2 点 FFT，合并 O(n)：
T(n) = 2T(n/2) + O(n) = O(n log n)。
插值 = 逆 DFT（用 ωₙ^{-1} 与 1/n），定理 30.7（DFT 求逆）。
卷积定理（30.8）：多项式乘积系数 = 两多项式系数的卷积；可 FFT 计算。

30.3 FFT 电路 ¶

蝶形运算（butterfly）：一次乘加 + 复用；递归电路 → 完整的 O(n log n) 深度 log n 的 FFT 网络；输入按位逆序排列。

30 小结 ¶

系数↔点值、单位根与引理、FFT 分治（O(n log n)）、卷积定理、电路实现；是信号处理与大数据乘法（大整数乘法）的基础

第 31 章数论算法（Number-Theoretic Algorithms）¶

教学目标 ¶

掌握数论基础（整除、模、gcd、唯一分解）
掌握欧几里得算法与扩展欧几里得、模线性方程、中国剩余定理、幂模运算
掌握 RSA 公钥密码系统与素性测试（Miller-Rabin）

31.1 数论基础 ¶

整除性、除法定理（a = qn + r，0 ≤ r < n）、模等价、公约数与 gcd 性质（gcd 组合定理）。
唯一分解定理（算术基本定理）；互素与欧拉 φ 函数。

31.2 最大公约数 ¶

欧几里得算法（辗转相除）：EUCLID(a,b)，O(log min(a,b))（Lamé 定理：步数 ≤ 2 log φ(min)）。
扩展欧几里得：EXTENDED-EUCLID 求 (d, x, y) 使 ax + by = d。

31.3 模算术与群论基础 ¶

有限群 Z_n（加法群）与 Z_n（乘法群）；子群与 Lagrange 定理*（子群大小整除群大小）。
循环群与生成元（元素阶的性质）。

31.4 模线性方程 ¶

方程 ax ≡ b (mod n) 有解 ⇔ gcd(a,n) | b；解数 = gcd(a,n) 个（模 n）。
求解方法：先用扩展欧几里得求 ax ≡ d (mod n) 的特解，再加 n/d 的倍数。

31.5 中国剩余定理（CRT）¶

给定两两互素的模 n₁,…,n_k，系统 x ≡ aᵢ (mod nᵢ) 有唯一解模 N = Π nᵢ。
应用：大数运算分解为小模运算再重组（快速并行算术）。

31.6 元素的幂与反复平方 ¶

Euler 定理：a^φ(n) ≡ 1 (mod n)（a 与 n 互素）；Fermat 小定理：a^{p−1} ≡ 1 (mod p)。
离散对数问题 与阶的性质（用于密码学）。
反复平方（MODULAR-EXPONENTIATION）：二进制展开指数，O(log n) 次乘法。

31.7 RSA 公钥密码 ¶

密钥生成：选大素数 p,q，n = pq，e 与 (p−1)(q−1) 互素，d = e⁻¹ mod φ(n)；公钥 (e,n)、私钥 (d,n)。
加密 c = mᵉ mod n，解密 m = cᵈ mod n（正确性依赖 Euler 定理，定理 31.36）。
安全性：破解 RSA 需要分解 n（大整数分解难题）；混合密码系统 = 对称密钥 + RSA 交换。

31.8 素性测试 ¶

素数定理：π(x) ≈ x/ln x（素数密度）。
伪素性测试（Fermat 测试）：a^{n−1} ≡ 1 的合数可能通过（Carmichael 数）；
Miller-Rabin 随机测试：错误率 ≤ 1/4（可多次运行指数压低，定理 31.39/31.40）；是实践中寻找大素数（RSA 密钥）的标准工具。

31 小结 ¶

数论基础、Euclid/扩展欧几里得、模群与 Lagrange、模线性方程、CRT、Euler/Fermat、反复平方、RSA、Miller-Rabin；是密码学与信息安全的核心算法库

第七部分：应用与前沿（第 32–35 章）¶

第 32 章字符串匹配（String Matching）¶

教学目标 ¶

掌握字符串匹配问题的各种算法及其思想
重点掌握 KMP 算法（前缀函数）与 Rabin-Karp（哈希）
了解有限自动机与后缀数组

32.0 记号 ¶

文本 T[1..n]、模式 P[1..m]；有效位移 s 使 T[s+1..s+m] = P；重叠后缀引理（32.1）是 KMP 的基础。

32.1 朴素算法 ¶

每个位移逐字符比较：最坏 O((n−m+1)·m)。

32.2 Rabin-Karp ¶

把模式哈希为数值，滚动计算文本子串的哈希（模 q）；匹配则进一步验证。
期望 O(n+m)；最坏 O(nm)（哈希碰撞）；利用模 q 的小型随机性可期望线性。平均情形优秀。

32.3 有限自动机 ¶

由模式构造字符串匹配自动机（状态 = 已匹配前缀长度，转移函数 δ）；
匹配过程 O(n)，预处理 O(m·|Σ|)（三字符集）。
后缀函数递归引理（32.2/32.3）：δ(q, a) 由最长前缀后缀决定——是 KMP 的抽象。

32.4 Knuth-Morris-Pratt（KMP）¶

前缀函数 π：模式 P 中每个位置的最长”真前缀 = 后缀”长度；
匹配主循环不回溯文本指针：失配时按 π 回退模式——总时间 O(n + m)（文本只前进）。
正确性：前缀函数迭代引理（32.5）等；算法简洁，是字符串处理的核心工具。

32.5 后缀数组 ¶

文本所有后缀的字典序排序数组；配合 LCP 数组可支持 O(m + log n) 的子串匹配与许多字符串问题；
构造：倍增 + 基数排序 → O(n log n)。

32 小结 ¶

朴素 → Rabin-Karp（哈希）→ 有限自动机 → KMP（前缀函数，线性）→ 后缀数组；字符串匹配是文本处理、生物信息学的核心工具

第 33 章机器学习算法（Machine-Learning Algorithms）¶

教学目标 ¶

掌握 k-means 聚类（Lloyd 算法）的迭代优化思路
掌握乘法权重算法（multiplicative weights）的在线学习框架
掌握梯度下降（含随机梯度下降）及其在机器学习中的应用

33.1 聚类（k-means / Lloyd 方法）¶

特征向量与相似度（距离）；k-means 目标：最小化簇内点到中心的平方距离和。
Lloyd 过程：交替优化——固定簇 → 最优中心为均值（定理 33.1）；固定中心 → 每点分到最近中心（定理 33.2）；迭代直到收敛。
说明：Lloyd 收敛到局部最优（NP 难问题的启发式）；EM 思想的雏形；用于图像压缩、客户分群等。

33.2 乘法权重（multiplicative-weights）¶

框架：多个”专家”，每轮按权重分布选择，观察损失后按指数缩小坏专家权重；
定理 33.4（Hedge）：总损失 ≤ (1+ε)·最优专家损失 + O((ln N)/ε)——接近最优。
应用：在线学习、博弈、组合优化近似（如集合覆盖、L1 回归）。

33.3 梯度下降 ¶

无约束梯度下降：x ← x − η∇f(x)（凸函数保证收敛）；
对 α-强凸、β-光滑 函数：收敛率 O(1/ε²) 步或指数收敛（定理 33.8 等）。
约束梯度下降：投影步（projected gradient）保证可行域内（定理 33.11）。
应用：解线性方程组（最小二乘/正规方程）、机器学习训练损失函数最小化。
随机梯度下降（SGD）（习题 33-4）：每次用一个样本估计梯度——大数据规模下显著降成本（机器学习训练标配）。

33 小结 ¶

聚类（Lloyd/k-means）、乘法权重（在线学习竞比）、梯度下降（凸优化收敛性）、SGD；是现代机器学习算法的基础工具

第 34 章 NP 完全性（NP-Completeness）¶

教学目标 ¶

掌握 P、NP、NP 完全的形式化定义（语言/编码/归约）
掌握归约的方法与”证明一个问题是 NP 完全的”标准流程
熟悉经典 NP 完全问题谱系（电路可满足性 → SAT → 3-CNF → 团/顶点覆盖/哈密顿回路/TSP/子集和）

34.1 多项式时间 ¶

抽象问题 → 判定问题（语言）→ 编码；P = 可多项式时间判定的语言（图灵机模型；多项式时间 = 健壮（不依赖编码细节）——引理 34.1）。

34.2 多项式时间验证与 NP ¶

验证器：证书（certificate）在多项式时间内验证；NP = 有多项式时间验证器的语言。
例：哈密顿回路问题（HAM-CYCLE）易验证（给回路）但未知可求解。

34.3 可归约性与 NP 完全 ¶

多项式时间归约 A ≤_P B：A 的实例映射到 B 的实例，保持答案（yes⇔yes）。
NP 完全：∈ NP 且 NP 中所有问题可多项式归约到它（语言框架：引理 34.3，定理 34.4）。
第一个 NP 完全问题：电路可满足性（CIRCUIT-SAT）——Cook-Levin 思想：NP 语言的多项式验证器可编码为电路，故 NP ⊆ P 当且仅当 CIRCUIT-SAT ∈ P。

34.4 NP 完全性证明 ¶

标准流程：证明 L ∈ NP；选已知 NP 完全问题 A，构造 A ≤_P L（归约）。
公式可满足性 SAT ≤_P（从电路编码）；3-CNF-SAT（用”真值表/布尔公式等价”把 SAT 转为 3-CNF）。
归约设计策略（34.5.6）：从一般到特殊、利用原问题结构、找特例、设计构造部件（gadget）。

34.5 经典 NP 完全问题（归约链）¶

CLIQUE（来自 3-CNF-SAT）；
VERTEX-COVER（来自 CLIQUE）；
HAMILTONIAN-CYCLE（来自 VERTEX-COVER，部件构造）；
TSP（来自 HAM-CYCLE，加边权技巧）；
SUBSET-SUM（来自 3-CNF-SAT）。
这些归约展示了”从一个结构到另一个结构”的典型手法，是学习归约设计的样板。

34 小结 ¶

P、NP、NP 完全、归约、验证与语言、电路-SAT→SAT→3-CNF→（团/顶点覆盖/哈密顿/TSP/子集和）；”看起来像 NP 难”的判断力与归约构造能力是本章核心技能

第 35 章近似算法（Approximation Algorithms）¶

教学目标 ¶

掌握近似比与近似方案（PTAS/FPTAS）的定义
掌握几个经典问题的近似算法：顶点覆盖、TSP、集合覆盖、MAX-3-CNF、子集和
理解”NP 难优化问题如何妥协求近优”

35.0 性能比 ¶

近似比 ρ(n)：max{C/C, C/C} ≤ ρ(n)（C 算法解，C* 最优解）；最小化/最大化统一。
近似方案：对任意 ε>0 为 (1+ε)-近似；
PTAS：固定 ε 时多项式时间；
FPTAS：时间多项式于 n 与 1/ε（如 O((1/ε)² n³)）。

35.1 顶点覆盖（vertex cover）¶

贪心/极大匹配近似：选一条未覆盖边，两点都入覆盖——近似比 2（定理 35.1）。
证明思想：任一匹配边两顶点被覆盖，极大匹配大小 ≤ 最优 ≤ 2·匹配大小。

35.2 旅行商问题（TSP）¶

三角不等式 TSP：由 MST 深度优先遍历 + 跳跃（MST 双遍历）得近似比 2（定理 35.2）。
一般 TSP：若 P≠NP，则不存在任何常数比 ρ 近似（定理 35.3，把 HAM-CYCLE 归约构造）。
结论：近似算法依赖问题结构（三角不等式）——坏结构问题不可近似。

35.3 集合覆盖（set cover）¶

贪心算法：每次选覆盖最多未覆盖元素的新集合；
分析：代价 ≤ ln n 倍最优（对数近似比，定理 35.4）——利用分配/双计数证明。
集合覆盖是最小化的典型：比 2 更差但仍有界（且 (1−ε)ln n 近似不可改善，NP 假设下）。

35.4 随机化与线性规划 ¶

MAX-3-CNF 可满足性：随机给每个变量独立赋真值——期望满足子句 ≥ 7/8，即 8/7-近似（定理 35.5）。
加权顶点覆盖：用 LP 松弛（变量 0≤x≤1 放松整数约束）→ 取 x≥1/2 圆整 → 2-近似（定理 35.6）。
展示了随机化与线性规划两种现代近似工具。

35.5 子集和（subset-sum）¶

指数精确算法（枚举合并表）；
FPTAS：缩放/修剪（truncation + rounding 去掉多余子集）→ 对任何 ε 得到 (1+ε)-近似，时间多项式于 n 与 1/ε（定理 35.7）。
例：0-1 背包的近似模式（习题）。

35 小结 ¶

近似比/PTAS/FPTAS、2-顶点覆盖、2-TSP（三角不等式）、对数集合覆盖、8/7-MAX-3SAT、LP 松弛与随机化、子集和 FPTAS；近似算法是在 NP 难问题面前”工程可得性”的系统方法

结语与学习路径建议 ¶

全课程知识框架 ¶

分析工具：渐近记号（3）、递归式（4）、概率/随机（5）、摊还（16）
排序与顺序统计：插入/归并（2）、堆（6）、快排（7）、线性排序（8）、选择（9）
数据结构：基础结构（10）、哈希（11）、BST（12）、红黑树（13）、B 树（18）、并查集（19）、扩充结构（17）
设计技术：分治（2/4）、动态规划（14）、贪心（15）、随机化（5/7/9）
图算法：BFS/DFS/拓扑/SCC（20）、MST（21）、最短路（22–23）、最大流（24）、匹配（25）
高级主题：并行（26）、在线（27）、矩阵（28）、LP（29）、FFT（30）、数论（31）、字符串（32）、ML（33）
复杂度与现代：NP 完全（34）、近似（35）

掌握程度自检建议 ¶

必会证明：循环不变式（2）、递归式主定理（4）、BFS/DFS 正确性（20）、Dijkstra/Bellman-Ford 正确性（22）、max-flow min-cut（24）、贪心正确性（15）、DP 最优子结构（14）、NP 归约（34）。
必会手算：插入/归并/堆/快排过程、红黑树插入删除、Floyd-Warshall 表、Ford-Fulkerson 增广、KMP 前缀函数、FFT 蝶形。
复杂度表（核心记忆）：
| 算法 | 时间复杂度 |
|—|—|
| 插入排序 | O(n²) |
| 归并/堆/快排（期望） | O(n log n) |
| 计数/基数/桶（条件） | O(n) |
| 选择（期望/最坏） | O(n) |
| 哈希 | 期望 O(1) |
| 红黑树/B 树 | O(log n) |
| BFS/DFS/拓扑/SCC | O(V+E) |
| Prim/Kruskal | O(E log V) |
| Dijkstra | O(E log V) |
| Bellman-Ford | O(VE) |
| Floyd-Warshall | O(n³) |
| Johnson | O(VE + V² log V) |
| Ford-Fulkerson | O(E·f*) |
| Edmonds-Karp | O(VE²) |
| Hopcroft-Karp | O(√V·E) |
| KMP/Rabin-Karp | O(n+m) |
| FFT | O(n log n) |
| Euclid | O(log n) |
| 并查集（两个启发式） | O(m α(n)) |

教授寄语：算法导论的核心不是背算法，而是培养三种能力——严谨的证明能力（为什么正确）、精确的分析能力（为什么高效）、建模的能力（把实际问题转成已知算法问题）。每章学完后，建议亲手实现关键算法并用随机数据对拍验证，再回归本章”必须掌握的关键词”自测。

（本文档根据各章节 full.md 材料整理，覆盖第 1–35 章全部学习要点。）

AI生成