期末周在图书馆复习《算法设计与分析》的时候，我发现一个特别普遍的现象：很多人抱着教材从头到尾翻，试图把每个算法的代码实现“背下来”，结果翻到第八章、第九章，前面全忘了。

这门课真正要背的，根本就不是某种具体语言的实现代码，而是用伪代码表达出来的算法骨架。伪代码的好处是剥离了语法噪声，把“每一步在做什么”暴露得一清二楚，考试时不管是让写算法、补代码、画过程，还是让算复杂度，你心里都有一张清晰的流程图可以调出来。这篇总结把我自己复习时反复默写过的必考算法按策略分类整理出来，直接给出伪代码、复杂度结论和考场易错点，适合正在备考、需要一份可背诵提纲的同学。

1. 备考逻辑先理清楚：这门课背的不是代码，是五个策略加两类工具

很多同学对算法设计与分析有个误解，觉得它是“编程课”的延伸，于是花大量时间抠语法细节，变量命名、边界条件、循环写法全都要跟教材一字不差。事实是，期末考试的算法设计题基本都是让你“写出算法的伪代码或主要步骤”，然后分析复杂度。阅卷看的是你有没有抓住策略核心，而不是你的指针有没有置空。

所以复习的正确姿势是：按算法设计策略分类，把每个策略下最经典的模型吃透，再把图论算法当作独立工具掌握。分治、动态规划、贪心、回溯、分支限界这五个策略，加上排序/图论这些基础算法工具，基本覆盖了期末80%以上的考点。

另一个容易翻车的点是复杂度推导。主定理怎么用、递归树怎么画、DP的时间复杂度怎么从状态和转移两个维度算，这些是简答题和计算题的高频考法。只看结论不推过程的话，考试换个参数就懵。下面每一节我会把算法的伪代码和复杂度推导一起讲，照着这个思路走，复习效率会高很多。

2. 分治策略：归并、快排与主定理，考场上最稳的得分点

分治法的核心一句话：把一个规模为 n 的问题拆成若干个规模更小的子问题，分别解决后再合并结果。考试最爱考的三个分治算法是归并排序、快速排序和二分查找，它们分别对应“合并复杂”“划分复杂”“直接砍半”三种典型套路。主定理则负责解决一个更上层的问题——递归式的复杂度到底是多少。

2.1 归并排序：合并过程是重点

归并排序的思路非常规整：把数组一分为二，递归排序两半，最后线性合并。伪代码可以这样写：

Algorithm MergeSort(A, l, r) // 对数组 A[l..r] 升序排序 if l < r then m <- ⌊(l + r) / 2⌋ MergeSort(A, l, m) MergeSort(A, m + 1, r) Merge(A, l, m, r) end if Algorithm Merge(A, l, m, r) // 合并有序子数组 A[l..m] 与 A[m+1..r] i <- l, j <- m + 1, k <- 0 B <- 新建长度为 r - l + 1 的临时数组 while i <= m and j <= r do if A[i] <= A[j] then B[k++] <- A[i++] else B[k++] <- A[j++] end while while i <= m do B[k++] <- A[i++] while j <= r do B[k++] <- A[j++] A[l..r] <- B[0..k-1]

这里的Merge过程就是考试最容易出小题的地方：比较次数是多少？需要多少额外空间？Merge的复杂度显然是 O(r-l+1)，因此整体递推式为 T(n)=2T(n/2)+O(n)，解得 O(n log n)。空间复杂度 O(n) 这一点也经常考，注意别答成 O(1)。

2.2 快速排序：划分函数决定效率

快排的伪代码骨架比归并更短，关键在那个Partition函数：

Algorithm QuickSort(A, l, r) if l < r then pivot <- Partition(A, l, r) QuickSort(A, l, pivot - 1) QuickSort(A, pivot + 1, r) end if Algorithm Partition(A, l, r) // 以 A[r] 为基准，返回基准最终位置 x <- A[r] i <- l - 1 for j <- l to r - 1 do if A[j] <= x then i <- i + 1 swap(A[i], A[j]) end if end for swap(A[i + 1], A[r]) return i + 1

考试常见的问法是：最坏情况发生在什么时候？答案是当数组已经有序或逆序且每次都选端点做基准时，划分极度不均，复杂度退化成 O(n²)。平均复杂度 O(n log n) 的推导一般用递归树或期望来分析，期末常以选择题形式出现。快速排序是不稳定的，这一点也请记牢。

