《算法导论》四层知识地图与高频易错点复习指南

简介：《算法导论》英文原版（第三版）PDF 教材面向计算机专业学生、考研与算法竞赛备赛者，以及需要补齐算法基础的开发者，用于系统学习算法设计与分析。全书由 Cormen 等四位作者合著，从插入排序、分治法、概率分析与随机化算法讲起，逐步延伸到堆排序、快速排序、线性时间排序、哈希表与二叉搜索树等数据结构，再进入动态规划、贪心算法、回溯法与图算法等进阶主题，并配以渐进记号、递归式求解、摊还分析等数学工具。该版本为 MIT Press 2009 年第三版，英文表述严谨，术语与习题贴近国际课程与英文面试场景。压缩包内共 1 个文件，为 pdf 格式的教材正文，体积约 5.12MB，轻量便携，便于在电脑、平板与手机上随时查阅，也可配合检索工具快速定位章节定理、伪代码与习题。已有 640 人在线学习下载，适合作为课程配套精读材料或长期案头参考书。

1. 知识地图：一本千页教材其实只有四层

第一次翻开《算法导论》的人，十有八九会被目录吓退：34 章、8 个部分、外加四个数学附录，排版密得像字典。可把它当成复习笔记重新梳理一遍就会发现，这本书的组织逻辑并不是按算法罗列，而是按分析工具分层——先给你一套描述代价的语言，再给你一组可复用的设计套路，最后才是各应用领域的实例。第一部分和附录是工具层，讲渐进记号、递归式、概率、求和；第三、第五部分是结构层，讲哈希、红黑树、B 树、斐波那契堆；第四部分是范式层，动态规划、贪心、摊还分析三大件；第六、第七部分是应用层，图算法、矩阵运算、数论、字符串、计算几何、NP 完全性。第三版全书 34 章、957 道练习、158 个问题、244 幅插图，真正适合一轮啃完的其实只有二十来章，其余都是查阅型内容。准备考研专业课、研究生算法课，或者想补数学功底的自学者，都可以按这个四层结构来安排顺序，而不是从第 1 页硬翻到最后一页。

2. 基础层：渐进记号、递归式与分治法的复习骨架

这一层是整本书里唯一不能跳的部分。后面所有算法分析，本质上都是把一段代码翻译成一个递归式，再用这里的工具求出一个渐进界。复习时最容易犯的错，是把这一部分当成数学课背公式，结果到排序、图算法章节里连“为什么这里是 Θ 而不是 O”都说不清。正确的做法是把五个记号、三种解递归式的方法、分治三步走连成一条线：记号负责描述代价，递归式负责建模代价，分治法负责产生递归式。

2.1 渐进记号：五个符号的边界感

很多人能背出 O 是上界、Ω 是下界，一到写题就全部写成 O。梳理下来会发现，失分点几乎都集中在“该用 Θ 的地方用了 O”。Θ 是紧确界，只有当上界和下界同阶时才成立，2n² = O(n³)成立，但2n² = Θ(n³)是错的。o 和 ω 则是“严格小于/大于”，区别在于对任意常数 c 都成立，而 O 只需要存在一个常数。

还有两个常被忽略的细节：对数底数不影响渐进阶，log₂n 和 ln n 只差常数因子；指数与多项式的分界线在 nᵏ 与 cⁿ 之间，任何多项式都小于任何底数大于 1 的指数。常见增长率的完整排序是 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!，考试里判断两个函数谁增长快，先往这张表上靠就行。

2.2 递归式三法：代入、递归树与主定理

代入法是先猜答案再用归纳法证明，考场上最不推荐，因为猜不出来就卡死；递归树法适合用来“找感觉”，画出几层之后观察每层代价是等比还是等差；主定理是主力工具，但它的适用面比想象中窄，只处理T(n) = aT(n/b) + f(n)这种子问题规模严格等分的形式。

主定理的核心是比较 f(n) 与临界函数 n^(log_b a) 的量级，分三种情况：

第三情况里那个af(n/b) ≤ cf(n)叫正则条件，c < 1，作用是保证递归树每层代价几何递减，否则求和会发散。这是最容易被跳过的一行，跳过之后的结论往往对不上。

