算法设计与分析这门课的期末试卷几乎是每个计算机相关专业学生都要正面硬刚的一场硬仗。它不像数据结构那样偏重你记不记得这个结构怎么操作也不像高等数学那样考计算熟练度——它考的是一种更上层的能力给你一个从没见过的问题你能不能在十几分钟内判断它该用分治、动态规划还是贪心然后把状态定义、转移方程、复杂度一道推下来。很多人复习时把课件翻了三遍一到考场上遇到请设计一个 O(n log n) 的算法求解下列问题就脑子空白根本原因是没搞清这门课的命题逻辑。这篇东西我想从一个做过题、带过人、也踩过坑的角度把算法设计与分析期末试卷这件事彻底拆开它的考点地图长什么样高频题型背后想考什么计算题和设计题的标准解法套路是什么以及考场上真正会失分的地方在哪里。不管你是在临时抱佛脚还是想提前一学期把节奏铺好这里的内容都能直接拿去用。1. 试卷整体设计与命题思路拆解1.1 这门课的知识地图到底铺了多宽算法设计与分析的课程内容看着杂其实主干非常清晰就五根柱子复杂度分析、算法设计范式、图算法、难解性与归约、以及工程化的算法选择。复杂度分析是所有题的地基它决定了你后面每一个答案能不能自圆其说设计范式是核心通常包括分治、动态规划、贪心、回溯、分支限界、随机化这几类图算法是应用最密集的一块最短路、最小生成树、最大流、拓扑排序、强连通分量都在这难解性部分讲 P、NP、NPC、NP-hard 以及多项式归约最后一块经常被学生忽略就是给定场景选算法的综合题。期末试卷的覆盖面基本会照着这个地图走但权重从来不是平均的。动态规划通常吃掉整张卷子 25% 到 35% 的分值因为它是唯一一个既能考建模、又能考计算、还能考证明的范式分治次之主要考递归式求解和主定理贪心往往和证明题绑定图算法一般以一道大题的形式出现要么手算表格要么写伪代码NP 部分通常是一道小题加一道归约证明分值不高但极其容易翻车。我的经验是考前如果只有两天复习时间你会想把 70% 的精力压在 DP 和图算法上——这两块的内容密度和出题频率远高于其他章节。分治的递归式求解是会了就拿分的送分题投入产出比极高值得单独花两小时吃透。1.2 一张典型卷子的题型结构与分值权重把近几年不同院校的算法期末卷放一起对比结构惊人地相似。下面这张表是我整理的典型结构你可以拿去对照自己学校的卷子看看哪里被加强、哪里被弱化。题型常见分值主要考查能力拿分难度选择/填空15-20 分概念记忆、复杂度常识低但要细心简答/名词解释10-15 分定义复述与理解低计算题20-30 分手算流程、递归式、表格填充中算法设计题25-35 分建模、伪代码、复杂度分析高证明题10-15 分正确性、归约、最优子结构高编程/伪代码实现5-10 分落地能力中从这张表能读出一个很关键的信号选择和填空加起来只占不到 20%剩下的 80% 都是你得动笔推的题。这直接决定了复习策略——死背名词解释顶多保住及格线真正拉开差距的是计算题和设计题能不能写出规范的过程。另外一个细节是很多卷子会在计算题里塞一道陷阱题比如给一个不满足主定理条件的递归式或者给一个用贪心会出错、必须用 DP 的背包变种。这类题的用意不是刁难而是筛掉那些只会套模板、不理解适用条件的人。1.3 命题背后的能力分层逻辑我更愿意把这张卷子理解成一个四层的过滤器每一层对应一种能力分值也大致按这个梯度往上走。第一层是记忆层考渐进记号的严格定义、各种排序的稳定性、常见算法的时间复杂度。这一层的题几乎不需要思考属于你看过就能答。第二层是理解层考你知不知道某个算法的前提假设。比如 Dijkstra 为什么不能处理负权边Floyd 为什么能处理负权但不能处理负权环Kruskal 依赖的并查集为什么能做到近似常数时间。这一层开始需要解释为什么而不是是什么。第三层是应用层也就是设计题的主战场。给你一个具体场景比如某仓库有一排货架每次能搬走相邻的一段……让你判断这是区间调度、背包还是编辑距离的变体然后建状态、写转移。第四层是分析层包括正确性证明、复杂度下界、多项式归约。这一层考的是你能不能说服阅卷人你的算法是对的也是最容易只写结论不给理由、被扣掉一半分的地方。说实话我见过太多人卡在第三层和第四层之间他其实能写出正确的 DP 转移方程但让他在答案里解释为什么这个状态定义是完备的就说不出来了。阅卷老师哪怕知道他答案对也会因为过程缺失扣分。2. 核心考点细节解析与高频陷阱2.1 复杂度分析定义证明才是真考点渐进记号那套定义几乎所有卷子都会考但形式非常固定。你要把五个记号的定义背到条件反射的程度O 是存在 c 和 n₀ 使得对所有 n ≥ n₀ 有 f(n) ≤ c·g(n)Ω 是不等号反向Θ 是两者同时成立小 o 要求的是对任意常数 c 都成立且通常要求 c 可以任意小小 ω 同理反向。题目最喜欢的形式是用定义证明 3n² 5n 7 Θ(n²)。标准写法是取 c₁ 3、c₂ 15、n₀ 1然后分别证明上下界。这里有个细节很多人栽n₀ 的选择不是唯一的你只要给出一个可行的就行但必须显式给出。我见过有同学写了一大堆不等式推导最后忘了写取 n₀ 1硬生生被扣分。还有个高频陷阱是渐进复杂度不等于实际快慢。两个都是 O(n log n) 的算法常数因子可能差三倍。卷子上如果问下列算法中最坏情况下最优的是通常比的是渐进阶但如果问实际运行更快的是就得考虑输入规模和常数了。审题时把这两种表述区分清楚比多背两个公式有用得多。2.2 主定理与递归式会解和不会解的分水岭分治题的灵魂是递归式求解。主定理给的是三种情况判断依据是比较 f(n) 和 n^(log_b a) 的大小关系。我把这个判断流程整理成一张速查表考场上可以照着走。比较关系情形结果例子f(n) 多项式地小于 n^(log_b a)情况一T(n) Θ(n^(log_b a))T(n)8T(n/2)n²f(n) 与 n^(log_b a) 同阶情况二T(n) Θ(n^(log_b a) · log n)T(n)2T(n/2)nf(n) 多项式地大于且满足正则条件情况三T(n) Θ(f(n))T(n)2T(n/2)n²多项式地这三个字是判断的关键。如果 f(n) 只比 n^(log_b a) 大一个 log 因子比如 T(n) 2T(n/2) n log n主定理的三种情况都不适用你得改用递归树或代入法答案是 Θ(n log² n)。这种题专门用来筛只会套公式的人遇到的时候千万别硬套直接在答案里说明主定理不适用改用递归树然后画树、分层求和反而能拿全分。代入法也叫猜测-验证法的规范写法是三步先猜出解的形式再代入递归式验证最后用归纳法证明边界成立。很多人只猜不证或者猜完代进去算对了就收笔实际上证明部分才是这道题的分所在。2.3 动态规划状态定义决定了你 80% 的分数DP 题的评分标准很现实状态定义写对得分就过半转移方程写对基本满分过程再规范点就是高分。反过来状态定义错了后面写得再长都是零分。我把 DP 的解题过程固化成五个动作考场上按顺序做就行。第一步是判断有没有最优子结构和重叠子问题这两个条件缺一不可缺了就该换范式。第二步是定义状态通常用 f[i] 表示以第 i 个元素结尾的最优值或 f[i][j] 表示前 i 个和前 j 个的最优匹配。第三步是写出转移方程这一步要覆盖所有决策分支不能漏。第四步是确定边界条件和填表顺序比如 0-1 背包必须倒序枚举容量LCS 必须按行或按列从小到大填。第五步是给出答案所在的格子很多人算完整个表却答错了最终值的位置。几个高频模型的转移方程必须背熟最长公共子序列LCS如果两个字符相等f[i][j] f[i-1][j-1] 1否则 f[i][j] max(f[i-1][j], f[i][j-1])。0-1 背包f[j] max(f[j], f[j-w[i]] v[i])容量维度倒序。最长递增子序列O(n²) 版本是 f[i] 1 max{f[j] | j i 且 a[j] a[i]}O(n log n) 版本用 tail 数组做二分。矩阵链乘m[i][j] min{ m[i][k] m[k1][j] p[i-1]·p[k]·p[j] }按链长从小到大填。坑最多的是0-1 背包和完全背包的枚举顺序。这个区别不是死记硬背能解决的得理解倒序是为了保证每个物品只被用一次正序会让同一件物品被重复放入。卷子上如果把每件物品无限件和每件物品一件混在一道题里考八成就是冲着这个知识点来的。2.4 贪心写对了算法不等于拿到了分贪心题最容易被低估。很多同学写出一个看起来正确的贪心策略就收笔了结果证明题部分一分没拿。这里的关键认知是贪心算法的正确性不是显而易见的必须用交换论证exchange argument或拟阵理论来证。交换论证的标准结构是三步。先假设存在一个最优解 OPT然后找出 OPT 与贪心解 G 的第一个不同决策把 OPT 里的那个选择换成 G 的选择证明换完之后解不会变差最后用归纳法说明可以一直换下去直到 OPT 变成 G。听起来抽象但落到具体题上非常套路化比如区间调度题交换论证的核心就是最优解里第一个结束的区间一定能换成贪心选的那个最早结束的区间且不影响后续选择。判断一道题能不能用贪心经验上有两个信号一是问题有没有选择后不影响后续的性质也就是贪心选择性质二是能不能找到一个反例。后者更实用——考试前你如果能记住几个经典反例比如0-1 背包不能用贪心反例容量 10物品 (6, 6)、(5, 5)、(5, 5)遇到类似题就能立刻判断该用 DP。下面这张表是我归纳的该用哪个范式的判断依据做题时可以先扫一遍。问题特征首选范式典型题目可分解为独立子问题子问题不重叠分治归并排序、快排、最近点对子问题重叠需要最优子结构动态规划背包、LCS、编辑距离有贪心选择性质局部最优即全局最优贪心区间调度、Huffman、最小生成树解空间是树形结构需要剪枝回溯/分支限界N 皇后、TSP、装载问题规模大、允许近似精确解太难近似算法顶点覆盖、TSP 近似2.5 图算法与 NP 归约两道高频证明题图算法的手算题几乎必考。Dijkstra 的表格填充、Floyd 的三重循环矩阵更新、Prim 和 Kruskal 的边选择过程、拓扑排序的出队顺序这些都是按流程走就能拿分的题。但有两个地方特别容易出错。第一个是Dijkstra 手算时忘记更新 dist 数组的松弛条件。规范做法是每一步都画出 dist 表和已确定集合 S每一步只把当前最近的未确定点加入 S然后用它松弛邻居。考官看的不是你的最终答案而是你的过程有没有体现松弛操作。第二个是Floyd 的三重循环顺序。k 必须放最外层因为它的物理含义是允许经过的中间点集合逐步扩大。如果你把 k 放到最内层算法含义就变了这是常见错误。NP 归约题的套路非常固定。题目通常给两个问题 A 和 B让你证明 A ≤ₚ B 或者证明某个问题是 NP-hard。归约的方向是最容易搞混的地方要证明 B 是 NP-hard你需要找一个已知的 NP-hard 问题 A把 A 归约到 B也就是A 的任意实例都能在多项式时间内转成 B 的一个实例且答案一致。方向写成 B 归约到 A 就完全反了这道题直接归零。典型归约链要记住3-SAT → 团问题 → 顶点覆盖 → 集合覆盖 → 哈密顿回路 → TSP。这条链上任意两个节点之间的归约考试都有可能让你补一段。我的建议是至少把3-SAT 归约到团这个经典构造背下来因为它的构造手法用子句和文字构造图是很多题目的模板。3. 完整试卷模拟与逐步拆解接下来这部分是实战。我按一套 100 分的标准卷来写题目难度参照多数院校的中上水平每题都给出答案和必要的解题过程。你可以先自己写再对答案。3.1 选择题与填空题附解析题目 1下列关于渐进记号的表述正确的是 A. 如果 f(n) O(g(n))那么 g(n) O(f(n)) B. 如果 f(n) Θ(g(n))那么 f(n) O(g(n)) 且 f(n) Ω(g(n)) C. 如果 f(n) o(g(n))那么 f(n) Θ(g(n)) D. n log n O(n)答案B。A 显然错反例是 n O(n²) 但 n² ≠ O(n)C 把小 o 和 Θ 搞混了D 的 n log n 增长速度超过 n不成立。题目 2关于 Dijkstra 算法下列说法正确的是 A. 可以处理负权边 B. 时间复杂度在用二叉堆优化下是 O((VE) log V) C. 只能求单源最短路不能求全源最短路 D. 相当于对图做一次广度优先搜索答案B。A 是经典陷阱负权边会让已确定的最短路被推翻C 表述本身看着对但其实可以用它跑 V 次求全源D 只在边权全为 1 时成立。题目 3以下问题中属于 NP 完全的是 A. 排序 B. 单源最短路 C. 0-1 背包的判定版本 D. 最大流答案C。0-1 背包的判定版本是 NP 完全的而它的最优化版本是 NP-hard。这里要特别注意判定版本和最优化版本的区别很多卷子就考这个点。题目 4用主定理求解 T(n) 4T(n/2) n结果是 A. Θ(n²) B. Θ(n log n) C. Θ(n² log n) D. Θ(n)答案A。这里 a4b2n^(log₂4) n²f(n) n 多项式地小于 n²属于情况一结果是 Θ(n²)。3.2 计算题矩阵链乘的手算填表题目给定矩阵链 A₁A₂A₃A₄维度分别为 10×20、20×5、5×40、40×25求最优加括号方式和最小乘法次数。解题过程先把维度数组写成 p [10, 20, 5, 40, 25]p[i-1] × p[i] 是第 i 个矩阵的行列数。然后按链长 L 从 2 到 4 依次填表。链长为 2 时m[1][2] 10×20×5 1000m[2][3] 20×5×40 4000m[3][4] 5×40×25 5000。链长为 3 时m[1][3] 要比较 k1 和 k2 两种情况k1 时代价为 m[1][1] m[2][3] 10×20×40 0 4000 8000 12000k2 时代价为 m[1][2] m[3][3] 10×5×40 1000 0 2000 3000取小的 3000。链长为 4 时m[1][4] 比较三个 k 值。k1m[1][1] m[2][4] 10×20×25其中 m[2][4] 需要先算出来。这里就体现出填表顺序为什么必须是按链长递增——外层循环枚举链长才能保证计算 m[i][j] 时所有更短的子链都已经算好。最终结果是 m[1][4] 11000最优加括号方式是 (A₁)((A₂A₃)A₄) 或类似形式具体看 s 表的记录。注意这道题的手算过程一定要把 m 表和 s 表都画出来光写一个最终答案通常只能拿一半分因为阅卷是按过程给分的。3.3 算法设计题从场景到状态定义题目某物流站有一排共 n 个包裹第 i 个包裹重量为 w[i]、价值为 v[i]。现在有一辆容量为 C 的车每个包裹要么装要么不装求能装走的最大总价值。这题就是标准的 0-1 背包。状态定义f[j] 表示容量为 j 时能获得的最大价值。转移方程对每个物品 i倒序枚举 j 从 C 到 w[i]执行 f[j] max(f[j], f[j-w[i]] v[i])。边界是 f[0..C] 全部初始化为 0。时间复杂度 O(nC)空间复杂度 O(C)。关键是要在答案里解释为什么用滚动数组而不是二维数组以及为什么容量维度要倒序。前者是为了把空间从 O(nC) 降到 O(C)后者是为了保证每件物品只被选中一次。这两句话写上去就是区分背模板和真懂的地方。Python 实现如下def knapsack_01(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): # 倒序是关键 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity] # 测试 w [2, 3, 4, 5] v [3, 4, 5, 6] print(knapsack_01(w, v, 8)) # 输出 103.4 证明题:贪心正确性的交换论证题目给定 n 个区间 [sᵢ, fᵢ]选择尽可能多的互不重叠区间。按结束时间升序的贪心策略是否正确证明你的结论。这是经典的区间调度问题贪心策略是正确的。证明用交换论证假设 OPT 是一个最优解且 OPT 中的区间按结束时间排列为 o₁, o₂, ..., oₖ。贪心解 G 的第一个区间是 g₁它是所有区间中结束时间最早的。因为 g₁ 的结束时间 ≤ o₁ 的结束时间且 o₁ 是 OPT 中最早结束的所以把 o₁ 换成 g₁ 之后g₁ 与 o₂ 一定不重叠因为 g₁ 结束得更早。替换后的解仍然是合法解且区间数量不变所以也是最优解。接下来对剩余区间递归地用同样的论证最终得到 G 和 OPT 数量相同贪心正确。提示这道题的采分点是两个关键性质——g₁ 与后续区间不重叠以及更早结束的区间对后续约束更弱。能写出这两句话基本就是满分回答。3.5 编程题三个必写模板编程题通常要求用伪代码或指定语言实现下面给出三个最常考的模板都属于写出来就能拿分的题。最长公共子序列def lcs(a, b): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[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]堆优化版 Dijkstraimport heapq def dijkstra(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist快速选择求第 k 小import random def quickselect(arr, k): if len(arr) 1: return arr[0] pivot random.choice(arr) left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] if k len(left): return quickselect(left, k) elif k len(left) len(mid): return pivot else: return quickselect(right, k - len(left) - len(mid))这三个模板覆盖了 DP、图算法、分治三大块。写的时候要注意if d dist[u]: continue这个剪枝不能省有人写堆优化 Dijkstra 忘了这一步会导致同一个点被反复入堆理论复杂度退化。4. 常见问题与排查技巧实录4.1 失分点速查表带过几轮复习之后我发现学生翻车的点高度集中。下面这张表是我从作业和试卷里整理出来的对号入座看看你中了几条。症状根因纠正方法DP 状态定义写了但转移算错没覆盖所有决策分支每次写完转移手动枚举小规模输入验算贪心题只给策略不给证明不知道证明是采分点记住交换论证三步法强制写进答案复杂度分析只给结论漏了 n₀ 和常数 c定义证明必须显式写出 c 和 n₀归约方向写反没搞清楚谁归约到谁记住要证 B 难就把已知难的 A 归约到 B主定理乱套没检查多项式地这个条件遇到带 log 的 f(n) 先怀疑主定理失效手算最短路不画中间表以为答案对就行每步画 dist 表和 S 集合过程给分编程题超时用了朴素实现记住堆优化、滚动数组、埃氏筛这些常见优化其中我觉得最值得展开讲的是DP 状态定义写了但转移算错。这不是能力问题是习惯问题。我的做法是每次写完转移方程都拿一个 3×3 或者 4×4 的小例子手动跑一遍看看边界和值对不对。这个动作只要一分钟能省掉后面二十分钟的返工。我见过太多人交卷后才意识到自己某个下标写反了。4.2 考场时间分配与答题顺序150 分钟的卷子我的建议时间分配是这样的选择填空 20 分钟简答 15 分钟计算题 40 分钟算法设计题 50 分钟证明题 20 分钟检查 5 分钟。这个分配的底层逻辑是把分值密度最高的题放在状态最好的时间段做。具体操作上我会先通读全卷用铅笔在题号旁标注难度一星到三星。然后按一星 → 二星 → 三星的顺序做。不要按题号顺序硬推因为前面一道卡壳的大题会严重影响后面的心态和时间。算法设计题就算一时想不出最优解也可以先把暴力解法写上去很多卷子对暴力解法给 30% 到 50% 的分空着是零分。还有一个很实际的技巧证明题和设计题的答案要分层写。先写我的思路是……再写具体步骤……最后写复杂度分析……。分层的答案即使某一部分错了阅卷老师也能清楚看到你哪部分是对的按点给分。4.3 从判卷视角看失分我帮老师看过几轮卷子站在判卷的位置会发现一些平时完全想不到的事。最典型的是写得多的不一定得分高写得有条理的一定得分高。有的同学把整页纸写满推导七八行但状态定义藏在中间某行转移方程写在边上阅卷老师得费劲找——这种情况下即使全对也容易被误判。反过来把状态定义 / 转移方程 / 边界 / 复杂度四行分点写清楚老师扫一眼就给了满分。其次是符号规范。用 f[i][j] 也好用 dp[i][j] 也好只要前后一致就行但如果前面用 f、后面用 d老师会怀疑你自己都没想清楚。下标的含义一定要在第一次出现时用一句话说明比如f[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列长度。最后透露一个规律设计题的最后一小问通常是分析你算法的时间复杂度这问分值不高但极容易拿。哪怕你前面的伪代码写得一般只要复杂度分析写对这一问的分就稳了。很多人在前面耗光时间最后这一问空着非常可惜。4.4 复习路径与投入产出比如果你现在距离考试还有两周以上我建议按这个顺序推进。第一周铺基础把复杂度分析、分治递归式、五大 DP 模型过一遍每天手写两道计算题重点是矩阵链乘、LCS、背包的填表。第二周攻专题图算法一天Dijkstra、Floyd、Prim、Kruskal、拓扑排序手算各两遍NP 归约一天背熟归约链和三个经典构造贪心证明一天交换论证写五遍直到形成肌肉记忆。剩下的时间做两套完整模拟卷严格计时。如果只剩三天那就把资源全部压在三个点上递归式求解、DP 状态设计、Dijkstra 与 Floyd 手算。这三块加起来通常能覆盖 45% 到 55% 的分值而且是练了就有分的类型。NP 归约如果时间实在不够至少要背下3-SAT 归约到团这一个构造因为它是很多变体的母题。我个人在实际复习和帮别人复习的过程中发现算法设计与分析这门课最大的敌人不是难度而是以为看懂了。翻课件的时候每一页都眼熟一合上书什么都写不出来这是最危险的状态。判断自己有没有真懂只有一个标准拿一张白纸不看书把矩阵链乘的填表过程完整写出来把区间调度的交换论证完整写出来把 3-SAT 归约到团的图构造完整画出来。能独立完成这三件事这张卷子你基本就稳了。做不出来的部分就是你该补的地方——不用猜白纸会告诉你答案。