算法设计与分析这门课的期末复习跟背概念型的科目完全不是一个路数。它更像是健身——你看再多教程不动手推一遍递推式、不亲手把矩阵链乘的表填满考场上照样卡壳。我这篇东西写给两类人一类是平时作业抄得比较顺手、考前两周才发现自己连主定理都记混的另一类是基础还行但面对编程题分析题证明题混编的卷子不知道从哪儿下手的。核心就讲一件事怎么用最短的时间把散落在十几章里的算法思想串成一条线再针对期末题型做定向突破。下面所有内容都是我自己和身边同学反复试错后留下的东西包括哪些章节可以战略性放弃、哪些题型几乎年年出现、手算题怎么把表格填得又快又不出错。我会尽量把为什么这么复习讲清楚而不是只给你一份知识点清单——因为这门课真正的考点从来不是知识点本身而是你能不能在陌生问题面前把已有工具用对。1. 先搞清楚这门课到底考什么考点分布与复习优先级1.1 课程骨架五大思想与三大分析工具不管你用的是哪本教材算法设计与分析的骨架基本是固定的分治、动态规划、贪心、回溯含分支限界、图算法这五大块是毫无争议的必考区再往外延一点可能还有NP完全性理论和近似算法但这两块在期末卷里通常只占一道概念题或判断题的分量。很多同学复习时犯的第一个错误是把算法和分析割裂开看。实际上这门课的每道题几乎都是双层的上层是你选哪个算法思想来解这个问题下层是这个解的时间复杂度是多少、怎么证明。所以我建议你在复习每一个算法时都强制自己回答三个问题它的核心思想一句话是什么、它的递推式或状态转移怎么写的、它的复杂度怎么算出来的。这三个问题答不上来说明这块还没过关。分析工具那边真正高频使用的其实只有三样渐进记号O、Ω、Θ、o的严格定义、递推式的求解方法主定理、递归树、代入法、以及摊还分析的基本概念。其中渐进记号的严格定义经常以证明题的形式出现比如让你证明 $3n^25n2 \Theta(n^2)$或者判断 $2^{n1}$ 和 $2^n$ 之间的关系。这类题的套路性极强属于复习两小时、稳定拿分的送分题一定要优先拿下。1.2 从题型反推复习顺序哪些必考哪些可以放弃我观察过好几套不同学校的期末卷题型分布相当稳定大致是这么个比例题型典型分值与题量复习优先级说明选择题/填空题20~30分中覆盖面广但难度低靠刷真题解决复杂度分析题10~15分高主定理、递归式求解套路固定手算/填表题20~30分最高矩阵链乘、LCS、哈夫曼、最短路径等算法设计题20~30分高给一个实际问题要求设计算法并分析编程题20~30分高现场写代码或补全代码证明题10分左右低多为渐进记号定义、贪心正确性证明从这个表能看出来手算填表题和算法设计题加起来能占到一半的分而这两块恰好是最需要动笔练的。我个人的复习顺序建议是先花两天把复杂度分析的基本工具过一遍这是所有题的地基然后集中三到四天攻克动态规划和贪心的手算题最后两天练算法设计和编程题的模板。图算法和回溯穿插着看NP理论留到最后半天扫一遍概念就够。注意选择放弃某个章节之前先翻一遍近三年的卷子确认它真的没出现。我见过有人听信分支限界不考的说法直接跳过结果那年出了一道用优先队列式分支限界解装载问题的题。2. 复杂度分析所有题目的地基2.1 渐进记号与常见复杂度速查渐进记号的严格定义是必背内容尤其是大O的定义$f(n) O(g(n))$ 当且仅当存在正常数 $c$ 和 $n_0$使得对所有 $n \geq n_0$都有 $0 \leq f(n) \leq c \cdot g(n)$。这个定义看着简单但考试里喜欢考它的边界情形。比如一个经典陷阱$n O(n^2)$ 成立吗成立因为取 $c1$、$n_01$ 就有 $n \leq n^2$。但反过来说 $n^2 O(n)$ 就不成立因为无论取多大的 $c$随着 $n$ 增大 $n^2$ 总会超过 $c \cdot n$。这个渐进行为的理解是整个分析部分的核心。再比如 $2^{n1} O(2^n)$因为 $2^{n1} 2 \cdot 2^n$取 $c2$ 即可。但 $2^{2n} O(2^n)$ 不成立因为 $2^{2n} 4^n$指数底数不同增长速度天差地别。这类判断几乎每次考试都会出现一两道。常见复杂度的增长顺序建议背熟从慢到快$$O(1) O(\log n) O(\sqrt{n}) O(n) O(n\log n) O(n^2) O(n^3) O(2^n) O(n!)$$我在复习时会在草稿纸上默写这条链然后在每个记号旁边标注一个对应的算法例子比如 $O(n\log n)$ 对应归并排序、$O(2^n)$ 对应朴素递归求斐波那契。有了具体例子判断两个复杂度谁涨得快时就基本不会错。2.2 主定理的实战用法与三种情况对照主定理是求解形如 $T(n) aT(n/b) f(n)$ 这类递推式的利器其中 $a \geq 1$、$b 1$。它的核心思路是比较两个量的大小一个是子问题分裂带来的开销 $n^{\log_b a}$另一个是合并或分解本身的额外开销 $f(n)$。情况条件结果直观理解情况1$f(n) O(n^{\log_b a - \epsilon})$某个 $\epsilon0$$T(n) \Theta(n^{\log_b a})$叶子节点开销占主导合并开销可忽略情况2$f(n) \Theta(n^{\log_b a})$$T(n) \Theta(n^{\log_b a} \log n)$每层开销相当总共多了个 $\log n$情况3$f(n) \Omega(n^{\log_b a \epsilon})$ 且满足正则条件$T(n) \Theta(f(n))$根节点开销占主导向下递归可忽略实际考试里情况1和情况2出现的频率最高。拿归并排序举例$T(n) 2T(n/2) n$这里 $a2$、$b2$所以 $n^{\log_b a} n^{\log_2 2} n^1 n$。而 $f(n) n$恰好等于 $n^{\log_b a}$属于情况2所以 $T(n) \Theta(n \log n)$。这个推导过程几乎是必考内容我建议你练到闭着眼睛都能写出来。再举一个情况1的例子$T(n) 8T(n/2) n^2$。这里 $a8$、$b2$$n^{\log_b a} n^{\log_2 8} n^3$。而 $f(n) n^2$明显小于 $n^3$属于情况1所以 $T(n) \Theta(n^3)$。提示用主定理之前务必先检查递推式是否满足标准形式。如果子问题规模不是严格均分的比如 $T(n) T(n/3) T(2n/3) n$主定理的三种情况下都用不了这时候得换递归树法。2.3 递归树法与代入法验证主定理虽然好用但它有覆盖不到的地方这时候递归树法就是主力。递归树法的核心做法是把每一层的开销加起来然后对所有层的开销求总和。以 $T(n) T(n/3) T(2n/3) n$ 为例。这棵树每次分裂成两个规模分别为 $n/3$ 和 $2n/3$ 的子问题树的最深路径是一路走 $2n/3$ 那条所以树高约为 $\log_{3/2} n$。而每一层的总开销都是 $n$因为所有子问题的规模加起来还是 $n$再加上每层分解本身的开销。所以总复杂度是 $O(n \log n)$。代入法的用途是验证你猜的答案对不对它的思路是先猜一个上界然后用数学归纳法证明它成立。比如猜 $T(n) \leq cn\log n$代入递推式假设对小于 $n$ 的规模都成立然后做代数化简看看能不能推出 $T(n) \leq cn\log n$。代入法容易踩的坑是猜界的松紧。如果猜得太松比如猜 $T(n) O(n^2)$虽然也能证出来但得不到紧确界考试里通常会扣分。所以还是先用主定理或递归树求出紧界再用代入法验证比较稳妥。3. 五大算法思想的独立突破路线3.1 分治法从归并排序到最近点对分治的三步走——分解、解决、合并——几乎人人都会背但考试考的是你能不能把这三步具体化到一个陌生问题上。归并排序是最标准的模板它的关键点在于合并操作的实现。很多同学手写归并排序时会在边界处理上出错我的经验是用两个哨兵值简化合并逻辑def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result最近点对问题是分治部分的经典难题它的考点不在于代码而在于理解为什么能优化到 $O(n \log n)$。朴素做法是两两比较复杂度 $O(n^2)$。分治做法是把点集按 $x$ 坐标排序后一分为二分别求出左右两半的最近距离 $d_l$ 和 $d_r$令 $d \min(d_l, d_r)$。然后关键来了只需要检查中线两侧宽度为 $d$ 的条带区域内的点。而且在条带内每个点只需要和它后面最多 7 个点比较——因为可以证明如果两个点距离小于 $d$它们一定落在同一个 $d/2 \times d/2$ 的小方块里而每个方块内最多 1 个点。这个最多比较 7 个点的结论是考试常考的分析点它的推导过程是把 $d \times 2d$ 的矩形划分成 6 个 $d/2 \times d/2$ 的小格子每个格子内最多 1 个点否则这两个点距离小于 $d$与 $d$ 是左右两边最近距离矛盾所以每个点最多和其他 5 个点在格子内相邻加上自身实际比较次数上界是 7 次。这个数字我建议直接记住结论推导过程理解清楚就好。3.2 动态规划状态定义的三个判断标准动态规划是整门课最核心也是最容易翻车的部分。它的难点不在代码而在于状态怎么定义。我总结了一个三问法来判断状态定义是否合理第一问状态能不能唯一确定一个子问题的答案如果两个不同的状态对应同一个子问题说明定义有冗余。第二问状态转移方程是不是只依赖规模更小的状态如果转移方程里出现了规模相同的状态说明没有形成无后效性。第三问最优子结构成立吗也就是最优解是不是由子问题的最优解拼出来的。以 0-1 背包为例。状态定义是 $dp[i][j]$ 表示前 $i$ 件物品、容量为 $j$ 时的最大价值。这里 $i$ 和 $j$ 共同唯一确定了一个子问题转移方程 $dp[i][j] \max(dp[i-1][j], dp[i-1][j-w_i] v_i)$ 只依赖 $i-1$ 行最优子结构也成立。三个问题全部通过定义就是合理的。用这个三问法去检查最长公共子序列LCS的状态定义$dp[i][j]$ 表示字符串 A 的前 $i$ 个字符和字符串 B 的前 $j$ 个字符的最长公共子序列长度。同样三个问题都能过。这时候你会发现DP 的状态定义其实有很强的规律性通常是前 i 个这种前缀形式的组合。3.3 贪心法什么时候能贪什么时候不能贪心是看起来最简单、用起来最容易翻车的思想。它的核心是每次选择当前看来最优的选项但这样做不一定能保证全局最优——经典的反例是 0-1 背包问题按单位价值贪心会得到错误答案。而分数背包问题就可以贪心求解因为物品可以分割贪心选择单位价值最高的物品总能保证最优。这两个问题的对比几乎是年年必考的经典案例我建议你把它的证明过程背下来为什么分数背包的贪心选择性质成立因为任何最优解都可以通过交换论证调整成包含贪心选择的形式而不损失最优性。贪心算法的正确性证明通常有两种方法交换论证和数学归纳。交换论证的思路是假设存在一个最优解它没有包含贪心选择那么我们可以构造另一个解把贪心的那个选择替换进去结果不会变差。哈夫曼编码、活动安排、最小生成树的 Kruskal 和 Prim 都是用这套思路证明的。考试里如果让你证明某贪心策略是错误的标准做法是构造一个反例。比如证明按重量从小到大选的背包贪心策略错误只需要举出物品重量 1、价值 100物品重量 2、价值 101背包容量 2 的例子贪心会选择重量 1 的物品总价值 100但最优解是选重量 2 的物品总价值 101。反例要尽可能简单一两句话能说清最好。3.4 回溯与分支限界剪枝函数怎么设计回溯法的本质是带剪枝的深度优先搜索。它的代码框架非常固定我习惯把它拆成路径选择 约束检查 目标判断三块def backtrack(path, choices): if is_solution(path): record(path) return for choice in choices: if is_valid(path, choice): path.append(choice) backtrack(path, next_choices(choice)) path.pop()n 后问题是回溯的经典应用考试里常见的形式是让你画出解空间树的前几层或者写出剪枝条件。剪枝条件的写法是当前位置 $(i, j)$ 能否放皇后取决于同一列、同一主对角线、同一副对角线上是否已有皇后。对角线的判断可以用 $i-j$ 是否相等主对角线和 $ij$ 是否相等副对角线来快速判断。分支限界和回溯的区别在于搜索顺序和剪枝方式。回溯是深度优先分支限界通常用广度优先或优先队列最小耗费优先。分支限界需要设计一个限界函数用来估算当前节点可能达到的最优解如果这个估值还不如当前已找到的最优解就可以把这个节点剪掉。0-1 背包的分支限界法中限界函数通常用当前价值 剩余物品按单位价值贪心填满背包的价值来上界估计。注意分支限界考的通常是画出搜索树的展开过程和写出限界函数不太要求完整代码。但很多同学把两件事弄混——回溯的剪枝函数判断的是当前选择是否合法分支限界的限界函数判断的是当前分支是否还有希望超过已有最优解。这两个概念完全不一样考试前一定要分清楚。3.5 图算法最小生成树与最短路径的选型图算法部分的考点集中在四个算法的对比和手工执行上Prim、Kruskal、Dijkstra、Floyd。算法解决的问题适用条件时间复杂度数据结构Prim最小生成树无向连通图$O(n^2)$ 或 $O(m\log n)$邻接矩阵/堆Kruskal最小生成树无向连通图$O(m\log m)$并查集Dijkstra单源最短路径非负权$O(n^2)$ 或 $O(m\log n)$邻接矩阵/堆Floyd全源最短路径可有负权无负环$O(n^3)$邻接矩阵这几个算法的手工执行过程几乎必考尤其是 Dijkstra 的逐步松弛和 Floyd 的三重循环填表。我的经验是把 Dijkstra 的过程写成一张表每轮选一个未访问的距离最小的顶点然后松弛它的所有邻居。表格分三栏——已确定的顶点集、各顶点的当前最短距离、各顶点的前驱。填表时手要稳每一轮都要对照上一轮的结果避免漏掉松弛。Floyd 的填表更考验耐心它的核心是那个三重循环for k in range(n): for i in range(n): for j in range(n): if dist[i][j] dist[i][k] dist[k][j]: dist[i][j] dist[i][k] dist[k][j]注意 $k$ 必须在最外层这是很多同学的易错点。考试里如果只要求填表那么第 $k$ 轮填表时允许经过的中间顶点集合是 ${0, 1, \dots, k}$这个理解对填表非常关键。4. 实操演练手算题与编程题的定向突破4.1 手算题的三类填表套路手算题是拉分的关键因为它的评分标准很明确对的给分、错的扣分没有模糊空间。我把高频的手算题型归纳成三类第一类是矩阵链乘。给定一串矩阵的维度 $p_0, p_1, \dots, p_n$要求填出 $m[i][j]$ 表最少乘法次数和 $s[i][j]$ 表最优分割点。填表顺序是按链长从小到大先填长度 2 的对角线再填长度 3、4直到填满右上三角。每个 $m[i][j]$ 的计算公式是 $m[i][j] \min_{i \leq k j}{m[i][k] m[k1][j] p_{i-1}p_k p_j}$。填的时候务必把每一层的候选值都列出来不要心算跳步。第二类是 LCS 表。给定两个字符串要求填出 DP 表并回溯出最长公共子序列。填表规则是字符相等时 $dp[i][j] dp[i-1][j-1] 1$否则 $dp[i][j] \max(dp[i-1][j], dp[i][j-1])$。回溯时从右下角开始如果该格的值来自左上角加一就记录字符并往左上走否则往值更大的方向走。第三类是哈夫曼树构造。给定一组权值要求构造哈夫曼树并计算带权路径长度 WPL。操作要点是每次选两个最小的权值合并把合并结果放回集合。构造出来的树不唯一因为左右子树可以交换但 WPL 是唯一的。WPL 的计算方式是所有叶子节点的权值乘以它到根节点的路径长度之和或者等价地所有合并过程产生的中间权值之和。4.2 编程题的代码模板与常见坑期末编程题通常有两种形式一种是给出问题描述要求写出完整算法另一种是给出代码框架要求补全关键部分。前者的准备方式是背模板——快排、归并、二分、DP 的几种常见模型、图的存储和遍历这几个模板必须烂熟。以二分查找为例最容易被扣分的地方是循环边界和中间值取法。我习惯用这个版本def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1这里mid left (right - left) // 2是为了防止left right溢出虽然 Python 里不会溢出但考试里阅卷老师看到这个写法会加印象分而且如果你写 C 或 Java 就真的需要。循环条件left right表示闭区间退出时left right说明没找到。动态规划的编程题里最常考的坑是初始化和边界条件。比如 LCS 的 $dp[0][j]$ 和 $dp[i][0]$ 都要初始化为 0这个看起来简单但漏了就直接全错。再比如完全背包和 0-1 背包的区别在于内层循环的方向0-1 背包的容量维度要倒序遍历完全背包要正序遍历。这个规律我是这么记的倒序保证每件物品只用一次正序允许重复使用。4.3 真题演练的节奏安排复习到最后阶段最好的方法是限时做真题。我会把每套卷子按考试时长打个八折来练比如考试 120 分钟我就给自己 100 分钟。这样做的好处是提前适应时间压力考场上不会因为最后二十分钟还有两道大题没写完而慌乱。做完真题后的复盘比做题本身更重要。我复盘时重点关注三件事一是错题的错因归类是概念不清、计算失误还是思路根本不对二是每题的实际用时看看哪类题拖了后腿三是有没有可以简化的步骤比如某些推导过程考场上可以省去把时间留给后面的题。5. 常见问题与排查技巧实录5.1 复习过程中的典型卡点速查下面这张表是我和同学在复习过程中反复遇到的卡点按出现频率排序你可以对照自查卡点现象根本原因解决方式主定理套错情况只会记结论不会比较 $n^{\log_b a}$ 和 $f(n)$每次先算 $n^{\log_b a}$写在草稿纸最上面DP 状态定义不出来没有做够题型缺少状态命名的语感先做 20 道经典 DP 题总结状态定义模式贪心正确性证不出来不清楚交换论证的结构背熟活动安排问题的证明模板手算填表慢边算边想没有形成流程每种题型定死填表顺序先机械填再检查编程题写不完整平时只看不写纸上写代码手生每周至少手写 3 段完整代码不用 IDE这里面我感受最深的是最后一条。我有个同学平时看代码觉得都懂结果考试时手写快排写了两遍都没写对问题出在递归边界上。后来他逼着自己每天在纸上手写一段代码两周后明显顺畅了。手写代码和在 IDE 里敲完全是两回事因为 IDE 会帮你高亮、补全而考场只有一张白纸。5.2 考场上的时间分配与应急技巧我个人的时间分配建议是这样选择题和填空题控制在 20 分钟内复杂度分析和证明题 25 分钟手算题 30 分钟算法设计题 25 分钟编程题 30 分钟留 10 分钟检查。当然这个比例要根据实际卷面调整但核心原则是不要在低分值的题上纠缠太久。应急技巧方面有几个是我亲测有效的第一算法设计题如果一时想不出最优解先写暴力解法再优化通常能拿到一半的步骤分第二复杂度分析题如果主定理用不了立刻转递归树法不要在一道题上死磕第三编程题如果写不完把伪代码和关键步骤的注释写上阅卷时按点给分写得清楚比写得完整更划算。还有一个小细节手算题的表格一定要用尺子画或者画整齐因为阅卷老师要在你的表上找对应格子表画乱了很容易被误判。我习惯用铅笔先画表头填完再擦掉辅助线看起来干净利落。最后提一个我踩过的坑有一年考试要求用分支限界法求解装载问题我背的是回溯法的模板结果整个思路都不对那道题几乎没得分。后来我才明白回溯法的搜索是深度优先、找到解就记录而分支限界的搜索是优先队列、不断更新当前最优解。这两种策略在代码结构上差别很大复习时一定要分开练。