2.3 主定理：三种情况的口诀式记忆

分治算法的复杂度大多能套主定理。对于形如 T(n)=aT(n/b)+f(n) 的递推式，令 c*=log_b a，比较 f(n) 与 n^c* 的增长阶即可：

记忆方法很简单：谁大听谁的，一样大就加一个 log。比如 T(n)=9T(n/3)+n，a=9，b=3，c*=2，而 f(n)=n=n^(1)，比 n² 小，所以答案是 Θ(n²)。如果是 T(n)=2T(n/2)+n，c*=1，f(n)=n 跟 n^c* 同阶，答案是 Θ(n log n)。主定理不满足时（比如 f(n) 比 n^c* 小但是又不是多项式地小），老老实实画递归树。

3. 动态规划：状态定义是分水岭，四大经典模型务必背熟

动态规划是期末的大头，也是不少同学的噩梦。它的答题思路其实非常固定：第一步定义状态，第二步写状态转移方程，第三步注意初始化与遍历顺序，第四步给出时间复杂度。这四步里，前面两步占了80%的分数，能写对状态，后面基本就是机械劳动。

3.1 0-1背包：所有背包问题的地基

题目描述一般是一堆物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 C，求能装下的最大价值。关键是每种物品最多选一件。二维 DP 的伪代码如下：

Algorithm ZeroOneKnap(w, v, n, C) // dp[i][j] 表示前 i 件物品在容量为 j 时的最大价值 for j <- 0 to C do dp[0][j] <- 0 for i <- 1 to n do for j <- 0 to C do if j < w[i] then dp[i][j] <- dp[i-1][j] else dp[i][j] <- max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) end if end for end for return dp[n][C]

这里最容易错的一点：转移用的是dp[i-1][j-w[i]]，不是dp[i][j-w[i]]。因为每件物品只能选一次，必须从上个状态转移过来。滚动数组优化后要倒序遍历容量，否则物品会被选多次，这也就是为什么完全背包可以正序、而 0-1 背包必须倒序。期末考试特别喜欢问这个区别，答的时候别只说“倒序”，要说清楚是为了保证每个物品只被取一次。

复杂度：时间 O(nC)，空间 O(C)（滚动数组）或 O(nC)（二维）。题目如果问“恰好装满背包”的最大价值，初始化时把dp[0][0]=0，其余dp[0][j] = -∞，这个变体也很常考。

3.2 最长公共子序列：画表法是最好的得分工具

LCS 的经典性和背包不相上下。状态定义是dp[i][j]表示X[1..i]与Y[1..j]的 LCS 长度：

Algorithm LCS(X, Y) m <- len(X), n <- len(Y) for i <- 0 to m do dp[i][0] <- 0 for j <- 0 to n do dp[0][j] <- 0 for i <- 1 to m do for j <- 1 to n do if X[i] = Y[j] then dp[i][j] <- dp[i-1][j-1] + 1 else dp[i][j] <- max(dp[i-1][j], dp[i][j-1]) end if end for end for return dp[m][n]

如果题目要求“构造出最长公共子序列本身”，需要额外开一个c[i][j]数组记录每个位置是从哪个方向转移来的（左上 / 上 / 左），然后从dp[m][n]倒着回溯。考试画表时我建议手写方向箭头，阅卷老师一看就懂。

3.3 矩阵链乘：括号化问题，状态转移是“划分中间点”

这题的题意是给一串矩阵维度序列，求完全加括号后标量乘法的最少次数。状态dp[i][j]表示矩阵 i 到矩阵 j 的最小乘法次数：

Algorithm MatrixChain(p, n) // p[0..n] 为维度数组，矩阵 Ai 的维度是 p[i-1] × p[i] for i <- 1 to n do dp[i][i] <- 0 for L <- 2 to n do // L 为链长 for i <- 1 to n - L + 1 do j <- i + L - 1 dp[i][j] <- ∞ for k <- i to j - 1 do cost <- dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] if cost < dp[i][j] then dp[i][j] <- cost s[i][j] <- k // 记录断点，用于回溯构造方案 end if end for end for end for return dp[1][n]