递归树法可以用几行代码把每层代价展开，直观看到收敛过程：

def recursion_tree_cost(n, a=3, b=4): """估算 T(n) = a*T(n/b) + n^2 的递归树总代价，逐层打印""" total = 0.0 level = 0 while n >= 1: level_cost = (a ** level) * (n ** 2) # 本层子问题个数 × 单个子问题代价 total += level_cost print(f"第 {level} 层：子问题 {a**level} 个，单代价 {n**2:.2f}，层代价 {level_cost:.2f}") n /= b level += 1 return total recursion_tree_cost(64) # a/b^2 = 3/16 < 1，层代价几何递减，总和为 O(n^2)

这段代码里a ** level是第 k 层的子问题数量，n ** 2是单个子问题在那一层的非递归代价。因为 a/b² = 3/16 小于 1，层代价构成一个公比小于 1 的等比数列，求和收敛到常数倍的首项，所以整体是 Θ(n²)。把 a 改成 4、b 改成 2，公比变成 1，每层代价相同，结果就变成 Θ(n² log n)——这就是主定理第二种情况的来源。改动这两个参数跑一遍，比背三条结论管用得多。

2.3 分治法：合并代价才是隐藏主角

分治三步是分解、解决、合并，教材里所有分治例子都在强调第三步。归并排序的合并是 Θ(n)，所以T(n) = 2T(n/2) + Θ(n)落到主定理第二情况，得 Θ(n log n)；二分查找的“合并”是 Θ(1)，于是T(n) = T(n/2) + Θ(1)得 Θ(log n)；Strassen 把 8 次矩阵乘法压到 7 次，递归式变成T(n) = 7T(n/2) + Θ(n²)，临界指数 log₂7 ≈ 2.81，f(n) 落在第一种情况，结果是 Θ(n^2.81)，比朴素法的 Θ(n³) 好。

最大子数组问题值得单独拎出来复习：它把数组从中点切开，最大子数组要么全在左半、要么全在右半、要么跨越中点。前两种递归解决，第三种用一次线性扫描从中点向两侧扩展求最大后缀和与最大前缀和。这个“跨越中点”的分支是整道题的全部难点，也是最容易在考场上漏写的一步。复习时不要只记结论，要能手写出那个从 mid 向两边扫的双指针过程，否则换一个变体（比如求最大子数组的起止下标）就写不出来。

2.4 概率分析与随机化：指示器随机变量是万能钥匙

概率分析假设输入服从某种分布，随机化算法则主动引入随机性，使得对任意输入都有好的期望性能。这两者在教材里被放在同一章，但考试问法完全不同：前者问“期望是多少”，后者问“最坏情况下还是不是这个界”。

整章最有价值的一句话是期望的线性性：E[X₁ + X₂ + … + Xₙ] = E[X₁] + … + E[Xₙ]，不要求变量独立。雇佣问题里把“雇佣次数”拆成每个候选人是否比前面所有人都强的指示器变量，问题立刻从“分析复杂事件”变成“n 个独立概率求和”。随机化快排的期望比较次数是 O(n log n)，用的也是同一招：把总比较次数拆成每一对元素是否被比较的指示器，再对概率求和。

血泪经验是，很多人在这里死记“期望等于概率乘以次数”，但一到指示器变量就不会设。补的方法很朴素：凡是题目里出现“次数”“个数”“有多少个”这类计数词，先想能不能拆成一堆 0/1 变量的和，拆得动，题目就过半了。

3. 排序与数据结构：从堆排序到红黑树的考点串联

排序和数据结构在教材里分属第二、第三部分，但复习时可以合成一条线，因为它们共享同一个问题：如何在维持某种结构性不变量（堆序、哈希分布、红黑性质）的前提下，把操作代价压到对数级。这条线串起来是：比较排序的下界告诉我们 n log n 是天花板，堆和快排告诉我们怎么达到它，线性时间排序告诉我们什么条件下能突破它，哈希表和平衡树告诉我们怎么在动态集合上维持它。

3.1 比较排序的下界与三种线性时间排序

