简介：《算法导论》第三版英文原版以PDF电子书形式呈现，面向计算机专业本科生、研究生及准备算法岗面试与技术深造的读者，用于系统搭建算法设计与分析的知识框架。压缩包内仅含1个PDF文件，体积约5.12MB，采用MIT Press原版排版，目录、索引与参考文献齐全，便于按章节定位和全文检索。全书34章由基础篇、排序与顺序统计、数据结构、高级设计与分析技术、图算法等模块构成，涉及插入排序、堆排序、快速排序、散列表、二叉搜索树、分治法、动态规划、贪心算法、摊还分析、最短路径与最大流等内容；书中配有伪代码、正确性证明与章末习题，可对照课程进度精读，也可作为刷题、科研时查阅术语与证明思路的案头参考。英文原版保留了asymptotic notation等标准表述，适合需要衔接英文文献与原始定义的读者。目前已有640人学习。
1. 知识地图：34 章与 4 个附录如何拼成一张算法地图
把《算法导论》第三版英文原版摊开，劝退人的不是红黑树，而是目录：八个部分、34 章、4 个数学附录，957 道练习加 158 个问题，翻到附录 D 还有矩阵。可这张目录本身就是一张分层地图：第 1～5 章给分析工具，包括算法的角色、渐近记号、递归式、概率分析与随机化；第 6～9 章把工具用在排序与顺序统计量上；第 10～14 章和第 18～21 章讲结构，从栈队列一路到 B 树、斐波那契堆、vEB 树与并查集；第 15～17 章讲设计范式，动态规划、贪心、摊还分析；第 22～26 章让结构和范式在图上合流；第 27～35 章是专题，矩阵、线性规划、FFT、数论、串匹配、计算几何、NP 完全性、近似算法；附录 A～D 补求和、集合、计数与概率、矩阵。
整本书反复只回答两个问题：这个算法跑多快，凭什么说它对。算法分析与设计的所有知识点，都能挂到「工具 → 结构 → 范式 → 图与难解性」这四层上。
2. 分析工具与排序：渐近记号、递归式、堆与快排的复习重点
2.1 渐近记号：O、Ω、Θ 各有边界，别记反
分析工具是整本书的基础，也是复习时最容易被跳过的部分。很多人直接翻到快排，看两页觉得「懂了」，做课后练习却连 T(n)=2T(n/2)+n 都推不完整。问题不在排序，而在于增长函数那套语言没建立起来。渐近记号描述的是输入规模趋于无穷时增长率的量级，常数因子和低阶项一律丢掉，所以 3n²+100n+7 和 n² 是同一档。
| 记号 | 数学含义 | 一句话记法 | 常见误用 |
|---|---|---|---|
| O | 存在 c、n₀ 使 0 ≤ f(n) ≤ c·g(n) | 渐近上界，不要求紧 | 把 O 当成「最坏情况」 |
| Ω | 存在 c、n₀ 使 0 ≤ c·g(n) ≤ f(n) | 渐近下界 | 和 O 混着写同一句话 |
| Θ | 同时是 O 和 Ω | 紧确界，量级刚好 | 该用 Θ 的地方写了 O |
| o | 对任意 c 都成立 f(n) < c·g(n) | 严格上界，类似 < | 当作 O 的别名 |
| ω | 对任意 c 都成立 f(n) > c·g(n) | 严格下界，类似 > | 当作 Ω 的别名 |
增长阶从低到高：1 < lg n < √n < n < n lg n < n² < n³ < 2ⁿ < n!。教材约定 lg n 就是以 2 为底，ln 才是自然对数，这个约定在信息论下界和决策树高度那几处会直接决定答案对不对。另外还有迭代对数 lg* n，它增长极慢，在并查集的摊还界 α(n) 里会再次遇到。
有一个反直觉的点值得记牢：O 记号和「最好/最坏情况」没有对应关系。最坏情况是一种分析场景，O 是一种上界记号。说「快排最坏情况是 Θ(n²)」是精确说法，说「快排最坏情况是 O(n²)」也没错但不紧，说「O 就是最坏情况」则直接错。复习时看到题目要求「紧确界」，就要自觉写 Θ。
2.2 递归式求解：代入法、递归树与主定理的三条路
分治算法的运行时间天然是递归式，第 4 章给出的三件套必须会手推。代入法是猜一个界再数学归纳验证，难在猜；递归树是把每层代价画出来求和，直观但需要证明；主定理是给 T(n) = aT(n/b) + f(n) 形式的公式化结论，考试命中率最高，也最容易用错。
| 情况 | 条件（与 n^(log_b a) 比较） | 结论 |
|---|---|---|
| 1 | f(n) = O(n^(log_b a − ε))，ε > 0 | T(n) = Θ(n^(log_b a)) |
| 2 | f(n) = Θ(n^(log_b a)) | T(n) = Θ(n^(log_b a) · lg n) |
| 3 | f(n) = Ω(n^(log_b a + ε))，且满足正则条件 a·f(n/b) ≤ c·f(n) | T(n) = Θ(f(n)) |
举例：归并排序 T(n)=2T(n/2)+Θ(n)，log₂2=1，落在情况 2，得 Θ(n lg n)；二分查找 T(n)=T(n/2)+Θ(1)，log₂1=0，也落在情况 2，得 Θ(lg n)；Strassen 矩阵乘法 T(n)=7T(n/2)+Θ(n²)，log₂7≈2.81，n² 更小，落在情况 1，得 Θ(n^lg7)≈Θ(n^2.81)。
最容易翻车的地方是情况 2 和情况 3 之间的空隙：T(n)=2T(n/2)+n lg n 的 f(n) 既不是 Θ(n)，也不满足情况 3 的多项式大于条件，主定理直接不适用，只能上递归树。教材专门留了这道题，就是提醒你三个情况不是全覆盖。可以用一段代码把递归树逐层代价打出来，避免手算时漏层：
def tree_cost(n, a=2, b=2): # 演示 T(n) = a*T(n/b) + n 的逐层代价 # a: 子问题个数；b: 规模缩小比例；level: 当前层单节点规模 total, level, k = 0.0, n, 0 while level >= 1: cost = (a ** k) * level # 本层节点数 × 单节点代价 total += cost print(f"第{k}层 节点数={a**k:>4} 单节点代价={level:>8.2f} 本层代价={cost:>10.2f}") level /= b k += 1 return total print(tree_cost(8)) # a=b=2 时每层代价恒为 n，共 lg n 层这段输出的关键结论是：a = b 时每层代价相等，总和为 n·lg n；a < b 时每层代价递减，总和由根主导，等于 Θ(n)；a > b 时每层代价递增，总和由叶主导，等于 Θ(n^(log_b a))。把这三个形态记住，主定理的三种情况就不用死背了。参数换一下，比如 a=7、b=2，就能看到 Strassen 的场面：叶子数爆炸，总代价被叶层决定。
2.3 排序算法：堆、快排与线性时间排序的取舍
排序是第 6～8 章的主线，复习重点不在会不会写，而在每个算法的界是怎么来的、什么场景下选它。
| 算法 | 最坏 | 期望/平均 | 额外空间 | 稳定 | 关键前提 |
|---|---|---|---|---|---|
| 插入排序 | Θ(n²) | Θ(n²) | O(1) | 是 | 小规模或近乎有序时快 |
| 归并排序 | Θ(n lg n) | Θ(n lg n) | Θ(n) | 是 | 需要额外数组 |
| 堆排序 | O(n lg n) | O(n lg n) | O(1) | 否 | 原地，常数大 |
| 快速排序 | Θ(n²) | Θ(n lg n) | O(lg n) 栈 | 否 | 随机化后可避免最坏 |
| 计数排序 | Θ(n+k) | Θ(n+k) | Θ(n+k) | 是 | 关键字为 0..k 的整数 |
| 基数排序 | Θ(d(n+k)) | Θ(d(n+k)) | Θ(n+k) | 是 | 每轮必须用稳定排序 |
| 桶排序 | Θ(n²) | Θ(n) | Θ(n) | 视实现 | 输入均匀分布 |
堆排序的核心在两个函数。书里用 1-based 下标，PARENT(i)=⌊i/2⌋、LEFT(i)=2i、RIGHT(i)=2i+1；改成 0-based 就是 2i+1 和 2i+2。维护堆性质的代价是 O(lg n)，建堆却是 Θ(n) 而非 O(n lg n)，差别来自「高度为 h 的节点数最多 ⌈n/2^(h+1)⌉」这个求和。
def max_heapify(a, i, size): # 0-based 下标：左孩子 2i+1，右孩子 2i+2 l, r = 2 * i + 1, 2 * i + 2 largest = i if l < size and a[l] > a[largest]: largest = l if r < size and a[r] > a[largest]: largest = r if largest != i: a[i], a[largest] = a[largest], a[i] max_heapify(a, largest, size) # 只沿被破坏的那条路径继续下沉递归深度等于树高 O(lg n)，每层做常数次比较，所以单次维护是 O(lg n)。建堆从 ⌊n/2⌋ 向前逐个调用，看起来是 n/2 次 O(lg n)，实际因为底层节点高度小，求和后是 Θ(n)。这个「看起来 O(n lg n)、实际 Θ(n)」是笔试高频陷阱。堆还顺带提供了优先队列：INSERT 与 EXTRACT-MAX 都是 O(lg n)，MAX 是 Θ(1)，后面 Prim 和 Dijkstra 的复杂度分析都建立在这上面。
快排的重点在 PARTITION 的循环不变式和最坏情况的构造。取末尾元素作枢轴、输入已经有序时，每次划分都极不平衡，退化成 Θ(n²)；随机选取枢轴后，期望比较次数约为 2n ln n，即 Θ(n lg n)。比较排序的下界是 Ω(n lg n)，来自决策树：n 个元素有 n! 种排列，二叉树高度至少 lg(n!) = Θ(n lg n)。线性时间排序能突破这个下界，代价是放弃「只比较」这个前提——计数排序要求关键字是限定范围的整数，基数排序要求每轮稳定且按低位到高位处理，桶排序要求输入均匀分布。
2.4 顺序统计量：第 k 小元素的线性时间解法
找最大值和最小值各需 n−1 次比较，同时找两者可以压到 ⌈3n/2⌉−2 次，方法是成对处理、先对内比较再分别与当前最小最大比较。第 k 小问题用 RANDOMIZED-SELECT，思路是快排的划分但只递归一边，期望 Θ(n)。最坏情况下的线性时间算法 SELECT 用了「中位数的中位数」：五个一组排序取中位，再对这些中位递归取中位作枢轴，可以保证划分后至少有 3n/10−6 个元素落在某一侧。这两个算法的期望与最坏之差，是理解「随机化能消除对输入分布的依赖，但不能消除最坏情况」的最好例子。
3. 数据结构：哈希、平衡树与并查集的选择题
3.1 初级结构：链表、栈队列与指针的数组实现
栈和队列是后续 BFS、DFS、拓扑排序的载体，实现本身没什么难度，但有两个细节常被略过：用数组实现队列时要用循环下标，否则出队后空间浪费；用双向链表加哨兵节点可以把插入删除的边界判断全部消掉。第 10.3 节「指针与对象的数组实现」看起来偏工程，其实是后面斐波那契堆、并查集用数组写法的前提：用多个平行数组存 key、next、prev，再用一个自由表管理空闲槽位，ALLOCATE 和 FREE 都是 O(1)。有根树的「左孩子右兄弟」表示则解释了为什么多叉树可以塞进二叉结构里，B 树和树的遍历都会用到。
3.2 哈希表：链接法、开放寻址与全域散列
哈希表要解决的是「直接寻址空间太大」的问题。直接寻址最坏 Θ(1)，但要求关键字全集能开成数组。哈希把关键字映射到 m 个槽，冲突处理分两大类。
| 方案 | 查找期望 | 删除 | 注意点 |
|---|---|---|---|
| 链接法 | Θ(1+α) | 简单 | α=n/m 是装填因子 |
| 开放寻址 | 不成功查找 ≤ 1/(1−α) | 需 DELETED 标记 | α 必须小于 1 |
| 完美哈希 | 最坏 O(1) | 静态集合 | 两级结构，需预先知道关键字集合 |
散列函数的设计有除法散列 h(k)=k mod m，m 不宜取 2 的幂，否则只用到低位；乘法散列 h(k)=⌊m(kA mod 1)⌋，A 常取黄金分割比附近的值；全域散列用随机化的 h_ab(k)=((ak+b) mod p) mod m，p 是大于 m 的素数，可以证明对任意固定输入集合期望冲突数为 n/m。α 接近 1 时开放寻址的探测次数会急剧变差，这是实践中必须控制装填因子的原因。
3.3 二叉搜索树与红黑树：旋转与插入修复
二叉搜索树的性质是左子树键小于根、右子树键大于根，中序遍历得到有序序列。查找、插入、删除都是 O(h)，h 是树高；随机建树时期望高度 O(lg n)，但有序插入会退化成链。红黑树用五条性质把高度锁在 O(lg n)：节点非红即黑；根为黑；叶（NIL）为黑；红节点的两个孩子都是黑；任一节点到其所有后代叶子的简单路径上黑节点数相同。由这些性质可推出最长路径不超过最短路径的两倍，于是树高 ≤ 2lg(n+1)。
旋转是保持中序序列不变、只改局部指针的操作，代价 O(1)。
def left_rotate(tree, x): # tree 持有 root 与统一哨兵 nil，省掉大量 None 判断 y = x.right x.right = y.left # y 的左子树挂到 x 右侧 if y.left is not tree.nil: y.left.parent = x y.parent = x.parent if x.parent is tree.nil: tree.root = y elif x is x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y三组指针改向，x 下沉、y 上浮，中序顺序不变。参数 tree 是一个带 root 和 nil 哨兵的结构体，x 是旋转支点，y 是它的右孩子。插入修复分三种情况：叔叔为红时只染色并上移两层；叔叔为黑且当前节点是内侧孩子时先旋转成外侧；叔叔为黑且当前节点是外侧孩子时染色加一次旋转。删除修复更繁琐，四种情况里「兄弟为黑、两个侄子都为黑」需要把兄弟染红并上移，容易漏掉对兄弟为红要先旋转的分支。
3.4 高级结构：B 树、斐波那契堆、vEB 与并查集
B 树面向磁盘：每个节点存 2t−1 个关键字上限、t−1 个下限（根除外），所有叶子同深，高度不超过 log_t((n+1)/2)。插入用「预分裂」自上而下走一趟，删除用「预合并」，都是为了让每次磁盘访问只碰一个节点。斐波那契堆的价值在于摊还界：INSERT、UNION、DECREASE-KEY 摊还 O(1)，EXTRACT-MIN 摊还 O(lg n)，靠势函数 Φ = 树数 + 2×标记节点数 来平摊懒惰合并的代价，Dijkstra 与 Prim 用它可以把复杂度压到 O(E + V lg V)。vEB 树在宇宙大小 u 上做到 O(lg lg u)，用「簇 + 摘要」的递归结构，适合密集整数键。并查集用按秩合并加路径压缩，m 次操作的摊还代价是 O(m·α(n))，α 增长慢到在可想象的 n 范围内不超过 4，这是「理论上不是常数、实践上等同常数」的经典案例。
4. 设计范式与图算法：DP、贪心、摊还到最短路与最大流
4.1 动态规划：最优子结构从哪来，状态怎么定义
动态规划适用的两个条件是重叠子问题和最优子结构。钢条切割、矩阵链乘、最长公共子序列、最优二叉搜索树这四个例子覆盖了四种状态定义套路：一维前缀、二维区间、二维双前缀、二维区间加根位置。矩阵链乘的递推是 m[i,j] = min_{i≤k<j}{ m[i,k] + m[k+1,j] + p_{i−1}p_k p_j }，三重循环 Θ(n³)，空间 Θ(n²)；LCS 的递推分字符相等与不等两支，Θ(mn)。写 DP 的关键不是背递推，而是三件事：状态含义写清楚、边界初始化不漏、需要输出方案时额外存一个选择表。
def lcs(x, y): # dp[i][j] = x 前 i 个字符与 y 前 j 个字符的 LCS 长度 m, n = len(x), len(y) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if x[i - 1] == y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]两层循环各走 m、n 步，每步常数时间，总时间 Θ(mn)，空间 Θ(mn)；若只要长度，可以把空间压到两行，代价是丢掉回溯路径。参数 x、y 是待比较序列，dp 的下标从 1 开始，与「前 i 个字符」的说法对齐，这样边界行和列天然是 0，省掉特判。
4.2 贪心与拟阵：什么时候可以「不回头看」
贪心要成立，需要贪心选择性质和最优子结构两条都满足。活动选择问题按结束时间排序后依次挑选，O(n lg n)；Huffman 编码每次取权值最小的两个合并，用最小堆实现是 O(n lg n)。判断贪心对不对，标准手段是交换论证：假设最优解不选贪心那一项，构造一个同样优的解，证明不亏。拟阵那一节（带星号）提供了更抽象的保证：在拟阵上，按权值排序后贪心一定得到最大权独立集，任务调度问题就是它的实例。动态规划与贪心的分界线在于，贪心做完选择后只留一个子问题，DP 会保留所有可能的子问题答案；一旦发现「当前最优选择依赖后面的选择」，就该退回 DP。
4.3 摊还分析：聚合、记账、势能三把尺子
摊还分析回答的是「一串操作的总代价除以操作数」。聚合分析直接对 n 次操作求和再平均；记账法给每种操作记上虚拟费用，把余额存到数据结构里；势能法定义一个势函数 Φ，摊还代价 = 实际代价 + ΔΦ。动态表是最好的例子：插入时若表满就扩张一倍，扩张代价 O(n)，但把每次插入的摊还代价算成 3 就够——一次支付自己的插入，两次存着给将来扩张用。注意摊还和平均不是一回事：摊还分析针对的是操作序列的最坏情况，不涉及概率假设，而平均情况分析必须指定输入分布。这是复习里极容易被混为一谈的一对概念。
4.4 图的基本功：BFS、DFS、拓扑排序与强连通分量
图的表示首选邻接表，空间 O(V+E)；稠密图或需要 O(1) 判边时用邻接矩阵，空间 O(V²)。BFS 用队列，白灰黑三色标记，得到的是无权图最短路径，每条边和每个顶点各访问常数次，O(V+E)。DFS 记录发现时间 d 和完成时间 f，形成括号结构：两个区间要么完全包含要么完全分离。边分四类，有向图存在后向边等价于存在环，这个判据比想象中好用。拓扑排序有两条路：DFS 按完成时间逆序输出，或 Kahn 算法每次取入度为零的点，都是 O(V+E)。强连通分量用 Kosaraju 两趟 DFS（第二趟在转置图上按完成时间逆序），或 Tarjan 一趟搞定，复杂度同样 O(V+E)。
4.5 最小生成树与最短路：算法选择和负权边界
MST 的两种算法都基于切割性质。Kruskal 把边排序后用并查集判环，O(E lg E)；Prim 从一个点开始不断加最近的点，二叉堆 O(E lg V)，斐波那契堆 O(E + V lg V)，稠密图更适合直接用数组实现成 O(V²)。
| 问题 | 算法 | 复杂度 | 适用条件 |
|---|---|---|---|
| 单源最短路 | Bellman-Ford | O(VE) | 可有负权边，能检测负环 |
| 单源最短路 | DAG 上按拓扑序松弛 | O(V+E) | 有向无环图 |
| 单源最短路 | Dijkstra | O(E lg V) | 边权非负 |
| 全源最短路 | Floyd-Warshall | Θ(V³) | 可有负权，无负环 |
| 全源最短路 | Johnson | O(V²lg V + VE) | 稀疏图，可负权 |
Bellman-Ford 对每条边松弛 V−1 轮，如果第 V 轮还能松弛就说明有负环；这个「多跑一轮」的技巧是判断负环的标准写法。Dijkstra 的正确性依赖非负权，负权边会让已经出队的点不再是最优，属于典型翻车场景。差分约束系统把不等式 x_j − x_i ≤ w 转成边，用 Bellman-Ford 求可行解，是单源最短路的经典应用。
import heapq def dijkstra(graph, src): # graph[u] = [(v, w), ...]，w 必须非负 dist = {u: float('inf') for u in graph} dist[src] = 0 pq = [(0, src)] # (当前距离, 顶点) while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue # 过期条目，直接丢弃 for v, w in graph[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(pq, (nd, v)) return dist每条边最多引发一次成功松弛，每次入堆 O(lg V)，总时间 O(E lg V)；惰性删除让堆里可能出现重复条目，所以出堆时要和 dist 比对跳过。参数 graph 是邻接表，src 是源点，w 为负时算法不保证正确，这是使用前必须确认的前提。
4.6 最大流与难解性：从增广路到 NP 完全与近似
流网络满足容量约束和流量守恒，残量网络上的增广路径决定还能不能继续推流，最大流最小割定理说三者等价：最大流的值等于最小割容量，且不存在增广路径时流最大。Ford-Fulkerson 每轮找一条增广路，复杂度 O(E|f*|)，整数容量时收敛但可能很慢；Edmonds-Karp 固定用 BFS 找最短增广路，O(VE²)；推送-重贴标签与重贴标签到前端是另外两条路。二分图最大匹配可以建成单位容量流网络求解。
NP 完全性那部分的关键是区分三个概念：P 是多项式时间可解，NP 是多项式时间可验证，NPC 是 NP 中最难的一类——任何 NP 问题都能多项式归约到它。证明一个问题是 NPC，需要两步：先证它在 NP 里（给证书能多项式验证），再把一个已知 NPC 问题归约到它。经典链条从电路可满足性出发，到 3-CNF-SAT、团、顶点覆盖、哈密顿回路、旅行商。面对 NPC 问题，实际出路是近似算法：顶点覆盖有 2-近似，满足三角不等式的 TSP 有 2-近似，集合覆盖有 ln n + 1 近似，子集和有 FPTAS。近似比的定义和证明套路，是这部分最值得动手写的练习。
5. 易错点：五个最容易翻车的复习盲区
第一个：把 O 当成「最坏情况」，该写 Θ 的地方写 O。漏的原因是教材前面几章为了行文方便大量使用 O，读久了就把 O 当成万能量词。补法是做题时先问一句「这里要求上界、下界还是紧确界」，凡是要「紧确界」的答案一律用 Θ，并检查是否存在一个更小的同阶函数也能作上界。
第二个：主定理三种情况当成全覆盖，遇到 n lg n 这类间隙项直接硬套。漏的原因是只记了结论没记条件，尤其情况 3 的正则条件经常被忽略。补法是每次套用前先算 log_b a，写出 n^(log_b a)，再和 f(n) 做多项式级别的比较：差一个 n^ε 才能归入情况 1 或 3，恰好同阶才是情况 2；比较不出来就退回递归树。
第三个：建堆写成 O(n lg n)，或者忘记 BUILD-MAX-HEAP 是紧确界 Θ(n)。漏的原因是只数了调用次数乘单次代价，没有按节点高度求和。补法是把 Σ_{h=0}^{⌊lg n⌋} ⌈n/2^(h+1)⌉·O(h) 这个式子手推一遍，记住结论：大部分节点在底层，高度小，所以总代价线性。
第四个：开放寻址删除时把槽位置成 NIL。漏的原因是直觉上「删掉就是空的」，但开放寻址的查找依赖探测序列连续，中间挖空会让后面的键永远找不到。补法是删除时写入 DELETED 标记，查找时跳过 DELETED 但继续探测，插入时可以复用 DELETED 槽位；同时把装填因子控制在 1 以下并留出余量。
第五个：贪心和动态规划选错，或者把摊还当成平均。漏的原因是两者表面都在「一步步做选择」，而摊还和平均都涉及「多次操作取平均」。补法有两条：判断贪心时强迫自己写交换论证，写不出来就换 DP；区分摊还和平均时看有没有概率假设，摊还分析是最坏情况序列的总代价平摊，不需要任何分布。
6. 复习清单：三轮过书与查漏补缺的执行表
第一轮按八个部分走概念，每章只做三件事：读懂伪代码、能复述算法思路、把该章末尾练习里最简单的三道做掉。这一轮不要纠缠证明，目标是把地图上的每个节点都点亮，知道自己缺哪块。第二轮专攻证明和手推，重点只有五个：主定理的三种情况各推一个例子、红黑树插入的三种修复情况、摊还分析的势能法、最大流最小割定理的等价性、NPC 归约链条。这一轮要合上书在纸上写，写不出来说明第一轮只是「看懂了」而不是「会了」。第三轮限时手写伪代码，BFS、DFS、拓扑排序、Dijkstra、Bellman-Ford、Floyd-Warshall、矩阵链乘、LCS、KMP 各写一遍，控制在每题十分钟内。
| 高频考点 | 对应章节 | 自检标准 |
|---|---|---|
| 渐近记号与增长阶 | 第 3 章 | 能判断任意两函数的 O/Ω/Θ 关系 |
| 递归式与主定理 | 第 4 章 | 三个情况各能举一例并说明条件 |
| 堆与建堆线性证明 | 第 6 章 | 能推出 Θ(n) 的求和过程 |
| 快排期望分析 | 第 7 章 | 能说明随机化为什么消除最坏输入 |
| 比较排序下界 | 第 8 章 | 能从决策树高度推出 Ω(n lg n) |
| 红黑树插入修复 | 第 13 章 | 能画出三种情况的旋转与染色 |
| 动态规划状态设计 | 第 15 章 | 能独立写出矩阵链乘与 LCS |
| 贪心正确性证明 | 第 16 章 | 能写活动选择的交换论证 |
| 单源最短路三算法 | 第 24 章 | 能说清负权为什么让 Dijkstra 失效 |
| 最大流最小割 | 第 26 章 | 能构造残量网络并解释等价性 |
| NP 完全归约 | 第 34 章 | 能写出两步证明模板 |
查漏补缺的具体做法：把每章末尾标星号的节先跳过，等第二轮再回头；每错一道题，在笔记里只记一行「错因 + 正确思路的第一句话」，不抄完整答案；一周后再做同一道题，还错就说明这个概念没打通，回到对应章节重读那一节而不是继续刷题。
有一个血泪经验：我以前复习只爱看伪代码，觉得证明是「玄学」，结果考场上主定理的情况 2 少写一个 lg 因子，整道大题的分没了。从那以后我每复习一章都强制合上书默写一遍核心伪代码，再口述一遍它的正确性理由和复杂度来源，两个都过才算这章过关。希望帮到你。
本文还有配套的精品资源，点击获取
