“算法设计与分析”这门课说实话是很多计算机专业学生的分水岭。大一学程序设计大家写的是“功能”到大二大三学这门课才开始真正琢磨“效率”和“代价”。尤其在西电这种比较重视理论基础和算法功底的工科院校期末试卷从来不是靠背代码能混过去的。复习这门课最怕的就是把时间浪费在背具体代码上结果考场上遇到了设计题脑子一片空白。这篇笔记是我结合课程大纲和历年期末题型梳理的一份复习框架覆盖复杂度分析、分治、动态规划、贪心、回溯与分支限界这几大核心板块专门针对“怎么复习、怎么答题、怎么避坑”来写。适合正在冲刺期末的同学也适合想系统过一遍这门课核心体系的低年级学弟学妹。1. 先把课程主线捋清楚期末考的不是代码是思路1.1 四个核心板块的真实权重很多同学复习这门课时习惯性地按教材目录从头翻到尾翻到第一章复杂度分析觉得“哦大O啊我会”然后一路看到第八章好像什么都眼熟又什么都说不透。这是大忌。西电这门课的期末卷面结构我一直觉得很典型基本上是“选择填空考概念、大题考套路、压轴考设计”核心就落在四个板块上复杂度分析与递归方程求解分治策略动态规划贪心算法与回溯/分支限界这四个板块占了整张卷子的80%以上。剩下那些关于排序网络、串匹配之类的细节一般只在选择题或判断题里露个脸。所以复习顺序应该按“递归方程 → 分治 → 动态规划 → 贪心 → 回溯/分支限界”这条线推每一环的知识都能扣到下一环上。比如分治算法的复杂度分析直接用到递归方程求解动态规划里又要反复对比贪心算法的适用场景。1.2 真题很宝贵但更要学会“看出题人怎么想”期末复习最容易踩的坑是到处找原题背答案。坦率地说每年期末考试的大题类型确实高度相似但老师会换参数、换约束、换问法。比如去年考了“矩阵链乘的最小乘法次数”今年很可能改成“最优二叉搜索树的期望搜索代价”去年考了“用回溯法解N皇后”今年可能换成“图着色”或“批处理作业调度”。换汤不换药的背后考的是你有没有真懂“状态空间树怎么画”“剪枝函数怎么设计”这套方法论。我的建议是做过去的真题不要止步于“这道题的答案是什么”而是每做一道就问自己三个问题——这道题在考哪个算法的哪个核心特性如果换一组输入数据我的做题步骤是否还成立如果老师把题目从“求最优解”改成“求方案数”我还能不能hold住想清楚这三件事比刷十套卷子都管用。2. 复杂度分析递归方程的套路化求解2.1 渐进记号选择题的判定技巧复杂度这块期末第一类送分题通常就是给一段代码或递推关系判断时间复杂度。大O、大Ω、大Θ的定义肯定要背但我发现很多同学容易在“平均复杂度”和“最坏复杂度”上犯迷糊。比如快速排序平均情况是Θ(n log n)最坏情况是Θ(n²)这俩不矛盾因为渐进记号描述的是“趋势上界/下界/精确阶”不是“每次都发生一次”。复习时建议把常见的复杂度按量级排一个序O(1) O(log n) O(√n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)。这个顺序一定要刻在脑子里。选择题里经常出现“以下哪个函数的增长阶最高”这类题直接对照这个序列秒选。2.2 递归方程的三种求解方法递归方程求解是期末计算题的常客也是后面所有分治算法分析的基础。这里有三板斧必须全部掌握。代入法代换法一般用于证明或验证一个猜测的复杂度。套路是先根据递归形式猜一个上界然后用数学归纳法证明。考试时如果直接让你“用代入法证明T(n) T(n/2) 1 的解是O(log n)”那你得把归纳假设写得明明白白通常假设T(k) ≤ c·log k 对 k n 成立再代入递推T(n) T(n/2) 1 ≤ c·log(n/2) 1 c·log n - c 1只要 c ≥ 1就能推出 T(n) ≤ c·log n。注意归纳假设必须是“对更小规模成立”这个前提不能漏。递归树法适合用来“猜”复杂度特别是那种结构不太规整的递推比如 T(n) 2T(n/2) n。我习惯把每一层的代价写出来第一层是 n第二层是两个 n/2 加起来还是 n第三层是四个 n/4 加起来还是 n直到叶子层的代价变成 n·Θ(1)。树的层数是 log₂n所以总代价是 n·log₂n。递归树法的好处是直观坏处是写卷子时比较费时间。如果题目明确要求用递归树记得画一个层级图然后把“层数”和“每层代价”两个表头列出来最后用等比数列求和。主定理Master Theorem这是性价比最高的方法一道两分钟能搞定的题千万别拖。主定理针对 T(n) aT(n/b) f(n) 这种形式核心是比较 f(n) 和 n^(log_b a) 的阶。很多同学背了三条规则却不知道怎么用我教一个比较土但很稳的口诀先算 c_crit log_b a然后看 f(n)若 f(n) O(n^(c_crit - ε))即 n 的 log_b a 次方“压着打”结果是 Θ(n^(c_crit))若 f(n) Θ(n^(c_crit) log^k n)结果是 Θ(n^(c_crit) log^(k1) n)若 f(n) Ω(n^(c_crit ε)) 且满足 a·f(n/b) ≤ c·f(n)正则条件结果是 Θ(f(n))。考试时最常考的就是第二条比如 T(n) 2T(n/2) n这里 c_crit log₂2 1f(n) n Θ(n^1 log⁰ n)所以结果是 Θ(n log n)。2.3 主定理的边界情况这个坑每年都有人踩主定理看起来简单但有三个极容易翻车的地方第一f(n) 与 n^(log_b a) 同阶但差一个对数因子时直接用第二条。比如 T(n) 2T(n/2) n log n结果是 Θ(n log² n)不是 Θ(n log n)。注意这里 f(n) 的 k 是 1所以答案里多出一个 log n。第二第三条的正则条件经常被忽略。虽然考试一般不要求你验证正则条件但当 f(n) 是多项式级别大于 n^(log_b a) 时答案才是 Θ(f(n))。如果 f(n) 只是大了一点点比如 n^(1.0001) 对 n^1要小心 epsilon 是否真的存在。第三主定理不适用于 T(n) T(n-1) n 这种“减1”型递推也不适用于 T(n) 2T(n/2) n! 这种 f(n) 增长过快的。前者要用累加法T(n) T(n-1) n T(n-2) (n-1) n ... Θ(n²)。这种题型虽然简单但至少值一道计算题的分别丢。3. 分治策略边界条件和合并过程决定成败3.1 分治的固定三段式并不难难的是递归出口分治的思想可以用一句话概括把大问题拆成若干规模相同的小问题递归求解小问题再把小问题的解合并成大问题的解。期末卷面上分治的简答题一般会要求你“写算法思路 分析复杂度”而不是“默写完整代码”。所以复习分治重点不是背代码而是搞清楚三个东西分解步骤、递归出口、合并策略。以归并排序为例分解就是“从中间一刀切”递归出口是“区间只有一个元素或空”合并是“双指针线性合并”。这三个环节缺一个整个算法就站不住。尤其是递归出口很多同学写归并排序时忘了处理空区间结果 n 为偶数时没问题n 为奇数时就数组越界。这种细节在纸面上写算法的时候不明显但恰恰是判卷老师看你会不会“边界思考”的点。3.2 经典分治问题最大子数组与最近点对最大子数组问题是分治板块常考的题目。思路是把数组从中间分成左右两半最大子数组要么全在左半要么全在右半要么跨过中点。前两种情况递归求解第三种情况从中点向左向右分别扩展找最大连续和再相加。考试时如果出这道题分析复杂度的要点是跨中点的求解过程是 O(n)因此递推式是 T(n) 2T(n/2) O(n)主定理直接给出 Θ(n log n)。这其实就是把“线性扫描”和“分治递归”结合在了一起跟最大子数组的暴力 O(n²) 方案形成了鲜明的对比这种对比常常是简答题的得分点。最近点对问题则是分治板块的进阶题。在平面上找距离最近的两个点暴力法是 O(n²)分治法能做到 O(n log n)。核心步骤是按 x 坐标排序从中线分成左右两半递归找左右两半的最小距离 d min(d_left, d_right)最后检查中线两侧 d 范围内的候选点这个“合并步骤”是关键也是难点。复习时我建议认真推导一下“为什么只需要检查中线附近 d 距离内的点”以及“为什么每个点最多只需要和常数个点比较距离”。这其实是主定理第二条的应用——合并步骤 O(n)所以总体 O(n log n)。如果时间充裕把这个问题吃透对理解分治的“合并代价”非常有帮助。3.3 分治设计与递归方程的对照关系这里有一个期末复习的小技巧分治算法的复杂度分析其实可以统一成一个模板。假设每次把规模 n 的问题拆成 a 个子问题每个子问题规模 n/b分解和合并的总代价是 f(n)那么递推式就是 T(n) aT(n/b) f(n)。你做分治题的时候不管具体题目是什么先问自己拆成了几个子问题定 a每个子问题的规模减到了多少定 b分解合并的额外代价是多少定 f(n)把这三项指标填进递推式再套主定理复杂度分析基本不丢分。二分查找是 T(n) T(n/2) O(1)归并排序是 T(n) 2T(n/2) O(n)最近点对是 T(n) 2T(n/2) O(n)这三道题的递推式看似相似但 f(n) 不同结果也不同。考场上如果被问到“为什么二分查找是 O(log n) 而最近点对是 O(n log n)”答案就在 f(n) 上。4. 动态规划状态定义决定生死4.1 一个背下来就能解决90%问题的设计流程动态规划是这门课最核心、也是期末分值最重的部分之一。经常有同学问我“动态规划怎么学感觉题目一变就不会了。”我的回答是你先别管题目怎么变先把做题的流程固定下来。动态规划题的四步流程是定义状态。明确 dp[i] 或 dp[i][j] 表示什么。写状态转移方程。想清楚 dp[i][j] 怎么由更小的状态推过来。确定初始化和边界条件。确定遍历顺序和答案位置。这四步中第一步是最关键也是最难学的。状态定义得好转移方程几乎是顺水推舟状态定义得糊后面全崩。以0/1背包为例dp[i][j] 表示“前 i 个物品背包容量为 j 时的最大价值”在此基础上才有经典的转移dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])如果你把状态定义成“容量 j 时能装的最大价值”不记录物品编号那你就没法处理“每个物品只能用一次”这个约束很容易写成无限背包。这种细节就是考试里“设计题”和“编程题”拉开差距的地方。4.2 从背包、LCS到矩阵链乘用一张表打通期末动态规划的大题翻来覆去就是那么几道经典题但每次换一层皮。我把最常考的几类问题放在一起对照你会发现它们的结构高度一致问题类型状态定义转移方程复杂度0/1背包dp[i][j] 前i个物品容量j的最大价值dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]]v[i])O(n·C)最长公共子序列(LCS)dp[i][j] 前缀A[1..i]与B[1..j]的LCS长度若A[i]B[j]则dp[i][j]dp[i-1][j-1]1否则max(dp[i-1][j], dp[i][j-1])O(m·n)矩阵链乘dp[i][j] 矩阵i到j的最小乘法次数dp[i][j] min(dp[i][k] dp[k1][j] p[i-1]·p[k]·p[j])O(n³)最长递增子序列(LIS)dp[i] 以第i个元素结尾的LIS长度dp[i] max(dp[j] 1) 其中j i且a[j] a[i]O(n²)石子合并dp[i][j] 合并i到j堆石子的最小代价dp[i][j] min(dp[i][k] dp[k1][j]) sum(i,j)O(n³)看到共同点没有动态规划问题的本质都是“大问题的解 子问题的解 当前步骤的代价”。区别只在于“当前步骤的代价”这个函数怎么定义。背包是加物品的价值LCS是加匹配字符的贡献矩阵链乘是加矩阵乘法的次数。你把状态和转移方程对照着背一次记住一整套。4.3 动态规划与贪心算法的分界线动态规划章节最容易和贪心算法搞混期末也特别喜欢出那种“先判断该用贪心还是动态规划”的选择题。我的判断标准只有一个当前的选择会不会影响后续的选择如果会那就必须用动态规划。比如0/1背包你选了物品A背包剩余容量变了后续能选的物品组合就变了所以贪心不行。如果不会那就可以考虑贪心。比如分数背包单位价值最高的物品可以放心先装因为即使装了剩余容量还能继续装其他物品后续选择不受影响。记住这个标准考试时你就能快速判断活动选择问题按结束时间排序用贪心是对的因为“先选最早结束的活动”留给后面更多时间不破坏后续选择但带权活动选择问题按结束时间贪心就不行因为选一个权重低的早活动可能排挤掉一个权重高的晚活动必须用动态规划。4.4 期末设计题的踩坑点别忽略“最优子结构”的说明很多同学做动态规划设计题时直接甩一个状态定义和转移方程就完事。这在期末答题上是要扣分的。老师想看到的完整回答至少包括三部分问题的最优子结构性质、状态定义、转移方程。最优子结构的说明尤其重要——也就是“如果全局是最优的那么去掉最后一个物品/最后一次划分后剩余部分也一定是对应子问题的最优解”。这句话虽然听起来有点像套话但是它就值几分而且它体现了你真的理解动态规划为什么成立而不是只背了一个方程。5. 贪心算法拿分容易证明难5.1 贪心算法的使用条件与排序/剪枝策略贪心算法的复习可以拆成两块一是会“用”二是会“证”。会用指的是能写出贪心策略和算法过程这个对大部分同学不难。比如活动选择问题按结束时间从小到大排序然后依次选择“开始时间不早于上一个选中活动结束时间”的活动。这个策略想明白后写出来很简单期末简答题能拿分。难点在于“证明”。课程里讲贪心正确性有两种常用工具贪心选择性质和最优子结构性质。其中贪心选择性质的证明最常用的技法叫交换论证exchange argument。比如证明活动选择问题中“最早结束的贪心选择一定属于某个最优解”假设某个最优解中第一个活动不是最早结束的活动那么把最优解中的第一个活动换成最早结束的活动因为它的结束时间不晚于原活动所以剩下的活动仍然可以保留得到的新解不会更差。这就证明了贪心选择不会偏离最优解。期末如果考证明题我建议把这个交换论证的写法背熟练它能对付大部分贪心证明。步骤就三步假设一个最优解不含贪心选择把贪心选择“换”进最优解证明替换后解仍然是最优的。只要你把这三步写清楚基本就是满分。5.2 经典贪心题目Huffman编码与最小生成树Huffman编码是贪心板块的高频题目。算法思路很朴素每次从频率最小的两个节点合并成一个新节点新节点的权重等于两者之和重复这个过程直到只剩一个节点就得到了Huffman树。期末考Huffman题多半会让你画Huffman树并且写出各个字符的编码。这里有一个很实用的检查方法所有编码长度构成的带权路径长度WPL应该等于内部节点权重之和你可以快速验算自己有没有画错。另外要注意Huffman编码是不等长编码要求任何字符的编码不能是另一个字符编码的前缀这就是前缀码性质这也是为什么Huffman编码可以无歧义解码。最小生成树这边Prim算法和Kruskal算法几乎是必考二选一。期末常考的方式是给一张图让你手算最小生成树并写出边权之和。这类题只要细心基本不丢分。关键是在复习时把两种算法各自的贪心策略说准确Prim是从一个顶点出发每次加入连接“已在树内”和“树外”的最小权边Kruskal则是把所有边按权排序从小到大选边只要不形成回路就加入。很多同学会忽略Kruskal中“判断是否形成回路”的实现细节。我在期末编程题里就栽过一次用并查集判断回路时find操作没写路径压缩导致超时。这其实是数据结构课的知识但在算法课编程题里会直接卡你性能复习时一定要把并查集的路径压缩版本重新过一遍。5.3 一个反直觉的贪心反例换硬币问题复习贪心算法时我强烈建议看一遍换硬币找零钱问题的陷阱。如果硬币面值是1、5、11要凑15元贪心算法是111111 15用5枚硬币。但最优解是555 15只要3枚。这说明贪心策略在一般面额下不能保证最优只有当硬币面额满足某种规律比如人民币1、2、5、10的规律时贪心才是对的。期末卷子上如果出一道“判断该问题能否用贪心算法求解”的题这个例子就是你反驳的最大武器。如果能出一道设计题让你用动态规划求最少硬币数那么状态定义为 dp[i] “凑出 i 元需要的最少硬币数”转移是遍历所有面额取最小值这类题本质上就是完全背包问题别忘了遍历顺序是正序。6. 回溯与分支限界搜索树的剪枝艺术6.1 解空间树子集树与排列树的区别回溯法和分支限界法的共同点在于都使用搜索树来穷举所有候选解核心区别在于搜索策略回溯法用深度优先搜索分支限界法用广度优先搜索或优先队列搜索。期末复习的第一件事是搞清楚两类解空间树子集树从n个元素中选一个子集树的每一层对应“选/不选”一个元素叶子节点数为 2ⁿ。0/1背包问题就是典型的子集树。排列树求n个元素的一个排列树的每一层对应“下一个位置放哪个元素”叶子节点数为 n!。旅行商问题、N皇后问题都是排列树的典型例子。这个区分为什么重要因为题目最后总会问“该算法的解空间树有几个叶子节点”或“搜索复杂度是多少”你只需要回答 2ⁿ 或 n!这一分就是白送。但要记住剪枝可以大幅度减少实际搜索的节点数所以“理论上界是2ⁿ/n!”和“实际搜索量远小于这个值”这两句话要表达清楚。6.2 剪枝函数的设计限界函数与约束函数回溯法的“剪枝函数”由两部分组成约束函数和限界函数。约束函数在子集树里最常见。以0/1背包回溯法为例进入左子树选第i个物品前要检查当前重量 该物品重量是否超过背包容量超过则剪掉左子树。N皇后问题则是检查位置是否与已有皇后冲突冲突就不进入该分支。限界函数在求最优解问题时特别关键。还是0/1背包回溯法进入右子树不选第i个物品前通常用一个上界函数来估计“即使我接下来全选剩余物品或按单位价值贪心装剩余物品能获得的最大价值 bound”。如果 bound ≤ 当前最优价值 best那就不用进入右子树了因为即使装满了也不可能优于当前解。期末如果在编程题或设计题里考0/1背包回溯法这个上界函数的设计几乎必考。上界别定得太松比如“剩余物品价值之和”剪枝效果会很差也别定得太紧导致计算上界本身就花很多时间。一个常用的折中是按剩余物品单位价值降序用分数背包的贪心价值作为上界。这个上界肯定是真实最优值的一个上界而且计算是O(n)的。6.3 回溯与分支限界的本质差异一个DFS一个BFS很多同学把回溯和分支限界混在一起期末判断题一做就错。这里我把它拆成一句话回溯法要找的是“一个”或“所有”可行解用深度优先遍历碰到不满足条件的子树立刻剪掉分支限界法要求的是“最优解”用广度优先或优先队列遍历每扩展一个活结点就计算限界值优先扩展限界值更优的节点。分支限界法的优先队列实现里每个节点一般要记录当前部分解、当前价值、当前重量、还能继续扩展的位置。零一背包分支限界的经典写法是每个节点有两个子节点选/不选下一个物品选之前检查重量约束不选之前检查限界函数然后从优先队列里取出“上界最大”的节点继续扩展。循环直到队列为空或取出的节点上界不大于当前最优解。期末如果要求和分支限界法画搜索树我有个复习技巧用“节点编号 当前层数 当前背包价值 当前背包重量 限界值”这种格式去标注每个节点这样老师能一眼看清你的搜索过程不容易扣分。别只画一个光秃秃的树打分全靠解释文字。7. 期末计算与编程题的实战应对7.1 手算题从排序过程到动态规划表期末卷上最怕的不是不会做而是“会做但写得混乱”。我见过太多同学思路完全是正确的但因为过程写得像天书被扣掉大把分。这里分享我整理出来的几种手算题的标准书写格式。动态规划表题比如LCS或背包一定要画表格。行和列分别是两个序列或物品编号和容量表里填状态值旁边用箭头或颜色标出“当前状态是由哪个方向转移过来的”。这样即使最终答案填错了一格老师也能看到你的递推逻辑至少能拿一半分。分治算法手算题如快速排序、归并排序我的建议是每一轮单独一行写上“划分点xx”并用中括号把当前处理区间标出来。千万不要几十个数挤在一坨连你自己都分不清哪一轮到哪一轮。排序题是按步骤给分的过程写清楚才是王道。Huffman编码题树的每个内部节点和叶子节点都建议标注权重。写编码时按“从根到叶子的路径左0右1”的约定标注。最后一定要写一行 WPL 各叶子权重乘以路径长度之和这个数值是你画图的验算依据。7.2 算法设计题的得分点写法期末设计题给分一般看四点算法思想一句话、伪代码/自然语言步骤、复杂度分析、正确性说明。这四点不能缺。算法思想一句话是很多人会漏的。比如“用贪心法每次从剩余活动中选结束时间最早的”、“用动态规划状态dp[i][j]表示...”这一句话就证明了你知道这题在考什么策略。伪代码方面如果实在不会写严密的伪代码也别空着。用自然语言分步骤写清楚“第一步做什么、第二步做什么”同样能拿大部分分数。比如“先把所有区间按右端点升序排序然后用一个变量记录最后选中的区间的右端点遍历所有区间如果区间的左端点大于等于该变量就选中该区间并更新变量”这种描述虽然没有一行代码但算法思想清清楚楚得分完全没问题。复杂度分析一定不要只写结果要写“因为排序是O(n log n)后面的扫描是O(n)所以总复杂度是O(n log n)”。这是给分点缺一不可。正确性说明是最难的但不强求写严格的数学证明。能做到“说明贪心选择性质”或“说明子问题被正确覆盖了”就已经能拿到这部分的分数。7.3 期末编程题的模板化准备关于“算法设计与分析期末编程题”我遇到很多同学问要不要把每道经典题的代码都背下来我的回答是不要背代码要背模板。算法课的编程题和数据结构课的编程题不太一样它更侧重看你能否把某个算法策略快速实现而不是考你某个api怎么调用。所以我建议按算法类型准备以下代码模板归并排序的merge函数分治双指针0/1背包的一维滚动数组写法注意容量倒序遍历完全背包的一维写法容量正序遍历LCS的dp表回推路径可选并查集的find和unionKruskal用路径压缩按秩合并快速排序的partitionLomuto或Hoare选一个熟记二分查找的闭区间写法left ≤ right回溯法的通用递归框架path记录当前路径visited标记递归出口回溯撤销把上面这几个模板练熟期末编程题大概率能覆盖80%。我建议你在考试前一周每天默写一遍这些模板不用运行就手写。写到第3、4次的时候你会发现大脑里已经形成肌肉记忆了考场上即使紧张也能从容写出来。7.4 写编程题时的动词排查清单最后一道编程题通常时间紧很多同学是“能跑就交”。但根据我踩过的坑我整理了一个提交前快速检查的清单数组下标是否从0开始还是从1开始dp题目乱用会直接数组越界。背包循环遍历方向对不对0/1背包容量必须倒序完全背包正序错一个就是“无限用物品”和“只能用一次”的区别。递归出口是否覆盖了空集回溯法里“剪枝在递归前还是递归后”容易混乱。排序是否稳定有没有影响一般算法题不要求稳定但涉及到输出顺序就要留意。数据范围用int够不够动态规划求总价值/总代价时很容易爆int建议直接开long long或long。这五条每一条都是我或者身边同学真实摔过的坑。考场上花30秒扫一遍等于给自己多上了一道保险。8. 最后冲刺从“看懂”到“写对”的转化8.1 把书读薄的输出式复习法很多同学复习到后期感觉“书都看懂了但合上书什么都写不出来”。这是正常的因为看懂是输入写对是输出两者之间差着一道“练习”的鸿沟。我的办法是每天晚上合上书本拿一张白纸把我当天复习过的每类算法用一句话加一个小例子默写出来。比如动态规划我就默写“0/1背包dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])容量遍历倒序”然后写一个只有3个物品的小例子手算一遍dp表。别看这动作简单它就是“输出式复习”。你只有在纸上亲手算过一遍考试时才有可能30秒进入状态。8.2 考前一周的时间分配参考我认为考前一两天拼命刷难题是最不明智的。下面是更合理的时间安排也是我带过学弟学妹们实操过多次的节奏倒数第7天到倒数第5天分治和动态规划的核心题再过一遍重点看状态定义和转移方程而不是反复做难题。每天手写3道dp题不求新求熟。倒数第4天到倒数第3天贪心和回溯/分支限界重点看剪枝函数的写法和证明题套路。每天手画一棵搜索树或手推一个Huffman编码。倒数第2天全面默写代码模板上面的8个模板以及复习复杂度分析方法。倒数第1天不再大规模做题。只把每章你最容易错的点列成一张A4纸比如“主定理第三条要验正则条件”“Kruskal要用并查集”“回溯求最优解要加上界函数”等考前1小时翻一遍这一页。8.3 考场上最容易失分的三个小习惯写算法设计题的步骤时不少同学喜欢“跳步”。实际上期末判分是按点给分的你跳过的每一步恰恰就是分数所在。我在期末卷里见过最可惜的情况算法的思想完全正确但是忘了写“对所有元素按关键字排序”这一步白白丢掉2分。所以凡是涉及排序或预处理的操作都在算法步骤里写出来不要觉得这是显而易见的事。第二个是时间复杂度分析忘了写“额外空间复杂度”。有些简答题会问复杂度你得主动回答案空间复杂度比如归并排序的额外空间是O(n)快速排序递归栈深度平均是O(log n)。这种1分的小点丢了可惜。第三个是没看清题目让不让用某个算法。有时候题干会说“请用贪心算法设计”或者“请设计一个O(n log n)的算法”这其实是出题人给你的提示也是约束。不要看到“求最优解”就默认写动态规划先回头看一眼题目要求。8.4 考后复盘的价值不止于分数最后多说一句。这门课复习过程中遇到的那些“看了答案恍然大悟再做一遍还是错”的题目我建议你专门整理成一个错题本不要散落在草稿纸上。错题本的价值不在当下而在于它是你算法思维薄弱的真实镜像——它告诉你你是状态定义不熟还是交换论证不熟还是边界条件容易漏。把这个复习笔记的过程完整走下来哪怕考试已经结束你带走的也是一套真正属于自己的算法分析能力而不只是期末卷上的一个分数。