决策树模型是这一节的唯一考点：n 个元素有 n! 种排列，任何比较排序的决策树至少有 n! 个叶子，高度至少 log₂(n!) = Ω(n log n)。这个证明链条短但每一步都要能说清——为什么叶子对应一种排列、为什么二叉树高度下界是 log 叶子数、为什么 log(n!) 用斯特林公式展开后是 Θ(n log n)。

三种线性时间排序的适用条件差异极大，做选择填空题时经常被拿来互相干扰：

最容易错的是基数排序的“稳定”要求：它按位从低位到高位排，每一位必须用稳定排序（通常就是计数排序），否则高位排完低位信息就丢了。还有一点，基数排序的复杂度写成 Θ(d(n+k)) 而不是 Θ(n)，d 是位数，当 d 是常数时才退化成线性。

3.2 堆：建堆为什么是 O(n) 而不是 O(n log n)

堆排序本身很简单，真正的考点在 BUILD-MAX-HEAP 的复杂度。很多人凭直觉认为 n 次调用 MAX-HEAPIFY、每次 O(log n)，总共 O(n log n)。正确的算法是：高度为 h 的节点最多有 ⌈n/2^(h+1)⌉ 个，每个节点下沉代价 O(h)，求和得到 Σ h/2^h = O(1) 量级的常数，最终是 O(n)。这个求和的技巧（用无穷级数收敛）在摊还分析里还会再出现一次。

复习时不要只背“建堆 O(n)”，要能说出“为什么底层节点多但下沉距离短、顶层节点下沉距离长但数量少”这个抵消关系。另外，堆排序虽然最坏情况 O(n log n)、原地排序，但实际常数比快排大、缓存不友好，工程里很少直接用，优先队列（最大堆、最小堆）才是堆结构真正的价值所在。

3.3 哈希表：链接法与开放寻址的分工

哈希表的核心指标是装载因子 α = n/m，n 是元素数、m 是槽位数。链接法下，一次成功查找的期望代价是 Θ(1 + α)，不成功查找也是 Θ(1 + α)，前提是简单均匀哈希假设。开放寻址把元素直接存在表里，省掉指针开销，但 α 必须小于 1，查找的期望探测次数是 1/(1−α)，α 接近 1 时代价爆炸。

