1. 复杂度分析递归式才是期末卷上的第一道门槛我先说个反直觉的结论算法设计与分析这门课挂科的人绝大多数不是栽在动态规划或者图算法上而是栽在最前面那几道看着最人畜无害的复杂度题上。原因很简单后面的大题你写不出最优解好歹能拿过程分可复杂度分析是一道对就是对、错就是错的硬题主定理套错一个条件扣的就是整道题的分。所以复习算法设计与分析期末题的时候我建议你先把复杂度这根钉子钉死再去看别的。渐进记号这块很多人背得住定义却用不出来。大O描述的是上界也就是最坏不会超过这个量级大Ω描述下界大Θ是紧确界上下界同阶。考试里最常见的陷阱是让你判断某个关系成不成立比如 n O(n²) 成立但 n² O(n) 不成立再比如 2^(n1) O(2^n) 成立因为常数因子在渐进意义下被吞掉了。记住一条经验渐进分析里所有常数系数和低阶项都可以丢但指数上的 n 不能丢它决定了算法能不能跑得动。递归式求解是这块的绝对重点而主定理能覆盖大概七成的考题。主定理处理的是形如 T(n) aT(n/b) f(n) 的递归式核心是拿 f(n) 和 n^(log_b a) 去比大小。理解它的逻辑其实不难aT(n/b) 这一项是把问题切成 a 个子问题、每个规模是原来的 1/bn^(log_b a) 就是子问题数量的增长速度f(n) 是划分和合并这些子问题的额外开销。谁嗓门大谁说了算这就是主定理的直觉。具体分三种情况我给你一张表对照着记比死背文字靠谱得多。情况判断条件结果典型例子情况一f(n) 比 n^(log_b a) 小多项式量级T(n) Θ(n^(log_b a))T(n)8T(n/2)n²得 Θ(n³)情况二f(n) 与 n^(log_b a) 同阶T(n) Θ(n^(log_b a) · log n)归并排序 T(n)2T(n/2)n得 Θ(n log n)情况三f(n) 比 n^(log_b a) 大多项式量级且满足正则条件T(n) Θ(f(n))T(n)2T(n/2)n²得 Θ(n²)这里有个细节必须提醒情况一和情况三要求的是多项式量级的差距也就是说差的是 n 的某个正数次幂而不是差一个 log 因子。像 T(n) 2T(n/2) n log n 这种f(n) 虽然比 n 大了但只大了一个 log不满足多项式差距主定理三种情况全都套不上这时候必须改用递归树或者直接猜答案再代入验证。这是我在期末卷上见过最多的一个坑出题老师就爱拿这种主定理失效的题来筛人。递归树法适合主定理搞不定的场景。画法是把每一层的总代价写出来然后把所有层加起来。比如 T(n) 2T(n/2) n log n第一层是 n log n第二层是两个 (n/2)log(n/2) 加起来约等于 n(log n - 1)第三层再减一点层数一共 log n 层累加起来就是 Θ(n log²n)。你把这棵树画出来答案基本就自己浮出来了比硬猜靠谱。提示考试时间紧的时候先判断递归式能不能套主定理能套就直接套不要画树浪费时间套不上的再动笔。这个判断习惯能帮你省下至少十分钟。代入验证法有些教材叫替换法是最后的兜底手段。步骤是先根据经验猜一个解比如猜 T(n) O(n log n)然后假设 T(k) ≤ ck log k 对所有 k n 成立把这个假设代进递归式验证 T(n) ≤ cn log n 能不能推出来。推不出来就把猜测调高一个量级再试。这个方法看着笨但万能尤其在主定理失效的题里是唯一稳的路子。2. 分治法看到两半合并就要条件反射分治法的识别信号特别明显题干里只要出现把序列从中间分开递归处理左半和右半最后合并结果这类描述基本就是分治。复习的时候别满足于会写归并排序你得能识别出哪些问题天然适合分治——一句话总结子问题相互独立、可以并行解决、合并操作比原问题便宜这三条同时满足分治才有意义。归并排序是分治的模板答案但期末卷上很少有人直接考归并排序的代码更常见的是考它的复杂度推导和稳定性。归并排序的递归式 T(n) 2T(n/2) Θ(n)套主定理情况二得到 Θ(n log n)而且它在最坏情况下也是这个复杂度这是它比快排硬气的地方。合并两个有序数组的操作是线性的每个元素最多被比较和移动一次这就是 Θ(n) 那项的来源。二分查找是分治的另一个典型但它更特殊——它每次只递归一个子问题递归式是 T(n) T(n/2) Θ(1)套主定理得到 Θ(log n)。这里要特别注意二分查找本身是 O(log n)但前提是数组已经有序。如果题目先让你排序再二分那总复杂度就是排序的 O(n log n) 加上查询的 O(log n)。我见过有人在这类题上只写 O(log n)把前面排序的代价漏掉了直接丢一半分。最大子数组问题是分治里最值得琢磨的一道经典题。它的分治思路是最大子数组要么完全落在左半要么完全落在右半要么横跨中点。前两种递归求解第三种从中点向两边扫一遍找最大和扫描是线性的。所以递归式是 T(n) 2T(n/2) Θ(n)答案 Θ(n log n)。有意思的是这道题用动态规划能做到 O(n)考卷上经常让你把两种方法都写出来并比较这时候你要能说清楚分治法存在重复访问DP 通过记录以每个位置结尾的最大和避免了重复计算。快速排序严格说也是分治但它的划分不是按位置切而是按基准值分。它的平均复杂度 Θ(n log n)最坏 O(n²)最坏发生在每次选的基准都是极值的时候比如对已经有序的数组取第一个元素当基准。考试里如果问如何避免快排退化标准答案是随机选取基准或者三数取中把最坏情况变成概率极小的事件。我一般还会补一句随机化之后虽然理论最坏还是 O(n²)但它的期望复杂度稳定在 Θ(n log n)工程上这就够用了。讲一个我自己的踩坑经历。有次考试让分析在 n 个元素里同时找最大值和最小值最少需要多少次比较。我第一反应是分治两个子问题各找最值再合并写了半天比较次数。正确做法其实是两两分组先把元素配对每对比较一次分出大小然后在所有较大者里找最大值、所有较小者里找最小值。总比较次数是 3n/2 - 2比朴素的 2n - 2 少了四分之一。这个例子说明分治不是万能的有些题用一点预处理思维反而更快答题时别一根筋。3. 动态规划状态定义定生死写对一半就赢动态规划是整张卷子分值最高、也最容易拉开差距的部分。我把它放在复杂度之后讲是因为 DP 的复杂度分析全靠你状态怎么定义状态定错了后面方程再漂亮也是白搭。DP 的核心就三步定义状态、写状态转移方程、确定边界和计算顺序。这里面最难的是第一步也是最多人卡住的地方。先说矩阵链乘这是 DP 的入门经典题。问题是有 n 个矩阵连乘加括号的顺序不同总的标量乘法次数差异巨大。状态定义 m[i][j] 表示从第 i 个到第 j 个矩阵连乘的最少乘法次数转移方程是 m[i][j] min{ m[i][k] m[k1][j] p[i-1]·p[k]·p[j] }k 从 i 到 j-1。这里 p 数组是矩阵的维度链第 i 个矩阵的维度是 p[i-1] × p[i]。计算顺序必须按区间长度从小到大因为长的区间依赖短的区间这个顺序写错了数组里的值还没算出来就被引用了答案直接崩。0-1 背包是另一道必考。状态 f[i][v] 表示前 i 件物品、容量为 v 时能装的最大价值转移方程是 f[i][v] max( f[i-1][v], f[i-1][v-w[i]] val[i] )。前一项是不选第 i 件后一项是选。基于一维数组的滚动优化要倒序遍历容量 v从大到小这样能保证每件物品只用一次如果你写成正序遍历就变成了完全背包每件可以用无限次。这个正序倒序的区别是考点我见过太多人在卷子上写反了还浑然不觉。注意0-1 背包的一维优化必须倒序完全背包才是正序。这个细节一旦写错整道题的结果全错而且很多老师改卷时第一眼就看这里。最长公共子序列LCS也是高频题。状态 c[i][j] 表示字符串 X 前 i 个字符和 Y 前 j 个字符的 LCS 长度。当 X[i] Y[j] 时c[i][j] c[i-1][j-1] 1否则 c[i][j] max(c[i-1][j], c[i][j-1])。时间和空间都是 O(mn)。如果要还原出具体的子序列就沿着一张方向表回溯相等就记下字符往左上走否则往值大的那个方向走。这道题经常还会追问空间优化答案是用两行滚动数组把空间压到 O(min(m,n))代价是没法回溯出具体序列了只能求长度。最长递增子序列LIS是一道能体现算法优化思维的题。朴素 DP 的方程是 dp[i] max(dp[j]) 1j i 且 a[j] a[i]复杂度 O(n²)。但如果用贪心加二分维护一个当前长度下最小的结尾元素数组能做到 O(n log n)。考试里如果只要求写一种写 O(n²) 的保险如果要求最优就得把二分优化版写出来。这道题的二分思想很容易和前面的二分查找串起来复习时放在一起记会更牢。编辑距离是 DP 里比较有工程味的一道。状态 dp[i][j] 表示把 A 的前 i 个字符变成 B 的前 j 个字符最少要几步允许插入、删除、替换三种操作。转移方程分四种情况字符相等时继承 dp[i-1][j-1]不等时取 dp[i-1][j]删除、dp[i][j-1]插入、dp[i-1][j-1]替换三者最小值加一。这道题在自然语言处理、拼写纠错里都有实际应用理解它比死记公式有用得多。关于 DP 还有一个经常被问到的理论点最优子结构和重叠子问题。这两条是 DP 适用的前提缺一不可。最优子结构是说大问题的最优解包含子问题的最优解重叠子问题是指递归求解时会反复遇到同样的子问题。如果子问题不重叠那用分治就够了如果连最优子结构都没有那就得考虑别的模型。考试里让你判断某问题能否用 DP 解决时就把这两条拿出来对照分析逻辑链会很清晰。4. 贪心算法能用不能用靠交换论证说话贪心算法看着比 DP 简单写起来也短但它有个致命前提——你得证明贪心选择是正确的。很多人答题时直接写一套贪心策略就算完完全不证明这是丢分的重灾区。贪心正确性的标准证明方法是交换论证假设存在一个最优解其中第一个选择跟贪心选择不一样然后证明把它换成贪心选择后解不会变差从而说明贪心选择一定存在于某个最优解里。活动选择问题是贪心的标准范例。有 n 个活动每个活动有开始和结束时间要选出最多数量的互不冲突活动。贪心策略是按结束时间从早到晚排序然后依次选不冲突的。为什么按结束时间而不是开始时间或持续时间因为结束越早给后面活动留的空间越大这是尽早腾出资源的思路。交换论证的证明是最优解里第一个活动如果是 f结束时间记为 e_f贪心选的是结束最早的活动 g那么 e_g ≤ e_f把 f 换成 g 后剩下的活动集合兼容性只会更好不会更差。这个证明思路你必须能默写。Huffman 编码是贪心里唯一带点数据结构味道的题。构造方法是用最小堆每次取频率最小的两个节点合并直到只剩一个节点。得到的编码树保证加权路径长度最小也就是总的编码长度最短。考试里常见的考法是给一组频率让你手画 Huffman 树并写出各字符的编码。画的时候有个技巧合并产生的新节点要重新放回堆里参与比较别漏掉另外同一组频率的 Huffman 树不唯一但只要加权路径长度算对编码怎么标左右都行。最小生成树有两个贪心算法Prim 和 Kruskal。Prim 从一个点出发每次选连接当前树和外部的最短边适合稠密图用邻接矩阵加朴素实现是 O(n²)Kruskal 把所有边排序后依次加用并查集判断是否成环适合稀疏图复杂度 O(E log E)。这两个算法的选用逻辑经常被考点少边多用 Prim边少点多用 Kruskal。这个判断背后是复杂度表达式的实际含义不是拍脑袋。单源最短路径里Dijkstra 是贪心的代表但它的适用条件经常被考——不能有负权边。原因是 Dijkstra 的核心假设是已经确定的最短距离不会再被更新一旦出现负权边后面可能通过一条负边把已经确定的点再缩短这个假设就崩了。如果有负权边得用 Bellman-Ford它的复杂度是 O(VE)通过 V-1 轮松弛把所有最短路径找出来而且它还能检测负权回路。提示题干里出现负权边三个字Dijkstra 直接排除用 Bellman-Ford如果还要求所有点对的最短路那就是 Floyd-Warshall三重循环 O(n³)。0-1 背包和分数背包是检验你懂不懂贪心边界的经典对比。分数背包允许把物品切开按单位价值排序贪心取就对了因为切开之后每个部分的价值密度一样局部最优能推出全局最优。但 0-1 背包不能切贪心选单位价值最高的可能挤占空间导致总价值反而不如最优解所以必须用 DP。这道对比题几乎是每张卷子的必考点答题时要把为什么贪心在这里失效讲清楚最好的方式是举一个反例。贪心还有一个理论工具叫拟阵用来判断一类问题是否具备贪心可行性。拟阵满足遗传性和交换性两条性质在拟阵上做贪心能得到最优解。这个知识点偏理论期末考得不多但如果老师讲到这一块你至少要能说出拟阵的两个性质以及最小生成树问题可以建模成图拟阵所以 Prim 和 Kruskal 才能保证最优。5. 图论大题最短路、生成树、最大流三条主线图算法在期末卷上的分量很重几乎是必考一到大题。复习时把它拆成三条主线最短路径、最小生成树、最大流。这三条线的算法结构、适用条件和复杂度各不相同我建议你列一张表横向对比着背比零散记忆强太多。问题类型算法适用条件时间复杂度数据结构单源最短路Dijkstra无负权边O((VE)log V)邻接表优先队列单源最短路Bellman-Ford可有负权边可检测负环O(VE)边表全源最短路Floyd-Warshall可有负权边不能有负环O(V³)邻接矩阵最小生成树Prim稠密图更优O(V²) 或 O(E log V)邻接矩阵/优先队列最小生成树Kruskal稀疏图更优O(E log E)并查集最大流Ford-Fulkerson增广路思想依实现而定残量网络最大流Edmonds-KarpBFS 找增广路O(VE²)邻接表队列拓扑排序是 DAG有向无环图上的基础操作也是很多图算法的前置。实现方式是不断找入度为 0 的点输出并删除用队列维护这些点复杂度 O(VE)。它的实际意义是给有依赖关系的任务排序比如课程先修关系、编译构建顺序。考试里拓扑排序经常和判断图是否有环结合考如果拓扑排序输出的点数少于总点数说明图里有环。最大流是图论里公式感最强的一块核心定理是最大流最小割定理——一个网络的最大流等于最小割的容量。Edmonds-Karp 算法是 Ford-Fulkerson 的一个具体实现区别在于它每次用 BFS 找增广路保证找到的是最短增广路边数最少从而把复杂度收紧到 O(VE²)。理解残量网络是关键正向边的残量是剩余容量反向边的残量是已经流过去的流量反向边的存在让算法可以反悔把之前流的量退回去改道。Floyd-Warshall 的代码只有五行但很多人背不下来因为它有个容易记混的循环顺序。正确顺序是最外层循环 k 是允许经过的中间点内两层是起点 i 和终点 j。计算式是 dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。这个 k 必须在最外层因为它表示的是一种逐步放开中间点限制的 DP 思想。如果你把 i 或 j 放到最外层算法就错了。这个顺序是考点我见过有人顺手写成 k 在内层结果全盘皆错。还有一类最短路变体值得单独准备就是在 DAG 上求最短路。因为 DAG 没有环可以按拓扑序处理复杂度降到 O(VE)比 Dijkstra 还快。题目如果明确说是 DAG你就要意识到可以用拓扑排序加一次线性扫描搞定而不是上来就调 Dijkstra。这种识别特殊结构用更优算法的能力往往是拿满分和拿九十分的差别。6. 字符串匹配KMP 的 next 数组手算不再翻车KMP 是那种上课听懂了、考试手算就出错的典型算法。它的价值在于把朴素字符串匹配的最坏 O(mn) 降到 O(mn)m 是模式串长度n 是主串长度。降复杂度的关键是利用已经匹配过的信息避免主串指针回退。朴素算法每次失配就把主串指针退回到起点、模式串指针清零KMP 则通过 next 数组有的教材叫前缀函数 π让模式串指针在失配时跳到一个合适位置主串指针一路向前不回退。手算 next 数组是很多人的噩梦我给你一个不出错的流程。next 数组的含义是对于模式串的每个位置求出该位置之前子串的最长相同前后缀长度。举个例子模式串是 ABABC我一步步算位置 1 之前没有字符记 0位置 2 之前是 A没有相同前后缀记 0位置 3 之前是 AB前后缀不同记 0位置 4 之前是 ABA前缀 A 和后缀 A 相同长度 1记 1位置 5 之前是 ABAB前缀 AB 和后缀 AB 相同长度 2记 2。所以 next [0, 0, 0, 1, 2]。这个手算流程你练五遍基本就稳了。注意不同教材的 next 数组定义可能差 1有的用最长前后缀长度有的用这个长度加一还有的直接把整个数组右移一位。答题前先看清楚教材或老师给的定义别按自己习惯来否则答案对不上。匹配过程本身也有讲究。主串指针 i 一直往前走模式串指针 j 在失配时回退到 next[j]。当 j 走到模式串末尾时说明匹配成功记录位置后把 j 回退到 next[j] 继续找下一个匹配。整个过程 i 不回退这是 KMP 线性复杂度的根本原因。理解这一点比死记代码重要得多。KMP 之外字符串这块偶尔还会考字典树Trie和 AC 自动机。字典树用来做前缀查询每个节点代表一个字符从根到某节点的路径是一个前缀插入和查询都是 O(长度)。AC 自动机是 KMP 思想在多模式串上的扩展本质是字典树加失配指针用来在主串里同时匹配多个模式串。这块考得少但如果老师课上强调过至少要把字典树的插入和查询代码写出来。7. 回溯与分支限界搜索题怎么把时间打下来回溯和分支限界都属于搜索这个大范畴前者用深度优先、后者常用广度优先或优先队列。它们的共同点是通过剪枝来减少搜索空间区别在于回溯是找所有可行解或一个可行解分支限界是找最优解。期末卷上这两块经常合在一起考让你设计剪枝函数。回溯的模板结构是固定的进入一个状态判断是否到达边界如果没到就遍历所有候选选择对每个选择判断是否满足约束满足就做出选择、递归、再撤销选择。这个做选择—递归—撤销选择的框架适用于 N 皇后、子集和、图着色、数独、全排列等一大类问题。写代码时最容易漏的是撤销选择那一步一旦漏了状态会被污染后面的分支全错。N 皇后是回溯的代表题。剪枝的关键是约束函数任何两个皇后不能在同一列、同一主对角线、同一副对角线上。列冲突用一个布尔数组主对角线用行号减列号作索引副对角线用行号加列号作索引这样判断冲突就是 O(1) 的。如果不做任何剪枝、直接枚举所有位置组合复杂度是 O(n^n) 量级剪枝之后实际能处理的 n 大得多。这个从枚举到剪枝的复杂度差异是答题时要重点说清楚的。分支限界比回溯复杂一点它需要维护一个当前已知最优解作为限界。搜索过程中如果某个节点的估价值已经比当前最优解还差就直接剪掉不用再往下搜。TSP旅行商问题的分支限界是经典例子每个节点估计一条下界比如已走路径长度加上每个未访问点最小出边之和如果这个下界已经超过当前最优解就剪枝。这里说的下界是分支限界的核心概念它必须保证不会高估否则会误剪掉最优解。LC 检索最小耗费优先是分支限界的一种搜索策略用优先队列每次取当前估价值最小的节点扩展。它和 BFS、DFS 的区别在于BFS 按层扩展DFS 按深度优先LC 按估价值优先。期末卷上如果问哪种策略能更快找到最优解一般答 LC 检索因为它优先探索最有希望的方向。不过 LC 的内存开销大因为它要把所有活节点都存在优先队列里这是它的代价。剪枝这块有个通用思路值得记剪枝函数分两类约束函数剪掉不满足约束的子树限界函数剪掉不可能产生最优解的子树。写剪枝时先想清楚什么样的分支一定没有希望把判断条件写出来往往能省掉大量搜索。考试里评分不太看你能不能真的把大实例跑出来更看你剪枝的逻辑对不对、复杂度分析说得清楚不清楚。8. NP 完全性证明题有一套固定的话术NP 完全性是算法课里最抽象的一块也是期末卷上很多人直接放弃的一道大题。但我要说这道题其实是最套路化的只要你掌握归约的固定写法拿分反而比 DP 稳。核心概念有四个P 类、NP 类、NP 难、NP 完全。P 是能在多项式时间内解决的问题NP 是能在多项式时间内验证一个解的问题NP 难是所有 NP 问题都能归约到它的问题NP 完全是既属于 NP 又是 NP 难的问题。要证明一个问题是 NP 完全需要两步第一步证明它属于 NP也就是给出一个多项式时间的验证算法第二步证明它是 NP 难的方法是找一个已知的 NP 完全问题把它在多项式时间内归约到你要证的问题上。第一步通常一句话带过最难的是第二步的归约构造。多项式归约的写法是有模板的。假设已知问题 A 是 NP 完全的要证问题 B 也是 NP 完全的就构造一个从 A 到 B 的变换 f使得 A 的实例 x 是是当且仅当 f(x) 是 B 的实例且答案为是并且 f 必须在多项式时间内算完。答题时你要写清楚三件事怎么把 A 的输入变成 B 的输入、为什么这个变换是多项式的、以及为什么两边的答案一一对应。经典的归约链条要记住SAT 是第一个被证明的 NP 完全问题3-SAT 由 SAT 归约而来然后 3-SAT 可以归约到顶点覆盖、团问题、哈密顿回路、子集和、0-1 背包的判定版等。这张归约图是答题时的弹药库遇到相关证明题就从中找最接近的已知问题往上套。比如要证团问题是 NP 完全的可以从顶点覆盖归约因为图 G 有大小为 k 的团等价于补图里有大小为 |V|-k 的独立集。提示判定问题和优化问题要分清。TSP 的判定版是否存在长度不超过 L 的回路是 NP 完全的但优化版求最短回路是 NP 难但不是 NP 完全的因为它不是判定问题没有多项式时间验证这一说。还有一个常考的对比NP 难和 NP 完全的区别。NP 难只要求所有 NP 问题都能归约到它不要求它本身属于 NPNP 完全则两个条件都满足。所以一个 NP 难问题可能比 NP 里任何问题都难甚至可能根本不可判定。理解这个层次关系就能回答如果 P NP 会怎样这类理论题了——如果 P NP那所有 NP 完全问题都能在多项式时间内解决但因为目前没人能证明 P 和 NP 是否相等所以我们只能对 NP 完全问题求近似解。9. 排序算法横向对比与考前最后的复习路线排序算法是贯穿整门课的基础期末卷上要么单独考一道对比题要么作为其他大题的一部分出现。我把常见排序的复杂度、稳定性、适用场景整理成表你考前扫一眼就够了。排序算法平均时间最坏时间空间稳定性特点冒泡排序O(n²)O(n²)O(1)稳定实现简单教学用插入排序O(n²)O(n²)O(1)稳定小规模或近乎有序时快选择排序O(n²)O(n²)O(1)不稳定交换次数少希尔排序O(n^1.3) 左右O(n²)O(1)不稳定插入排序的改进归并排序O(n log n)O(n log n)O(n)稳定最坏也是 nlogn需额外空间快速排序O(n log n)O(n²)O(log n)不稳定平均最快可随机化堆排序O(n log n)O(n log n)O(1)不稳定原地排序最坏有保证计数排序O(nk)O(nk)O(k)稳定适合值域小的整数基数排序O(d(nk))O(d(nk))O(nk)稳定适合固定位数的整数或字符串这张表里有三个高频考点。第一哪些排序是稳定的。稳定意味着相等元素排序后相对顺序不变归并、冒泡、插入、计数、基数稳定快排、堆排、选择不稳定。第二哪些排序最坏能保证 O(n log n)。只有归并和堆排能做到快排最坏会退化到 O(n²)。第三哪些是原地排序。快排、堆排、插入、冒泡、选择空间都是 O(1) 或 O(log n)而归并需要 O(n) 额外空间。线性时间排序要单独说一句。计数排序、基数排序、桶排序都基于不通过比较来决定顺序的思想所以能突破比较排序的 Ω(n log n) 下界。这道下界证明本身也是考点用的是决策树模型n 个元素有 n! 种排列决策树至少有 n! 个叶子而高度为 h 的二叉树最多有 2^h 个叶子所以 2^h ≥ n!解出 h ≥ log(n!) Θ(n log n)。这个证明逻辑特别漂亮我建议你把它完整背下来考到就是白送的分。考前最后两天怎么安排我分享一套自己用过的路线。第一天上午把复杂度分析、分治、DP 的递归式和状态方程全部默写一遍尤其是主定理的三种情况和几个经典递归式下午刷图算法把 Dijkstra、Bellman-Ford、Floyd、Prim、Kruskal、拓扑排序的代码在纸上手写一遍不查书晚上过一遍贪心的交换论证和回溯剪枝的模板。第二天上午专门攻 NP 完全性的归约链条和排序对比表下午把历年真题里的编程题挑两三道完整写出手写代码晚上早睡。答题顺序上有个实用建议先扫一遍卷子把复杂度题和排序对比这类确定性高、耗时不长的题先做掉把 DP 和 NP 证明这类需要思考的放中间最后做编程大题。这样能保证基础分先拿到手心态也稳。遇到完全没思路的证明题不要空着把你记得的相关概念、归约方向、复杂度关系写上去很多时候老师会给步骤分。最后再分享一个我自己总结的小技巧复习时不要只盯着答案对不对要盯着为什么是这个答案。算法设计与分析这门课考的不是记忆力而是你分析问题的思路。你能把主定理为什么分三种情况、DP 的状态为什么这么定义、贪心的交换论证为什么成立这几点讲清楚那不管题目怎么变你都能找到下手的地方。我当年就是靠这套讲清楚为什么的方法从六十多分一路刷到接近满分这个方法比任何题库都管用。