注意遍历顺序：必须先枚举区间长度 L，再枚举左端点 i，最后枚举断点 k。如果直接在i外层循环，计算dp[i][j]时dp[k+1][j]（k+1 > i）可能还没算好。复杂度 O(n³)，空间 O(n²)。考试还有一个高频考点是让你写出某个断点划分的完整括号方案，s[i][j]数组就是干这个用的。

3.4 最长递增子序列：O(n log n) 的贪心+二分是加分项

LIS 有两个版本，基础的 O(n²) DP 很简单：

Algorithm LIS(A, n) for i <- 1 to n do dp[i] <- 1 for j <- 1 to i - 1 do if A[j] < A[i] then dp[i] <- max(dp[i], dp[j] + 1) end if end for end for return max(dp[1..n])

但期末如果要拔高，可能会考 O(n log n) 的解法：维护一个tail数组，用二分查找找第一个大于等于A[i]的位置并替换。这个版本的核心思想其实是贪心：保持 tail 中每个长度的最小末尾元素最小化，理解了这个，记代码就很容易了。

4. 贪心算法：正确性证明比代码本身更重要

贪心的代码写起来往往比 DP 短很多，但考试真正的区分度在**“为什么贪心是对的”。期末简答题或证明题很可能要求你证明某个贪心策略的正确性。不要慌，套路就两种：交换论证和归纳法**。交换论证是说“任意最优解都可以经有限次交换变成贪心解，且不损失最优性”；归纳法则是“证明贪心选择的局部最优能推广到全局”。

4.1 活动选择问题：入门级的贪心范式

问题描述：若干活动有开始时间和结束时间，同一时刻只能参加一个，求最多能参加多少个。贪心策略是每次选结束时间最早且与已选活动不冲突的活动：

Algorithm ActivitySelect(s, f, n) // s[i] 开始时间，f[i] 结束时间，活动已按 f 升序排列 A <- ∅ last <- 0 for i <- 1 to n do if s[i] >= last then A <- A ∪ {i} last <- f[i] end if end for return A

排序本身 O(n log n)，贪心选择 O(n)。为什么不能选开始时间最早或持续时间最短？因为结束时间最早能给后面留下最多余地——这就是贪心选择性质的直观解释。考试写证明时，用交换论证即可：如果最优解的第一个活动不是结束时间最早的，就把它替换掉，不会减少可选活动数量。

4.2 哈夫曼编码：记住“每次选频率最小的两个合并”

哈夫曼编码是必考贪心，步骤不难，但考试经常变成画图题或构建编码表题：

Algorithm Huffman(C) // C 为字符及其频率集合，n = |C| Q <- 以频率为关键字的最小优先队列 for i <- 1 to n - 1 do x <- ExtractMin(Q) y <- ExtractMin(Q) z <- 新结点，左孩子 x，右孩子 y，频率 = x.freq + y.freq Insert(Q, z) end for return ExtractMin(Q) // 返回根结点

复杂度 O(n log n)。这里要特别小心：哈夫曼编码是前缀码，任意字符的编码都不能是另一个字符编码的前缀，这样解码才不会产生歧义。题目可能还会问 WPL（带权路径长度），也就是所有叶子结点的频率乘深度之和，构建完树累加一遍就行。

4.3 Dijkstra与贪心的关系

严格说 Dijkstra 是最短路径算法，但它的每一步“选当前距离最小的未访问结点”本质上是贪心。伪代码放在后面图算法章节再展开。你只需要知道：贪心算法在能和 DP 混着考，最典型的就是“分数背包用贪心、0-1背包用DP”这个对照题。

5. 回溯与分支限界：两种搜索策略的剪枝艺术

回溯和分支限界都是系统性搜索解空间的方法，区别在于回溯是深度优先，走不通就回头；分支限界一般用广度优先或优先队列，靠界限函数剪掉不可能更优的分支。期末常考的是 n 皇后、图的着色、装载问题、0-1背包问题。

5.1 n皇后问题：回溯法的经典载体

n 皇后要求在 n×n 棋盘上放 n 个皇后，任意两个不能在同一行、同一列、同一对角线。核心是在第 k 行逐列尝试放置，检查冲突后递归进入下一行：