三种探测方式要能区分清楚：线性探测会出现一次聚集，连续被占的槽连成一片，越连越长；二次探测用h(k, i) = (h'(k) + c₁i + c₂i²) mod m，缓解一次聚集但可能出现二次聚集；双重哈希用两个哈希函数h(k, i) = (h₁(k) + i·h₂(k)) mod m，效果最好但要求 m 与 h₂(k) 互质。

还有一个绝大多数笔记里不会写、但实现时必然踩的坑：开放寻址的删除不能把槽直接置空，否则会截断后面元素的探测链，导致本来存在的元素查不到。标准做法是引入 DELETED 标记，查找时遇到 DELETED 继续往后探，插入时可以复用 DELETED 槽。这条在教材的习题里出现过，工程实现里是必修项。

3.4 二叉搜索树与红黑树：五条性质与旋转

二叉搜索树的基本操作代价是 O(h)，h 是树高，随机构造时 h = O(log n)，但有序插入会退化成链表，h = n。红黑树就是用来把 h 锁死在 O(log n) 的：每个节点有红黑一色，根黑、叶（NIL）黑、红节点的两个子节点必黑、从任一节点到其所有后代叶子的简单路径上黑节点数相同（黑高）。由这几条可以推出“最长路径不超过最短路径的两倍”，进而 h ≤ 2log₂(n+1)。

旋转是唯一需要手写的操作，LEFT-ROTATE 的关键是把 y 的左子树挂到 x 的右孩子上，再让 x 成为 y 的左孩子：

class Node: __slots__ = ("key", "color", "left", "right", "parent") def __init__(self, key, color="R"): self.key, self.color = key, color self.left = self.right = self.parent = None def left_rotate(root, x): """左旋：x 的右孩子 y 上浮，x 下沉为 y 的左孩子""" y = x.right x.right = y.left # y 的左子树变成 x 的右子树 if y.left: y.left.parent = x y.parent = x.parent if x.parent is None: # x 原来是根，y 接任根 root = y elif x is x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y return root

这段代码里最容易写错的是指针更新顺序：先处理 y 的左子树移交，再处理 x 的父节点指向 y，最后才是 y 和 x 的角色对调。顺序一乱就会把 y.left 覆盖掉，或者让 x.parent 指向错误节点。

插入的修复分三种情况：叔叔节点是红色时只需变色并上移两层；叔叔是黑色且当前节点是右孩子时先左旋转成第三种情况；叔叔是黑色且当前节点是左孩子时变色加右旋。删除的修复有四种情况，核心是处理“双黑”节点的额外黑高，考试里通常不会要求全写，但至少要能画出四种情况的示意图。

3.5 B 树与并查集：两个工程味最重的结构

B 树是为磁盘存储设计的，最小度 t 意味着每个非根节点至少有 t−1 个关键字、至多 2t−1 个，树高是 O(log_t n)。关键操作是分裂：节点满了就把中间关键字上移，左右各成一半。教材里那个“沿路径向下时提前分裂满节点”的技巧，是为了避免回溯，实现时一定要按这个顺序写。

并查集虽然在教材里叫“不相交集合的数据结构”，但它其实是图算法章节的前置工具。按秩合并加路径压缩的组合复杂度是 O(m α(n))，α(n) 是反阿克曼函数，实际取值不超过 4，几乎所有工程实现都把它当成 O(1)。这两条优化单独用都到不了这个界，必须同时用，这一点经常被忽略。

提示：红黑树和 B 树的复习不要停在性质列表，要能在纸上把一次插入的旋转-变色过程完整画出来；并查集一定要手写 FIND-SET 的路径压缩两行递归。

4. 设计范式与图算法：从动态规划到最大流的一条主线

设计范式与图算法在目录上相隔很远，实际上共用同一套思维：动态规划给的是“子问题重叠时如何避免重复计算”，贪心给的是“局部最优何时能推出全局最优”，摊还给的是“单次操作贵但总体便宜时怎么算账”。图算法恰好是这三种思想最集中的试验田——Dijkstra 是贪心，Floyd-Warshall 是动态规划，并查集的复杂度分析是摊还。把两者放在一起复习，记忆负担会小很多。

4.1 动态规划：四步法与三个经典模型

教材没有给出统一模板，但从钢条切割、矩阵链乘、最长公共子序列、最优二叉搜索树四个例子里可以抽出稳定的四步：刻画最优解的结构（这一步决定状态怎么定义）、递归地定义最优值（写出状态转移方程）、自底向上计算最优值（决定循环顺序）、用记录表构造最优解（回溯或额外数组）。

状态定义是最难的一步，也是最容易出岔子的地方。钢条切割的状态是“长度 i 的最大收益”，矩阵链乘的状态是“从 i 到 j 的链的最小乘法次数”，LCS 的状态是“两个前缀的最长公共子序列长度”。这三种状态的共同点是它们都是原问题的“前缀”或“区间”形式，而不是任意的子集。凡是状态定义里出现指数级维度（比如旅行商问题的状态压缩），基本就说明它不是教材这一章的重点。

以 LCS 为例，转移方程的代码只有几行，但要理解为什么从末尾往前比较：

def lcs_length(x, y): """返回最长公共子序列的长度，时间复杂度 O(m*n)，空间 O(m*n)""" m, n = len(x), len(y) c = [[0] * (n + 1) for _ in range(m + 1)] # c[i][j] 存 x[:i] 与 y[:j] 的 LCS 长度 for i in range(1, m + 1): for j in range(1, n + 1): if x[i - 1] == y[j - 1]: c[i][j] = c[i - 1][j - 1] + 1 # 末尾相同，接上 else: c[i][j] = max(c[i - 1][j], c[i][j - 1]) # 末尾不同，砍掉一边 return c[m][n]

c[i][j]的下标含义要记牢：它对应的是x的前 i 个字符与y的前 j 个字符。循环从 1 开始、比较x[i-1]与y[j-1]，这个错位是手写代码时最高频的越界来源。空间复杂度可以优化到 O(min(m,n)) 只保留两行，但优化之后就无法回溯出具体序列了，做题时先问清楚题目要长度还是要序列。

4.2 贪心：什么条件下局部最优能推出全局最优

贪心算法有两个必要条件：贪心选择性质（每一步的最优选择能扩展成某个全局最优解）和最优子结构。活动选择问题按结束时间排序后依次选取，Huffman 编码每次合并频率最小的两个节点，这两个例子的证明套路不同——前者用交换论证（把最优解里的第一个活动换成贪心选的那个，解不会变差），后者用拟阵或树形结构的归纳。

最容易混的是 0-1 背包与分数背包。分数背包可以贪心，按单位重量价值排序即可；0-1 背包不能贪心，必须动态规划。区别在于分数背包允许取一部分，贪心的每一次选择都不会让剩余问题变得更差；0-1 背包一旦选了某个物品，剩余容量和物品组合发生变化，局部最优可能堵死全局最优。这个对比几乎是必考选择题。

4.3 摊还分析：三种方法各自能回答什么问题

摊还分析回答的是“一串操作的总代价除以操作次数”，不是“平均情况”。它不涉及概率，是最坏情况下的平均。三种方法的分工要清楚：聚合分析把 n 次操作的总代价直接算出来除以 n；记账法给每种操作定一个摊还代价，贵的操作提前“存钱”；势能法定义一个势函数，用势能变化来平衡代价。

动态表扩容是标准例子：插入时表满了就扩一倍，单次插入最坏 O(n)，但 n 次插入的总代价是 O(n)，摊还每次 O(1)。用记账法理解最直观——每次插入收 3 块钱，1 块用于自己，2 块存起来给将来搬移用。三种方法给出的结论一样，但考试可能指定用某一种，所以三种都要会写。

4.4 图的表示与遍历：BFS、DFS、拓扑排序与强连通分量

邻接表适合稀疏图，空间 O(V+E)；邻接矩阵适合稠密图或需要快速判断边存在性，空间 O(V²)。这个选择直接影响后面所有图算法的复杂度写法，考试里经常要求“分别写出两种表示下的复杂度”。

BFS 用队列，能得到无权图的最短路径（边数最少），同时给每个节点标出层数；DFS 用递归或栈，产生时间戳 d[u] 和 f[u]，这两个时间戳是后面所有高级算法的基石。拓扑排序可以用 DFS 的完成时间逆序，也可以用入度为零的队列（Kahn 算法），后者更容易手写。强连通分量用 Kosaraju 两遍 DFS（第二遍在转置图上按完成时间逆序），或者 Tarjan 一遍 DFS 加 low 值。

这里最容易漏的是 DFS 的边分类：树边、后向边、前向边、横叉边。有向图里存在后向边等价于存在环，这个判定在拓扑排序和强连通分量里都用得上。

4.5 最短路径：四套算法怎么选

最短路径是图算法里考得最密的一块，四套算法各有边界，选错就扣分：

Dijkstra 的正确性依赖一个关键性质：一旦节点被取出优先队列，它的最短距离就已确定。这个性质在存在负权边时失效，因为后面可能通过一个负权边把已确定的距离改小。很多人记成“Dijkstra 不能有负权环”，其实只要有一条负权边就可能出错，负环只是更极端的情况。

Johnson 算法值得单独记一笔：它先用 Bellman-Ford 算一组势函数 h(v)，把每条边重赋权为w(u,v) + h(u) − h(v)，保证非负且不改变最短路径，然后对每个源跑一次 Dijkstra。这个“重赋权”技巧是它区别于“对每个源跑 Bellman-Ford”的全部价值。

4.6 最大流与二分匹配：残量网络是核心

最大流问题的三个概念要分清：流网络（容量、流量、流量守恒）、残量网络（正向残量 + 反向残量）、增广路径。Ford-Fulkerson 方法是框架而不是具体算法，它只说“不断找增广路径”，复杂度取决于怎么找。用 BFS 找最短增广路就是 Edmonds-Karp，复杂度 O(VE²)；用高度函数推进就是推送-重贴标签，复杂度更好但实现复杂。

最小割最大流定理是这一章的压轴：一个流是最大流，当且仅当残量网络中没有增广路径，当且仅当存在一个割使得流量等于容量。这个定理把“求最大流”和“求最小割”变成同一个问题，很多应用题的建模思路就藏在这里。

最大二分匹配可以规约成最大流：左侧加源点、右侧加汇点，所有边容量为 1，最大流的值就是最大匹配数。这里的建模细节（源点到左侧容量 1、右侧到汇点容量 1、中间边容量 1 或无穷）经常被写错，容量设错结果就会偏大。

4.7 NP 完全性与近似算法：归约的方向不能反

P 是多项式时间可解，NP 是多项式时间可验证，NPC 是 NP 中最难的一类（NP 中所有问题都能多项式归约到它），NP-hard 是不要求在 NP 里的那类。判断一个问题是 NPC，标准流程是：先证明它属于 NP（给出一个多项式时间的验证算法），再把一个已知的 NPC 问题归约到它。

归约方向是最容易搞反的地方：要证明新问题 X 是 NPC，是把已知 NPC 问题 A 归约到 X（A ≤ₚ X），不是把 X 归约到 A。方向反了只能说明 X 不比 A 难，什么也证明不了。教材里第一个 NPC 问题是电路可满足性，之后通过归约链推出 SAT、3-SAT、团、顶点覆盖、哈密顿回路、旅行商等一系列问题。

近似算法部分重点是两个：顶点覆盖的 2-近似（每次取一条边，把两个端点都放进解里，代价最多是最优解的两倍），以及满足三角不等式的旅行商问题的 2-近似（先求最小生成树，再对树做前序遍历）。这两个证明都不长，但“为什么是 2 倍”的论证要能自己写出来。

5. 易漏点与易错点：那些看起来会、一写就错的地方

这一章是整份笔记里最该反复看的部分。前面几章按知识模块铺开，这一章按“错误类型”重新切一遍。梳理下来会发现，真正拉开差距的不是会不会某个算法，而是这些边界条件记没记住。

5.1 记号与证明里的坑

易漏点一：O 与 Θ 混用。为什么漏：平时写代码注释习惯用 Big-O 表示“大概这个量级”，久而久之把 O 当成“等于”用。怎么补：做题时强制问自己一句“下界是多少”，能同时给出上下界且同阶，才写 Θ；只能给上界，写 O 并注明“上界”。排序下界那道题写Ω(n log n)而不是O(n log n)，这一分就保住了。

易漏点二：主定理漏掉正则条件。为什么漏：三种情况的结论太好背，第三情况的附加条件藏在定理陈述的后半句里。怎么补：每次用第三情况之前，先验证af(n/b) ≤ cf(n)对某个 c < 1 成立。典型反例是T(n) = 2T(n/2) + n log n，f(n) 与 n^(log_b a) 只差一个 log 因子，既不满足第二情况的 Θ 相等，也不满足第一、第三情况的“多项式差距”，属于主定理的缝隙，只能用递归树单独算，结果是 Θ(n log²n)。

易漏点三：摊还当平均。为什么漏：中文里“摊还”“平均”读起来很像。怎么补：记住摊还分析里没有任何概率假设，它算的是最坏情况下 n 次操作的总代价除以 n。随机化快排的 O(n log n) 是期望，动态表插入的 O(1) 是摊还，两者不能互换说法。

5.2 数据结构实现里的坑

易漏点四：开放寻址的删除直接置空。为什么漏：链地址法里删除就是摘链，直觉上开放寻址也应该“删掉就是空”。怎么补：置空会截断探测链，导致后面本应能找到的元素查不到。正确做法是打 DELETED 墓碑标记：查找遇到 DELETED 继续往后探，插入可以复用 DELETED 槽。这个改动只多一个状态位，但漏了就是查找失败。

易漏点五：红黑树删除的双黑处理。为什么漏：插入的三种情况背得很熟，删除的四种情况太长就跳过。怎么补：抓住核心——删除黑节点会让某条路径黑高少 1，产生“双黑”节点，修复的目标是把这多出来的一重黑往上推或消掉。四种情况按兄弟节点的颜色和兄弟孩子的颜色分类，画一遍图比背文字快。至少要做到给定一棵树和删除位置，能判断属于哪种情况、旋转几次。

易漏点六：建堆复杂度写成 O(n log n)。为什么漏：n 次调用 MAX-HEAPIFY 的直觉太强。怎么补：记住那个求和Σ_{h=0}^{⌊log n⌋} ⌈n/2^(h+1)⌉ · O(h) = O(n)，并理解它的物理含义——大部分节点在底层，下沉距离短；顶层节点少，下沉距离长，两者抵消。能用一句话说清这个抵消，就不会再写错。

5.3 设计与图算法里的坑

易漏点七：Dijkstra 用在负权图上。为什么漏：平时刷题遇到的图基本都是正权，负权是教材里的特例。怎么补：记一个反例就行——三个点 A、B、C，A→B 权 2，A→C 权 5，C→B 权 −4。Dijkstra 先确定 B 的距离为 2，之后不会再更新，但实际最短路是 A→C→B = 1。只要图里有负权边，就换 Bellman-Ford；有负环，Bellman-Ford 第 V 次迭代还能松弛就报负环。

易漏点八：最大流建模时容量设错。为什么漏：二分匹配的建图看起来简单，源点到左侧、右侧到汇点、中间连边，三步都设 1 好像对称。怎么补：中间边的容量要看题目允不允许一个左节点匹配多个右节点。标准二分匹配里中间边容量设 1（或无穷，因为左侧出边和右侧入边已经限流为 1），但如果是“一个任务可以由多人协作完成”的变体，中间边容量就要按需求改。建模题先写清楚每条边的物理含义，再定容量。

易漏点九：NP 完全性归约方向写反。为什么漏：A ≤ₚ B这个记号读作“A 归约到 B”，但很多人理解成“A 比 B 难”。怎么补：记住归约的方向是“把已知难的问题转成待证明的问题”，转得过去说明待证明的问题至少一样难。写证明时第一句就写“下面把已知的 NPC 问题 A 归约到 X”，方向锁死再往下写。

6. 复习清单：三遍法加上一张自查表

把前面五章压缩成可执行的三轮，比从头再读一遍有效得多。

第一轮打地基，只覆盖第 2 章到第 4 章的分析工具部分：渐进记号五个符号能互相翻译，主定理三种情况能判断并说出正则条件，递归树能画三层并求和，指示器随机变量能独立设出来。这一轮的目标不是做难题，而是拿到“能把算法翻译成递归式”的能力。检验标准很直接：随便给一段分治代码，能在两分钟内写出递归式并说出渐进界。

第二轮按结构走，排序、哈希、平衡树、并查集、图算法各挑两个代表实现手写一遍。手写不是抄，是关掉书从空文件开始写，写完再对照。红黑树插入、并查集路径压缩、Dijkstra 堆优化、Ford-Fulkerson 这四段是分水岭，能默写出来，说明结构层过关了。

第三轮只做错题和易漏点，把第 5 章那九条逐条对着自己的笔记检查一遍，每条问三个问题：我能不能说出它为什么错、能不能举一个反例、能不能写出正确版本。三条都答得上就划掉，答不上就回到对应章节补。

时间分配上，第一轮大约占四成，第二轮四成，第三轮两成。第一轮拖太久是常见病，因为它最像“在上数学课”，容易产生学会了的安全感，但真正的分在第二轮的手写和第三轮的反例上。

还有一个具体技巧：把第 5 章的九条易漏点做成九张卡片，正面写错误说法（比如“Dijkstra 可以处理负权，只要没有负环”），背面写反例和正确结论。每天抽五分钟随机翻三张，两周之后这些边界条件会变成条件反射。这比再刷十道同类型题管用，因为题目会变，错误类型不会变。

从那以后我每次复习这类大部头教材，都强制先画知识地图、再列易漏点卡片、最后才回头补细节，顺序一反就会陷入“读了很多页但说不清重点”的状态。这份笔记是按第三版英文原版的章节结构梳理的，34 章里真正需要精读的其实不到一半，其余按图索骥即可；如果你手头还没有这份 PDF，按文末方式取用，对照原文把每章末的练习题过一遍，效果会比单纯读正文好得多。希望帮到你。

本文还有配套的精品资源，点击获取