这门课叫《算法设计与分析》但真到了期末周你打开课本的那一瞬间就会发现它考的不是你能不能设计出一个新算法而是你能不能在两个小时内把一堆看起来毫不相干的模型识别出来然后套对模板、算对数、写出伪代码。考前突击这件事本质上是一场信息压缩战——把一学期几十万字的内容压成十几张能带进脑子的决策卡。我在这门课上花过整周时间从零开始啃也见过有人三天突击拿到不错的分数差别不在天赋而在于有没有抓住这门课的出题惯性。下面把我自己复习、陪考、复盘的全过程摊开讲包括哪些章节值得死磕、哪些可以放、编程题怎么在写不出来的情况下还能捞到步骤分适合完全没有系统学过、或者学过但已经忘得差不多的同学直接抄作业。1. 突击前先摸清这门课的出题惯性很多人一上来就从第一章开始翻翻到第二章就困了然后换本书重来一遍这是最典型的低效复习。任何一门有期末考的算法课它的卷子结构其实高度稳定概念辨析、复杂度计算、手工模拟、算法设计题、编程题大概就是这五块。你要做的第一件事不是学而是先弄清楚这五块各占多少分。1.1 设计和分析是两套完全不同的答题语言标题里这两个词拆开看就是两种题型。分析考的是给你一段代码或一个递归式让你推时间复杂度这类题答案是确定的对错分明是最该拿满的分。设计考的是给一个场景让你说用什么算法、为什么、怎么写这类题是主观题评分看的是思路链条是否完整而不是最后那行代码有多漂亮。我见过太多同学在分析题上丢分原因不是不会而是把 O(n log n) 写成了 O(n²) 或者漏掉了常数项以外的项。也见过在设计题上写了一大段代码结果零分的因为他没写复杂度分析也没说清楚为什么贪心在这里成立。记住一个原则设计题的评分点通常包括算法选择及理由伪代码复杂度分析三部分缺一部分就砍一截分。1.2 从题型反推复习优先级把复习时间按分值密度分配而不是按章节顺序分配。我给自己的排序是这样的优先级内容理由最高复杂度分析、递归式求解几乎所有大题都要用到出错则连带扣分高图算法MST、最短路、匹配手工模拟题和设计题双高频高动态规划设计题常客且套路清晰性价比高中分治、排序、KMP以手工模拟和概念题为主中回溯、分支限界、剪枝编程题高频但手写难度大低各种启发式算法模拟退火、粒子群等通常只考概念几句话就能答这张表不是绝对的但它背后的逻辑是通用的凡是能出成手工模拟的算法都值得优先复习因为手工模拟题的答案唯一、可控、必考凡是只能出成名词解释的算法看一眼、记住一句话定位就够了。1.3 战略性放弃是有必要的一学期讲的内容期末卷子最多覆盖六七成。剩下的三四成如果你时间不够放弃是理性的。判断标准很简单这个知识点能不能独立出一道 10 分以上的题如果不能它大概率只会以选择题或填空的形式出现投入产出比很低。举几个典型的低投入高回报例子了解模拟退火的核心思想是带着一定概率接受劣解从而跳出局部最优这一句话就足够应付一道两分的概念题知道DBSCAN 是基于密度的聚类不需要预先指定簇数量同样够用。反过来把时间花在推导这些算法的收敛性证明上风险极高且几乎不会考。提示放弃不等于不看。放弃是指只记结论不推过程这样即使考到也能拿到基础分。2. 复杂度分析是所有大题的地基先把它焊死如果只允许我复习一个知识点我会选复杂度分析。原因很直接它既是独立考点又是其他所有题目的隐藏评分项。你在设计题里写不出复杂度等于主动丢掉一到两分你在选择题里算错递归式可能连错三道。这块内容的特点是模型少、套路固定两天足够练到很稳。2.1 渐进记号不是背符号是读懂增长量级绝大多数人栽在把 O、Ω、Θ 当成纯符号记忆然后一到比较大小就懵。其实它们只是描述函数增长速度的三种关系O 是上界不超过Ω 是下界不低于Θ 是紧确界两者都满足。考试里让你判断 f(n) O(g(n)) 是否成立本质上就是问当 n 足够大时f 会不会被 g 的某个常数倍压住。这里有个常见的坑O 不是等于而是属于。写 f(n) O(g(n)) 是历史遗留的写法严格说应该是 f(n) ∈ O(g(n))。理解了这点你就不会纠结既然 2n O(n)那 O(n) 2n 对不对这种问题了。比较两个函数的增长速度时最实用的方法是取商求极限。判断 n log n 和 n^1.5 谁增长得快做个商再求极限如果趋于无穷说明分子快。有些题会给你一长串函数让你排序比如 n、n log n、n²、2ⁿ、n!、log n、√n掌握常见量级的阶梯就够了log n √n n n log n n² n³ 2ⁿ n! nⁿ顺带说一句log 的底数在渐进意义下不影响量级因为换底只差一个常数因子。所以 log₂n 和 log₁₀n 都是 Θ(log n)这一点经常被出成判断题。2.2 递归式求解主定理、递归树、代入法三件套算法分析题里最难也最常考的就是给一个递归式求渐进复杂度。比如 T(n) 2T(n/2) n。这类题有三种解法你需要根据题目特征选。主定理最快但适用条件严格。它只处理 T(n) aT(n/b) f(n) 这种形式。做法是比较 f(n) 和 n^(log_b a) 的大小关系如果 f(n) 更小答案就是 Θ(n^(log_b a))如果两者同阶答案就是 Θ(n^(log_b a) · log n)如果 f(n) 更大且满足正则条件答案就是 Θ(f(n))拿 T(n) 2T(n/2) n 举例a 2b 2n^(log₂2) nf(n) n两者同阶所以答案是 Θ(n log n)。这就是归并排序的复杂度几乎是必考的一个。递归树适合主定理套不上的情况尤其是 a 不是整数倍分或者递推式不规则的时候。方法就是一层一层画把每层的代价加总。这个方法的好处是直观考场上即使算不出精确解画个树也能拿到过程分。代入法也叫猜测验证是先猜一个答案再用数学归纳法证明它成立。它不常单独作为大题但在证明题里出现得很频繁。技巧是猜完以后一定要把常数 c 的取值范围写清楚否则归纳步骤会卡住。2.3 手算复杂度的稳定套路我给自己的手算流程是这样的基本不会漏项找到循环的终止条件和步长确定每层循环的迭代次数判断是否嵌套嵌套就相乘不嵌套就相加检查循环体内是否有与 n 相关的操作比如数组复制、递归调用最后只保留最高阶项去掉常数系数举个例子判断下面这段的复杂度for (int i 1; i n; i * 2) { for (int j 0; j i; j) { // O(1) 操作 } }外层循环 i 每次翻倍所以只跑 log n 次。内层循环次数是 1 2 4 ... n/2等比数列求和是 Θ(n)。两者相乘得到 Θ(n log n)。很多人会误以为两层循环就是 n²这里就栽了。3. 分治与递归三件套的骨架其实是同一件事分治是所有算法设计思想里最物理的一个因为它对应的代码结构非常固定。理解了分治二分查找、归并排序、快速排序、最近点对这些问题就都变成同一道题的不同参数。复习时要抓的是骨架不是每个例子的细节。3.1 分治三步走的真正含义标准的说法是划分、解决、合并Divide、Conquer、Combine。但光背这三步没用考试里真正被考的是你怎么证明这个划分是有效的。有效性的判断标准有两条子问题的规模要明显缩小且子问题之间不能有重复计算。以归并排序为例。划分是取中点一刀切解决是递归排好左右两半合并是把两个有序数组归并成一个。它的递归式是典型的 T(n) 2T(n/2) Θ(n)答案是 Θ(n log n)。这里的 Θ(n) 就是合并那一步的代价因为它要遍历所有元素一次。但是如果子问题之间产生了重叠分治就不适用了那是动态规划的地盘。这是分治和 DP 的分水岭记住了能省很多纠结。3.2 二分查找的边界问题是重灾区二分查找的思想简单到不用解释但它是面试和考试里最多人写错的算法没有之一。错的根源永远在边界while 用还是mid 要不要 1left 更新成 mid 还是 mid1。给你一个我一直在用的模板用整段代码记住它考试时直接默写比现场推导可靠得多def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这个模板的规则是区间始终是闭区间 [left, right]所以 while 用 更新时一定要跳过 mid。还有一点mid left (right - left) // 2比(left right) // 2更好因为它避免了两数相加溢出。虽然 Python 不会溢出但如果你写 C 或者 Java这个写法能救命。考场上的自检方法拿一个长度为 1 的数组和长度为 2 的数组手动跑一遍你的代码。这两个边界情况如果能过基本就没问题了。3.3 快速排序为什么看起来更快快排和归并都是 O(n log n)平均情况但实际运行中快排通常更快原因是它的常数因子小。快排是原地排序不需要额外的数组来归并而归并排序需要 O(n) 的辅助空间。这个区别在选择题里经常被考。但快排有个致命弱点最坏情况下退化成 O(n²)。当每次选的主元都是最大或最小值时划分就变成了 1 和 n-1递归深度达到 n。这就是为什么工程实现里会用随机化选主元或者三数取中。考试里可能会让你写出快排的一次划分过程。这时候要特别注意划分完成后主元应该被放到正确位置上划分函数的返回值是主元的最终下标而不是左右边界。这个细节写错后面递归调用就全乱了。4. 贪心和动态规划的分界线在哪这是整门课最容易混的一对概念也是最容易出设计题的地方。很多人做不出来题是因为根本判断不出该用贪心还是 DP于是在草稿纸上试半天最后两边都写一半。我给你一条判断准则贪心不问过去DP 记住过去。更具体一点如果一个问题的最优解可以由它的子问题的最优解直接组合得到最优子结构而且做选择时不需要回头反悔贪心选择性质那就能用贪心。如果子问题之间有重叠需要记住已经算过的结果那就是 DP。4.1 贪心的正确性怎么论证贪心题最大的陷阱是贪心策略看起来对但其实是错的。所以设计题里如果你答了贪心一定要给出正确性论证否则阅卷人完全可以认为你在碰运气。最常用的论证方法是交换论证。思路是假设存在一个最优解它跟贪心解在第一步做了不同的选择然后证明通过交换可以把最优解逐步改造得和贪心解一样而不会变差。这样就说明了贪心解也是最优的。以经典的区间调度为例给一堆区间选出最多的互不重叠区间贪心策略是每次选右端点最小的。交换论证的写法是设贪心选的是区间 a最优解选的第一个区间是 b。因为 a 的右端点最小所以 a 的右端点 ≤ b 的右端点把 b 换成 a 不会跟后面的区间冲突因此最优解不会变差。这类论证在考卷上写三四句就能拿分。4.2 动态规划的四个固定步骤DP 的解题流程是可以模板化的我复习时把它固化成四步定义状态dp[i] 或者 dp[i][j] 到底代表什么这是最关键的一步写状态转移方程当前状态如何从之前的状态推出来确定初始条件和边界dp[0] 是多少数组下标越界怎么处理确定计算顺序保证用到的状态已经算过拿最长公共子序列LCS举例。状态定义是 dp[i][j] 表示字符串 A 前 i 个字符和字符串 B 前 j 个字符的最长公共子序列长度。转移方程是如果 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])。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]这里有个手写容易出错的点dp 数组要多开一行一列作为边界用来表示空串的情况。很多人图省事只开 m×n结果初始化就崩了。这一步在考场上只要写出来就等于告诉阅卷人你懂 DP 的边界处理。4.3 那些一眼就能认出的 DP 标志复习到后期我总结出一批看到题干就知道是 DP的关键词求最大/最小值、有多少种方案、能不能凑出题目里出现了背包、子序列、编辑距离、硬币这类字眼暴力搜索的复杂度是指数级但问题规模又不小有一个明显的阶段性决策结构前一步的选择影响后一步反过来如果题目里出现了选最多的不冲突区间每次选最划算的这种描述优先考虑贪心。这个直觉在考场上能帮你省下至少十分钟的犹豫时间。5. 图算法是分值密度最高的地方如果要我说哪一章最值得投入答案一定是图论。原因很简单图算法几乎每一个都能出成手工模拟题而手工模拟题的答案唯一、给分严格、没有争议是性价比最高的得分点。MST、最短路径、拓扑排序、二分图匹配这四个是核心。5.1 最小生成树Prim 和 Kruskal 怎么选最小生成树的两种经典算法考试里经常让你二选一或者干脆两个都让你写。它们的选择逻辑其实很清楚维度PrimKruskal核心思想从一个点开始不断加最近的点把所有边排序依次加不构成环的边数据结构优先队列 / 邻接矩阵并查集 边排序时间复杂度O(n²) 或 O(m log n)O(m log m)适合稠密图稀疏图手工模拟难度中低按边权排序即可手工模拟时Kruskal 比 Prim 更容易做对因为它的流程就是把边从小到大排好一条条加跳过会成环的。判断是否成环靠目测就行。而 Prim 需要你每一步都维护一个已选集合和到集合的最短距离容易漏更新某个点的距离。注意考试让你手算 MST 时一定要把选边的顺序和总权值都写出来。只写最终结果阅卷人无法判断你是对的还是蒙的。5.2 最短路径三个算法的适用边界最短路径是图论里的另一个重头戏考的频率和 MST 差不多。关键是记住三个算法的边界Dijkstra单源最短路不能有负权边。核心是每次从未确定的点里选距离最小的那个然后松弛它的邻居Bellman-Ford单源最短路可以处理负权边还能检测负环。核心是松弛所有边 n-1 轮Floyd多源最短路全源之间两两最短距离。三重循环代码极短但复杂度是 O(n³)Dijkstra 为什么不能有负权因为它的贪心假设是当前距离最小的点其最短路径已经确定。如果存在负权边后面可能出现一条绕远路但总代价更小的路径这个假设就破了。这个解释在概念题里很值钱。Floyd 的代码短到几乎不会写错值得直接背下来def floyd(dist, n): for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]这段代码里循环顺序很关键k 必须是最外层。如果你把 k 放到最内层算法就是错的。这个点经常被出成判断题或者改错题。5.3 二分图匹配与匈牙利算法匈牙利算法用于求二分图最大匹配是这类课里比较特殊的一个考点因为它不像最短路那样有生活直觉。但它的思路其实很好理解不断尝试为每个左边的点找匹配如果目标点已经被占了就看看能不能给占用者换个别的点也就是找增广路。考试里通常不会让你手算很复杂的匹配但可能会让你说清楚增广路是什么。标准表述是一条起点和终点都是未匹配点且路径上匹配边和未匹配边交替出现的路径。找到增广路就能让匹配数加一这是匈牙利算法的核心。我个人的经验是这块内容不要试图理解所有细节先记住找增广路 - 匹配数 1这个循环然后在草稿纸上画个小图跑两遍比死记公式管用得多。6. 字符串匹配和 KMP手算 next 数组的固定套路KMP 是那种听懂了原理但一算就错的典型算法。原因在于不同教材对 next 数组的定义不一致有的是最长相等前后缀长度有的是加一后的值还有的是整体右移一位。你如果没搞清楚用的是哪套定义算出来的答案就会差一位。6.1 暴力匹配为什么慢KMP 省的是什么先搞清楚 KMP 到底在省什么。暴力匹配的问题在于一旦失配主串指针就要回退前面比较过的信息全部浪费。比如在AAAAAAAAAB里找AAAB暴力的做法会反复从头比。KMP 的做法是主串指针永远不回退失配时只移动模式串。移动多少由 next 数组决定。next 数组记录的是当前这个位置失配时模式串应该跳到哪个位置继续比较而它背后的含义是这段前缀里有多长的相等前后缀。6.2 手算 next 数组的稳定方法我给你一个手算不会错的方法。以模式串 ABABACA 为例下标0123456字符ABABACA最长相等前后缀0012301计算规则是对每个位置看它前面那段子串不包含自己的最长相等前后缀长度。位置 4 的字符是 A前面是 ABAB最长相等前后缀是 AB长度 2不对要包含自身。这里就体现出定义差异了。我的建议是考试前一定要确认课本用的是哪套定义然后把课本例题完整手算两遍。这是唯一不会出错的办法因为不同教材的答案确实不一样网上搜到的结果经常对不上。6.3 考场上的自查技巧如果你算完 next 数组不确定对不对有个简单的验证方法把模式串和它的 next 值对应画出来检查每个非零值是否真的对应了一段相等的前后缀。比如 next[4] 3 意味着模式串前 3 个字符和后 3 个字符相同。你直接肉眼核对一下就能发现错误。还有一个坑next[0] 的值在不同定义下可能是 0 也可能是 -1。如果课本用的是 -1你写成 0 就是错的。这种细节在一道 8 分的题里可能就扣掉 2 分。7. 回溯、分支限界与剪枝编程题的拿分重灾区这部分对应的是搜索类算法也是期末考试编程题最爱出的类型。它的特点是思路好懂、代码好写但性能优化难。考试里通常不会要求你写出最优解而是要求你能写出来、能说明复杂度、能提出优化方向。所以复习的重点是模板和剪枝思路。7.1 回溯的通用模板回溯Backtracking的本质是带撤销的深度优先搜索。所有回溯题的代码骨架几乎一模一样def backtrack(path, choices, result): if 满足结束条件: result.append(path[:]) # 注意要拷贝 return for choice in choices: if not is_valid(choice): continue path.append(choice) # 做选择 backtrack(path, new_choices, result) path.pop() # 撤销选择这个模板的关键是做选择和撤销选择必须成对出现。我见过太多人写完忘了 pop结果结果集里全是错的。result.append(path[:])里的切片也很关键不切片的话后面修改 path 会连带改掉之前存的结果这是新手最常踩的坑。7.2 剪枝的三种思路剪枝Pruning是把暴力搜索变成可接受的算法的核心手段。考试里常见的剪枝思路有三种可行性剪枝当前状态已经不可能满足约束了直接返回。比如凑数问题里当前和已经超过目标最优性剪枝当前代价已经比已知最优解还差继续搜没意义对称性剪枝排除掉等价的分支比如排列问题里跳过重复元素给出剪枝思路往往比自己写完整代码更能拿分因为阅卷人看的是你有没有优化意识。答题时可以说在搜索前先对候选集排序这样一旦某个分支被剪掉后面的分支可以直接跳过这样一句话就是一个得分点。7.3 分支限界和回溯的区别分支限界Branch and Bound经常和回溯一起出现因为两者都是搜索。区别在于搜索方式和目标维度回溯分支限界搜索方式深度优先广度优先 / 优先队列存储结构栈递归隐式实现队列 / 优先队列主要目标找所有解或任一可行解找最优解关键机制约束函数剪枝限界函数剪枝分支限界的关键在于设计限界函数也就是当前节点的上界估计。如果这个上界已经不如当前最优解就可以把整个子树砍掉。答题时如果能写出一个合理的限界函数基本就是满分思路了。8. 排序算法全家桶一张表记住所有排序是最基础也最容易考的内容几乎每份卷子都会覆盖。它的问题是知识点太碎光靠背容易混。我的办法是做一张对照表把所有关键维度列出来考前反复看这一张表就够了。8.1 稳定性、原地性、复杂度一次说清算法平均时间最坏时间空间稳定原地冒泡排序O(n²)O(n²)O(1)是是插入排序O(n²)O(n²)O(1)是是选择排序O(n²)O(n²)O(1)否是归并排序O(n log n)O(n log n)O(n)是否快速排序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)是否这张表里最值得关注的是稳定性和最坏复杂度两列。稳定性指的是相同元素的相对顺序在排序后是否保持不变。归并和冒泡稳定快排和堆排序不稳定这个在选择题里考得极频繁。8.2 堆排序的手推过程堆排序是排序题里最容易手算错的一个因为它涉及建堆和调整两个阶段的反复操作。我的做法是分两步走先把数组理解成一棵完全二叉树下标 i 的左右孩子是 2i1 和 2i2然后从最后一个非叶子节点开始逐个做下沉操作。建立大顶堆后每次把堆顶和末尾交换然后对剩下的部分重新调整。手算时画树比纯数字更清晰建议在草稿纸上画。8.3 外部排序和 K 路归并如果课程讲了外部排序那大概率会出在大题里。核心是把大文件分成若干块每块在内存里排序后写回磁盘然后做多路归并进行合并。考的是为什么要多路归并——单次归并路数越多需要的趟数越少总的 I/O 次数就越少。这个逻辑在答设计题时非常值钱。9. 考前 48 小时的时间分配与考场策略前面的内容都是知识层面的最后说点操作层面的。这是我复盘过很多次才总结出来的也是决定你能不能把学到的内容转化为分数的关键。9.1 倒计时复习表如果你只有两天时间我会这样排第一个半天复杂度分析 主定理配 5 道递归式求解题第一个晚上图算法三件套MST、最短路、拓扑排序把 Kruskal、Dijkstra、Floyd 的手算各跑两遍第二个半天DP 四步法 贪心交换论证各练 3 道典型题第二个晚上排序对照表 KMP 手算 回溯模板重点看自己最容易错的点考前两小时只看自己整理的一页纸速查卡不动新题这个安排的核心是把有限的题量分给分值密度最高的模块而不是平均用力。图算法和 DP 占的时间应该超过一半。9.2 编程题怎么写才能拿到步骤分很多人以为编程题写不出完整代码就是零分这是误解。评分通常分几档思路对不对、伪代码完不完整、关键步骤有没有、代码能不能跑。你就算最后跑不起来只要前三档占住也能拿到一半以上的分。我的答题顺序是这样的先用两三句话写清楚算法思路和为什么这么选写出每一步的伪代码变量含义标注清楚附上复杂度分析最后才写具体语言的代码这样即使时间不够前面三步也能保住分。提示伪代码不要写得太随意循环边界和返回条件一定要明确。阅卷人看不懂你的伪代码等于没写。9.3 考场上的最后检查清单做完卷子剩下的时间不要发呆按这个顺序回查复杂度有没有写成最简形式O(2n) 要写成 O(n)O(n² n) 要写成 O(n²)图算法题有没有写出总权值或最终距离DP 题的初始化和边界有没有处理空串、空集、下标 0 的情况next 数组的定义跟课本一致吗排序题的稳定性有没有搞反有没有漏写算法选择的理由这几条检查下来通常能挽回五到十分。我个人复习这门课最大的体会是算法课的期末考跟真正的算法能力其实是两回事。考场上你需要的不是灵感而是把常见的模型准确地匹配到题目上然后把模板完整地写出来。突击的本质就是压缩这张模型到模板的映射表把它的条目做得越少、越清晰你在考场上反应就越快。我最后一次考这门课之前把整本书压成了六页笔记其中三页是代码模板两页是对照表一页是易错点。翻完最后一遍进考场的时候我心里其实是有底的——不是因为我会做所有题而是因为我知道遇到哪类题该做什么。