Algorithm NQueens(k, n, x) // x[i] 表示第 i 行皇后所在列号 if k > n then output x[1..n] // 得到一个合法解 return end if for col <- 1 to n do if Place(k, col, x) then x[k] <- col NQueens(k + 1, n, x) end if end for Algorithm Place(k, col, x) for i <- 1 to k - 1 do if x[i] = col then return false // 同列 if |x[i] - col| = |i - k| then return false // 同一对角线 end for return true

考试可能的变形：求解的个数、画出搜索树的剪枝过程、统计扩展的结点数。每次递归尝试的复杂度是 O(n)，总复杂度虽然上界指数级，但剪枝后实际效率可观。注意Place检查对角线用的绝对值等式，这是最容易写错却又最好得分的细节。

5.2 子集和与装载问题：理解限界函数的工作方式

子集和问题是从集合中选若干元素，使和等于目标值。回溯法按“选/不选”分支搜索。分支限界处理装载问题时，会计算上界“当前载重 + 剩余所有物品重量”，如果上界都达不到当前最优值，就剪枝。这一题的考点往往是：上界函数为什么要这样取？因为分支限界要把可能的最优解上限估计出来，宁可高估不能低估，低估会剪掉真正的优解。

5.3 0-1背包的分支限界：优先队列式

分支限界处理 0-1 背包的思路和 DP 完全不同，更接近“按价值密度排序后，用贪心上界做剪枝”：

Algorithm BnBBag(items, C) // 物品按单位价值 v[i]/w[i] 降序排列 当前最优值 best <- 0 队列 Q <- ∅ 以根结点（不选任何物品）入队 while Q 不空 do 出队一个结点 node 计算选当前物品的分支上界 ub 如果 ub > best 且未越界，则扩展该分支并更新 best 计算不选当前物品的分支上界 ub 如果 ub > best，则扩展该分支 end while return best

这个伪代码里的“计算上界”是通过剩余容量按单位价值贪心装满来估计的，叫“松弛上界”。考试不要求你实现完整代码，但要求能手动跑几步、说明为什么某些分支被剪掉。优先队列结点的价值密度排序是关键，前提是物品本身按贪心价值降序排列。

6. 图算法：最短路径与最小生成树，代码细节别再丢分

图算法在期末卷子里通常独占一道大题，不是考最短路径就是考最小生成树，也可能两个都考。这部分算法不归入“五种策略”，但属于基础工具，必须单独背熟。要格外注意初始化、访问标记和优先队列操作。

6.1 拓扑排序：Kahn算法与DFS法二选一

图的拓扑排序常用于任务调度场景。Kahn 算法基于“不断删除入度为 0 的结点”：

Algorithm TopoSortKahn(G) 计算所有顶点入度 indegree 队列 Q <- 所有 indegree = 0 的顶点 order <- ∅ while Q 不空 do u <- 出队 order <- order + u for v in G.Adj[u] do indegree[v] <- indegree[v] - 1 if indegree[v] = 0 then Q <- Q + v end for end while if len(order) < |V| then 报告“图中有环” else return order

时间复杂度 O(V+E)。考试可能问：有环的图能不能拓扑排序？不能。拓扑排序不唯一——入度为 0 的结点有多个时就产生分支。DFS 版本的思路是对每个顶点做深度优先遍历，用栈记录完成顺序，最后逆序输出。

6.2 Dijkstra：堆优化必背

朴素版 Dijkstra 是 O(V²)，堆优化版是 O((V+E) log V)，期末如果想加大难度，往往是在这个优化上做文章：

Algorithm DijkstraHeap(G, s) for v in V do dist[v] <- ∞, visited[v] <- false dist[s] <- 0 优先队列 Q，元素为 (距离, 顶点)，插入 (0, s) while Q 不空 do (d, u) <- ExtractMin(Q) if visited[u] then continue visited[u] <- true for (v, w) in G.Adj[u] do if not visited[v] and dist[u] + w < dist[v] then dist[v] <- dist[u] + w Insert(Q, (dist[v], v)) end if end for end while return dist

这里的“跳过失效结点”是堆优化最常见的坑：因为一个顶点可能被多次松弛并重复入队，所以出队时如果已经确认过，就直接跳过。另外 Dijkstra 不能处理负权边，这个结论常考简答，原因是负权边会破坏贪心的“当前最小距离不会再被更新”的假设。

6.3 Floyd-Warshall：多源最短路径的DP思想

Floyd 本质是动态规划。dist[i][j]表示从 i 到 j 的最短路径长度，中间允许经过前 k 个结点时的更新公式特别干净：

