期末复习这门课最折磨人的不是题难是不知道哪些东西会考、哪些公式要背到什么熟练度。我当年复习《算法设计与分析》的时候教材翻了两遍一上考场还是栽在递推方程上——题目看着眼熟手一算就错。后来辅导过几届学弟学妹发现大家踩的坑几乎一模一样。这篇东西我就按期末试卷的实际出题逻辑把最常考、最容易扣分的模块拆开讲每个模块配例题和答题思路争取让你合上课本就能上手写题。这篇内容的适用对象很明确正在准备《算法设计与分析》期末考试、需要短时间把知识点串成答题能力的同学。不同学校卷面结构略有差异但核心模块跑不出复杂度分析、分治与动态规划、贪心、回溯与分支限界、NP理论这几块。我会把每个模块里“必须掌握”和“了解即可”分开你按自己的课时安排和考纲取舍。先有一张全局地图再谈刷题顺序不能反。1. 复习先画地图算法设计与分析期末的考点分布与主次排序1.1 这门课的复习状态为什么容易“看了等于没看”见过太多人复习算法课的方式打开教材从头读到尾读完第三章忘了第一章合上书觉得“都会了”一动手写题发现连递推式展开都算不明白。原因很简单——这门课和数据结构不一样数据结构有具体的代码可以背算法课考察的是“面对一个新问题你能不能设计出正确且高效的解法”这是能力题不是记忆题。所以复习策略必须反过来先搞清楚每类题的固定套路再刷题验证。比如动态规划大题你只要掌握了“状态定义→转移方程→初始化→填表方向”这条线不管题目换成背包还是最长公共子序列都能套出答案。背题是最亏的复习方式因为期末试卷里的原题比例通常很低考察的是你迁移套路的能力。1.2 各模块的考频和题型定位我根据几所高校的算法期末卷和常见教材习题把知识点模块做一个优先级排序。你复习时间不够的时候按这个优先级取舍。模块常见题型优先级原因复杂度分析、递推方程求解选择、填空、解答极高几乎每所学校的必考内容且动规、分治的复杂度分析都依赖这个基础动态规划算法设计大题极高期末压轴题的最大概率出题模块0-1背包、LCS、矩阵连乘轮流出分治策略解答、算法设计高归并排序、最大子段和、大整数乘法都是经典考点贪心算法解答、算法设计高活动安排、哈夫曼编码常考且容易和动规对比出题回溯法算法设计、手推解空间中高0-1背包、N皇后、图着色是三个经典模型分支限界法概念、对比中通常不考完整代码但会考察和回溯的区别NP理论、近似算法、概率算法选择、简答中分值不高但属于送分题背熟术语就能拿这个排序背后的逻辑很简单期末卷子的区分度全靠“会设计算法”的大题拉开的而设计题最稳定的出题方向就是动规和贪心。复杂度分析是小题的稳定考点也是大题倒数第二问的常客。回溯和分支限界出现的频率稍微低一点但一旦考到手推状态空间树不会的人直接丢十几分。1.3 试卷的时间分配建议我考试时给自己定过一套时间分配实测有效。假设卷面2小时选择题/填空题控制在25分钟以内这些题看的是概念的准确性犹豫越久错得越多。递推方程求解这类计算题每道5-8分钟重点检查主定理的应用条件。算法设计大题留足45分钟以上宁可前面快速跳过不会的选择题也要保证大题完整写出状态转移方程和伪代码。最后留5分钟检查复杂度公式是否写反。2. 复杂度分析必练项递推方程求解的套路与主定理使用陷阱2.1 复杂度记号别只记符号含义要会判断“紧界”大O、大Ω、大Θ这三个记号是选择题的最爱但很多同学只背了“上界、下界、紧界”这几个字一放进具体表达式就懵。我的记法是拿打车费类比大O是“最贵不会超过多少钱”大Ω是“司机再怎么绕也至少收这么多”大Θ是“市场价稳定在一个区间既不超过也不低于”。判断两个函数谁增长快直接代n等于极大值看比值比如n²和n log n的关系代n100000算一遍就彻底记住n²增长快得多。考卷上常见的一组选择题是给一堆函数让你按渐近增长率排序我整理了一个速记序列O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)注意O(n log n)和O(n√n)谁增长快这类边角比较很少考但O(2ⁿ)和O(n!)的位置经常出现在选择题里千万别把阶乘排到指数前面去——指数函数和阶乘相比阶乘增长更快因为阶乘是连乘到n而指数只是连乘n个2。2.2 递推方程求解的三种常规武器期末考试递推方程的题目九成可以用三种方法之一解决代入法、递归树法、主定理。代入法的核心是“先猜后证”适合那种能凭直觉猜出答案的递推式。比如T(n)T(n/2)1你猜T(n)O(log n)然后用数学归纳法证明。这里有个细节证明时假设T(n/2)≤c·log(n/2)代入右边得到c·log(n/2)1 c·log n - c 1要让这个式子≤c·log n只要c≥1就行。很多同学归纳法证到一半就停写成“显然成立”在平时练习没问题考试改卷会扣步骤分。递归树法适合主定理搞不定的情况。以T(n)2T(n/2)n为例展开后每一层的综合代价都是n树共有log₂(n1)层总计n·log n。这个方法的好处是能直观看到总代价的增长来源坏处是写起来费时间考试时能认出主定时段就直接用主定理实在认不出再展开画树。2.3 主定理的三种情况以及最容易翻车的细节主定理说的是T(n)aT(n/b)f(n)其中a≥1b1f(n)是渐近正的函数那么情况1f(n)O(n^(log_b(a)-ε))ε0则T(n)Θ(n^log_b(a))。通俗讲就是f(n)增长比n^log_b(a)慢复杂度被叶子节点主导。情况2f(n)Θ(n^log_b(a))则T(n)Θ(n^log_b(a)·log n)。这是最常见的考法比如T(n)2T(n/2)nn^log₂2nf(n)n正好属于情况2答案Θ(n log n)。情况3f(n)Ω(n^(log_b(a)ε))ε0且a·f(n/b)≤c·f(n)c1则T(n)Θ(f(n))。此时复杂度被根节点主导。翻车点有两个。第一个是比较f(n)和n^log_b(a)要看多项式意义上的差距。如果f(n)n log nn^log_b(a)n你不能套情况3因为f(n)/n^log_b(a)log n增长比任何n^ε都慢这种情况主定理覆盖不了得用其他方法。第二个翻车点是忘了检查正则条件。情况3的a·f(n/b)≤c·f(n)如果不满足结果不一定正确考试里如果遇到了老老实实展开递归树。典型例题T(n)2T(n/2)n²n^log₂2nf(n)n²f(n)增长比n快得多且4·(n/2)²n²≤c·n²c1满足正则条件属于情况3答案Θ(n²)。T(n)4T(n/2)nn^log₂4n²f(n)n属于情况1答案Θ(n²)。这两个例子一对比就发现递归分解的“指数”a决定了树的宽度a越大叶子节点数量级越高就算合并的代价很小总复杂度也被叶子撑起来。3. 三大设计策略的重头戏分治、动态规划、贪心的题型模板3.1 分治先“分”后“合并”合并步才是复杂度来源分治的设计思路一句话把一个大规模问题拆成若干个规模更小的同类子问题分别解决后再把结果合并。递归出口通常是规模小到可以直接算。期末最常考的分治题目有三个归并排序、最大子段和、大整数乘法。归并排序一定要会写递归式和分析过程。T(n)2T(n/2)O(n)套主定理O(n log n)。值得注意的细节是归并的合并过程需要额外O(n)的辅助数组所以空间复杂度是O(n)。最大子段和是很多学校动规和分治都会出的题。分治思路把数组从中间切开最大子段和要么完全在左边要么完全在右边要么跨过中间。前两种情况递归解决第三种情况从中间往左右两边扩展找最大和合并时比较三者。时间复杂度T(n)2T(n/2)O(n)O(n log n)。这里想多说一句如果题目限定数组里可以包含负数一定要记得处理“整个数组全是负数”的边界情况最大子段和应该是最大的那个负数而不是0。大整数乘法考察的是对复杂度的直观感受。普通乘法要把n位整数拆成两半直接做4次乘法T(n)4T(n/2)O(n)主定理算出O(n²)。Karatsuba的优化思路是用3次乘法代替4次T(n)3T(n/2)O(n)算出来O(n^log₂3)≈O(n^1.585)。这个题如果作为解答题考核心得分点是“为什么把acbd拆成(ab)(cd)-ac-bd可以省一次乘法”一定要用自己的话把推导写清楚。3.2 动态规划期末大题的最稳定出题点动态规划的大题无论题目怎么变答题都按四步走定义状态→写转移方程→定初始化→定遍历顺序。这四个步骤写全了就算最终答案有偏差阅卷老师也能看到你的思路给分不会太难看。0-1背包是动态规划里最经典的题目。设dp[i][j]表示前i件物品装入容量为j的背包能获得的最大价值转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-wi] vi)其中wi是第i件物品重量vi是价值。初始化dp[0][j]0表示没有物品时价值为0。遍历顺序是先按物品遍历再按容量遍历。如果用了滚动数组优化只保留一维数组内层循环必须倒序遍历否则同一件物品会被重复选取变成完全背包。这一条是期末选择题里的高频陷阱。这里想补一个最近几年很多学校喜欢挖的变体物品重量和价值不再按顺序给而是交错出现或者要求在O(1)空间完成。空间优化只影响代码实现不影响状态定义和转移方程你把基础版本写对了优化是加分项。**最长公共子序列LCS**的答题模板更固定。dp[i][j]表示字符串A前i个字符和字符串B前j个字符的LCS长度。转移方程分两种情况如果A[i]B[j]dp[i][j]dp[i-1][j-1]1否则dp[i][j]max(dp[i-1][j], dp[i][j-1])。初始化dp[i][0]dp[0][j]0。填表时每个格子只依赖左边、上边和左上三个方向所以遍历顺序是外层A内层B顺序或倒序无所谓。如果题目要求输出具体子序列还需要加一个记录表标记每个格子是从哪个方向转移来的答题时从表格右下角回溯即可。矩阵连乘的转移方程和LCS长得像但含义完全不同。dp[i][j]表示从第i个矩阵到第j个矩阵全部相乘所需的最小标量乘法次数。转移方程dp[i][j] min(dp[i][k] dp[k1][j] p_{i-1}·p_k·p_j)其中k在i到j-1之间枚举划分点。这个题容易错的地方在于遍历顺序不是简单的i从小到大因为dp[i][j]依赖更大的区间dp[i][k]和dp[k1][j]必须先按区间长度从小到大计算。期末常考选择题“矩阵连乘应该怎么填表”答案就是按长度递推。3.3 贪心先证明局部最优能推出全局最优贪心算法在期末的考察分两个层面一是给出一个场景让你设计贪心策略并证明其正确性二是让你分析某个策略是否可行。很多同学只学会了“设计”而没有学会“证明”导致解答题丢分。活动安排问题的标准贪心策略是按结束时间从小到大排序每次选择结束时间最早且和已选活动不冲突的活动。为什么按结束时间早排序而不是按持续时间短排序因为结束时间早能给剩余活动留下更多时间空间这是一个可以严格证明的贪心选择性质。证明思路是反证法假设某个最优解中第一个活动不是结束时间最早的把它换成结束时间最早的活动新解不会比最优解差从而说明贪心选择的正确性。这个证明逻辑在期末解答题就是得分点我建议你把反证法的完整步骤写成自己能背下来的模板。哈夫曼编码考察频率也很高步骤是统计字符出现频率每次从最小堆中取出两个频率最小的节点合并新节点的频率是它们之和重新加入堆直到只剩一个节点。这个题不光考“怎么做”还经常考“编码长度怎么算”从根到叶子的路径长度就是编码长度叶子节点是字符深度对应编码位数。有些学校会要求你手动画出哈夫曼树再给出每个字符的编码画树的时候注意如果有两个节点频率相同合并顺序不影响总加权路径长度的最小值但会影响具体编码选择题遇到“唯一性”的描述果断判断错误。3.4 三者怎么选一个容易上头但必须冷静的场景判断题有些学校会把分治、动态规划、贪心放一起考判断题给一个场景让你选合适方法。我的判断顺序是子问题之间有没有重叠如果没有重叠分治优先如果大量重叠动态规划优先。当前选择会不会影响后续子问题的解空间贪心要求“当前最优就是全局最优的一部分”这个条件很难满足大多数题都不满足别一看能排序就选贪心。问题能不能通过“加上/不加当前元素”来递推如果能多半是动规。举个例子找零钱问题如果硬币面额是1、5、11找15块钱贪心会选1111115个硬币实际情况最优是5553个硬币。这就是典型看似能用贪心实则要用动态规划的场景。期末考这种“反直觉”题出现率不低。4. 回溯与分支限界解空间树、剪枝/限界函数的实战写法4.1 回溯法深度优先搜索剪枝先画出解空间树回溯法的本质是在解空间树上做带剪枝的深度优先搜索。期末最常考的三类问题0-1背包、N皇后、图的m着色其中0-1背包回溯和动规版本列在一起考察的概率很高。先说解空间树的类型0-1背包和子集和这类“在n个元素中选若干元素”的问题解空间是子集树节点数为2ⁿN皇后和旅行商这类“给n个元素排列”的问题解空间是排列树节点数为n!。考试简答经常问“某个问题的解空间规模是多少”这两个数字直接背下来。回溯框架的伪代码可以统一成void backtrack(当前层数 t): if t 超过最大层数: 记录/比较结果 return for 当前层的每个候选: if 剪枝条件满足: 剪枝 continue 更新状态 backtrack(t1) 撤销状态0-1背包的回溯解法要掌握两点一是排序策略按单位价值从大到小排二是上界函数。上界函数通常是“当前价值加上剩余剩余物品全部装入后按单位价值排序在上界内的最大价值”如果上界小于当前已找到的最优解直接剪枝。答题时别忘了说明剪枝函数设计得越好搜索空间越小这也是回溯题的第二问经常考察的内容——“如何设计剪枝函数提高效率”。N皇后问题是另一个高频考点。冲突判断条件是“同行、同列、同对角线”用数组记录已放置皇后时只需要判断列冲突和对角线冲突行冲突因为逐行放置天然避免。对角线冲突的判断等价于|row1-row2||col1-col2|。这个题的剪枝条件是“当前位置与已有皇后冲突”一旦冲突立即回溯不需要计算上界。期末如果要求你画出N皇后在n4时的部分解空间树一定要标清每层的分支和剪枝位置画树的评分标准通常是结点、分支、剪枝标记三项各占一部分分。4.2 分支限界法广度优先加限界函数重点在“界”分支限界法和回溯法的本质区别在于搜索方式回溯是深度优先分支限界是广度优先或优先队列最佳优先。分支限界主要用于求解最优解其核心是限界函数先估算每个分支可能达到的目标函数值上/下界超过当前最优界的节点直接丢弃不继续扩展。0-1背包的分支限界通常用优先队列实现队列按节点的上界值排序每次取出上界最大的节点扩展扩展时计算左孩子选第i件物品和右孩子不选的上下界如果某个孩子的上界不超过当前最优解右孩子等不可能产生最优解的分支剪掉。期末对这个部分的考察很少要求完整代码更多是选择题里区分“回溯法和分支限界法的区别是什么”答题要点是回溯法用于搜索所有可行解或某个可行解空间复杂度取决于解空间树的深度分支限界法通常用于求最优解空间复杂度更大因为它要维护活节点表队列或优先队列。4.3 回溯和分支限界的对比记忆维度回溯法分支限界法搜索策略深度优先广度优先/最佳优先空间复杂度O(树的高度)通常更大适用目标找所有解或任意解找最优解剪枝方式约束函数限界函数限界函数经典题目N皇后、图着色、0-1背包0-1背包、单源最短路径、任务分配这个表格自己在草稿纸上默写一遍比反复读教材更能形成记忆。注意有的学校会考“回溯法和分支限界法在0-1背包问题中的应用对比”答题时先写相同点都是解空间树上的搜索策略再写上面表格的差异基本可以拿满分。5. NP理论、近似算法、概率算法的简答考点速记5.1 P、NP、NPC、NP难四组概念别糊成一团期末简答最喜欢考这四组概念的区别我见过最多的错误答案是把NP写成“非多项式时间可解”这完全错了。P类存在多项式时间内解决的算法的问题。也就是能在O(n^k)时间内求出答案。NP类存在多项式时间内验证“某个候选解是否为解”的问题。注意NP的全称是Nondeterministic Polynomial不是Non-Polynomial。能快速验证解不代表能快速求解。NP完全NPC既是NP问题又属于NP难问题所有NP问题都可以多项式时间归约到它。NP难NP-Hard不要求本身是NP问题只需要所有NP问题都能多项式时间归约到它。所以NPC一定是NP难但NP难不一定是NP。常见的NPC问题列举SAT布尔可满足性、旅行商问题TSP、哈密顿回路、图着色、顶点覆盖、子集和。其中SAT是第一个被证明的NPC问题期末考试如果考“第一个被证明的NPC问题是什么”答案就是SAT别答成背包问题。背包问题属于NP难但需要在特定描述下才是NPC简答题别拿它举例。5.2 近似算法的近似比答题模板近似算法出现的背景对NPC问题我们不知道多项式时间内能不能求出精确最优解于是退一步求一个“足够接近最优解”的解并给这个接近程度一个数学度量这就是近似比。近似比ρ定义为近似解与最优解的比值最大化问题和最小化问题的定义方向不同考试常考最小化问题的形式即近似解/最优解≤ρ。期末常考用贪心算法求顶点覆盖问题近似比为2。证明思路贪心算法每次选择一条未被覆盖的边并把它两个端点都加入覆盖集合。每次这样选边时最优解至少要包含这条边的一个端点所以贪心选入的点数不超过最优解的两倍。这个证明过程在教材里是完整段落期末简答时按“选边→最优解必要条件→近似比”三段式写逻辑清晰。5.3 概率算法的四大家族概率算法这个模块有些学校讲得深有些学校只做了解要求我按完整考点整理你自己对照考纲取舍。概率算法在期末出现的常见形式是选择/填空题考点集中在四个类别数值随机算法用随机采样估算数值比如用蒙特卡洛法估算圆周率π撒点落进四分之一圆的频率趋近π/4。蒙特卡洛算法执行时间确定但结果可能出错错误概率可以通过多次执行降低。拉斯维加斯算法结果一定正确但执行时间是随机的比如随机快速排序选主元。舍伍德算法用于消除算法的最坏情况让算法在所有输入上的表现都比较均衡。判断题“蒙特卡洛算法一定给出正确答案”是陷阱题它的特点反而是“可能给错”所以它适合允许出现小概率错误的场景。拉斯维加斯算法如果失败可以重新运行因为失败时算法会报告“我没找到解”不会给出错误答案。6. 冲刺阶段高频易错点清单与答题评分规则6.1 五个最容易丢分的细节第一复杂度记号混淆算出一个算法最好情况是O(n)、最坏情况是O(n²)不能写“算法复杂度是O(n)到O(n²)”应该写“最好情况O(n)最坏情况O(n²)”。复杂度是一个函数不是一个区间。第二主定理应用时忘了检查a≥1且b1有些递推式形如T(n)T(n/3)T(2n/3)O(n)两个不同规模的子问题主定理的a/b形式不适用这时候递归树展开每层代价是O(n)共有O(log n)层结果O(n log n)。这类“变体递推”经常作为压轴小题出现。第三动规的初始化条件漏一个大边界0-1背包的dp[0][j]和dp[i][0]都要初始化LCS的dp[i][0]和dp[0][j]也要初始化少一个填表第一行/第一列全错。答题的时候先把表格的0行0列标出来再写转移方程阅卷老师一眼能看出你的严谨程度。第四贪心问题不写证明很多同学设计出贪心策略就以为答题结束但解答题要求的是“策略正确性证明复杂度分析”三件套正确性证明用反证法或归纳法写不长但必须有。没有证明的贪心题答案在改卷时最高只能拿一半分。第五回溯的剪枝函数和限界函数混为一谈剪枝函数是约束函数判断当前解是否满足题目约束限界函数估算当前分支的目标函数上界用于剪掉不可能产生更优解的分支。0-1背包回溯中这两个都出现答题时分开写。6.2 算法设计大题的答题模板期末算法设计题的阅卷逻辑是按步骤给分。我强烈建议你按下面这个顺序答题保证步骤清晰明确子问题/状态定义一句话说清楚dp[i][j]或者函数solve的输入输出含义。写出递推方程或关键逻辑数学表达式优先。说明初始化和遍历顺序动规题必须写回溯题写递归出口。给出伪代码或关键代码片段不用写完整可编译代码但核心逻辑要完整。分析时间/空间复杂度写O(n²)这类记号加一句说明来源。我见过学弟学妹吃大亏的场景动规大题状态定义对了转移方程对了结果遍历顺序写错整张表填出来是错误的答案这个大题就从“接近满分”滑到“勉强给一半”。考试时答完题花30秒自查一遍遍历顺序非常值得。6.3 考前一周的实操安排最后一星期不建议再啃新题。把教材或老师PPT里所有例题的递推方程自己抄一遍然后每个题口算一遍复杂度。接着刷3-5套历年真题或课后典型题重点练“限时写出完整答案”的能力。临考前一夜把主定理三种情况、0-1背包的转移方程、贪心三件套答题模板、N皇后的冲突判断条件再过一遍这些是高频保分点。这门课复习的本质是练“条件反射”——看到“最大价值”反射出dp和背包看到“两字符串最长公共”反射出LCS的转移方程看到“最小生成树”“最早结束时间”反射出排序加贪心。你要的不是看懂每一个证明细节而是把那些最核心的模型刻进脑子里考场上能稳定输出。我从自己带过的学生复习数据看把本文提到的每道经典题独立写一遍、不看书自己推导出结果的同学期末成绩普遍在85分以上。这门课不考天赋考熟练度。刷就完了。