期末周在图书馆复习《算法设计与分析》的时候我发现一个特别普遍的现象很多人抱着教材从头到尾翻试图把每个算法的代码实现“背下来”结果翻到第八章、第九章前面全忘了。这门课真正要背的根本就不是某种具体语言的实现代码而是用伪代码表达出来的算法骨架。伪代码的好处是剥离了语法噪声把“每一步在做什么”暴露得一清二楚考试时不管是让写算法、补代码、画过程还是让算复杂度你心里都有一张清晰的流程图可以调出来。这篇总结把我自己复习时反复默写过的必考算法按策略分类整理出来直接给出伪代码、复杂度结论和考场易错点适合正在备考、需要一份可背诵提纲的同学。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[m1..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-l1)因此整体递推式为 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* 的增长阶即可条件结论f(n) O(n^(c* - ε))ε 0T(n) Θ(n^c*)f(n) Θ(n^c* · log^k n)T(n) Θ(n^c* · log^(k1) n)f(n) Ω(n^(c* ε))且存在 c1 使 af(n/b) ≤ cf(n)T(n) Θ(f(n))记忆方法很简单谁大听谁的一样大就加一个 log。比如 T(n)9T(n/3)na9b3c*2而 f(n)nn^(1)比 n² 小所以答案是 Θ(n²)。如果是 T(n)2T(n/2)nc*1f(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[k1][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[k1][j]k1 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(VE)。考试可能问有环的图能不能拓扑排序不能。拓扑排序不唯一——入度为 0 的结点有多个时就产生分支。DFS 版本的思路是对每个顶点做深度优先遍历用栈记录完成顺序最后逆序输出。6.2 Dijkstra堆优化必背朴素版 Dijkstra 是 O(V²)堆优化版是 O((VE) 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 whileAlgorithm 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((VE) 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 是 NPCA ≤ B 且 B 属于 NP则 B 也是 NPC。这题的分数基本是送的只要把方向记牢就不会错。7.3 近似算法NP难问题也能给出可用解期末考试对近似算法一般只要求了解概念和简单例子。顶点覆盖问题的 2 近似算法很好写反复选一条边把它的两个端点都加入覆盖集删除被覆盖的边直到无边可选。证明近似比的关键是选出的这些边互不相交所以最优覆盖至少要覆盖每条边的一个端点因此当前覆盖大小最多是最优解的两倍。Traveling Salesman ProblemTSP的三角不等式版本可以构造最小生成树后前序遍历得到 2 近似解这个结论记住即可。7.4 期末压轴题的常见套路压轴题往往不是单考一个算法而是把策略和工具结合起来。常见组合用 Floyd 求传递闭包 用 DP 找最短路径用 0-1 背包变体考察“恰好装满”和“方案数”用最优二叉搜索树或编辑距离这种不常练的 DP 模型考状态设计能力用最小生成树加一条边的思想求次小生成树。遇到这些变体先别慌把问题往熟悉的模型上靠能拆成子问题的用 DP能局部最优推全局的用贪心需要穷举且规模小的用回溯。最后说一个我复习时用下来特别有效的方法考前最后一晚不要翻书拿一张白纸把五个策略下的经典伪代码各默写一遍默写完再对照教材标错。这个过程逼着大脑把知识重新组织了一遍考场上很多细节比如 0-1 背包倒序、Floyd 中间层循环、Dijkstra 跳过过期结点会像肌肉记忆一样自己冒出来。祝复习顺利考试稳住。