Algorithm Floyd(W, n) // W 为带权邻接矩阵，不存在的边设为 ∞ for k <- 1 to n do for i <- 1 to n do for j <- 1 to n do if W[i][k] + W[k][j] < W[i][j] then W[i][j] <- W[i][k] + W[k][j] end if end for end for end for return W

三重循环的遍历顺序（最外层必须是中间结点 k）是考试爱问的点。如果最外层是 i 或 j，计算时会用到还没完全更新的中间结果，导致错误。复杂度 O(V³)。Floyd 能处理负权边，但不能处理负权回路。

6.4 最小生成树：Prim与Kruskal的复杂度对比

Prim 是“从点出发，每次选连接到已选集合的最短边”；Kruskal 是“从边出发，按权值从小到大选边，用并查集判环”。

Algorithm Prim(G) 从任意顶点 s 开始 visited[s] <- true while 未访问顶点数 > 0 do (u, v, w) <- 连接已访问集合与未访问集合的最小权边 visited[v] <- true，把边加入生成树 end while

Algorithm Kruskal(G) 把边按权值升序排列 并查集初始化：每个顶点独立 for (u, v, w) in 排序后的边 do if Find(u) != Find(v) then Union(u, v) 把边加入生成树 end if end for

复杂度对比要记清楚：Prim 一般 O(V²)，稠密图合适；堆优化 Prim O((V+E) log V)。Kruskal 的瓶颈在排序 O(E log E)，稀疏图更合适。并查集操作接近常数级 O(α(V))，常数级别可以忽略。

7. P/NP与近似算法：期末压轴题的常见考法

这部分属于课程后半段的理论内容，看起来抽象，其实期末出的题非常固定：给定义、判复杂度类、简单归约方向。这部分不要求你会写算法，但要求你理解分类体系。

7.1 P、NP、NP完全的基本定义

• P 类：存在多项式时间确定性算法能求解的问题。
• NP 类：存在多项式时间算法能验证一个解是否正确的问题。
• NP完全（NPC）：属于 NP，且所有 NP 问题都可多项式时间归约到它。

“P 是否等于 NP”是目前还没有结论的开放问题，考试常以判断题或填空题出现。注意一个常见误区：不能因为没找到多项式算法就说它是 NP 完全的，NP 完全性需要归约证明。

7.2 归约方向的理解

归约符号A ≤ B要理解成“若 B 能被多项式时间求解，则 A 也能”。所以归约方向是从已知难的问题到新问题：已知 A 是 NPC，A ≤ B 且 B 属于 NP，则 B 也是 NPC。这题的分数基本是送的，只要把方向记牢就不会错。

7.3 近似算法：NP难问题也能给出可用解

期末考试对近似算法一般只要求了解概念和简单例子。顶点覆盖问题的 2 近似算法很好写：反复选一条边，把它的两个端点都加入覆盖集，删除被覆盖的边，直到无边可选。证明近似比的关键是：选出的这些边互不相交，所以最优覆盖至少要覆盖每条边的一个端点，因此当前覆盖大小最多是最优解的两倍。

Traveling Salesman Problem（TSP）的三角不等式版本可以构造最小生成树后前序遍历得到 2 近似解，这个结论记住即可。

7.4 期末压轴题的常见套路

压轴题往往不是单考一个算法，而是把策略和工具结合起来。常见组合：

• 用 Floyd 求传递闭包 + 用 DP 找最短路径；
• 用 0-1 背包变体考察“恰好装满”和“方案数”；
• 用最优二叉搜索树或编辑距离这种不常练的 DP 模型考状态设计能力；
• 用最小生成树加一条边的思想求次小生成树。

遇到这些变体，先别慌，把问题往熟悉的模型上靠：能拆成子问题的用 DP，能局部最优推全局的用贪心，需要穷举且规模小的用回溯。

最后说一个我复习时用下来特别有效的方法：考前最后一晚，不要翻书，拿一张白纸，把五个策略下的经典伪代码各默写一遍，默写完再对照教材标错。这个过程逼着大脑把知识重新组织了一遍，考场上很多细节（比如 0-1 背包倒序、Floyd 中间层循环、Dijkstra 跳过过期结点）会像肌肉记忆一样自己冒出来。祝复习顺利，考试稳住。