期末周的图书馆凌晨两点我在翻一本被咖啡渍染了角的《算法设计与分析》书页上还留着上届学长的铅笔批注——那是他熬了三个通宵后总结的一句话这科不是背出来的是算出来、推出来、写出来的。说这话的时候我并不信直到考完复盘,才发现算法设计与分析这门课的考试逻辑确实和别的课不一样。它看着抽象其实套路极其固定看着知识点散其实考点高度集中。这篇就是我当年考前突击的完整复盘加上后来带过几届学弟学妹总结出来的东西从信息收集、考点定位到复杂度硬算、五大范式拆解、编程题手写再到时间分配和踩坑经验全都摊开讲。不管你是刚考完期中还没缓过来还是考前一周才想到这门课要考这篇都能直接拿去用。它解决的核心问题只有一个用最短的时间把有限的分抓到手里同时别把真正有用的算法思维丢掉。1. 先搞清楚这门课到底考什么突击前的信息收集1.1 为什么突击在算法课上也有讲究很多人一听考前突击就想到熬夜硬背但这门课恰恰最吃情报和结构。算法设计与分析本质上是三门课揉在一起一部分是数学复杂度、递归式、正确性证明一部分是设计范式分治、动态规划、贪心、回溯、分支限界还有一部分是图论与判定理论最短路、最小生成树、NP完全性。这三块的考试风格完全不同数学部分考推导和计算范式部分考识别和建模图论部分考算法流程和手推。我踩过的最大坑就是第一周拿着整本书从头看看到第三章还在纠结渐进符号的严格定义结果最后三天才意识到真正的大题集中在动态规划和回溯。突击的核心不是看多少而是看对多少。所以我建议你先花两个小时做一件看起来很功利但极其重要的事——把历年的题型摸清楚把分值分布画出来。这个动作做完你后面的每一小时复习都会踩在得分点上而不是踩在舒适区里。提示如果你实在找不到历年真题退一步也要把老师划的重点、期中卷、课堂例题、作业题这四样凑齐它们的重合度通常高得惊人。1.2 从哪搞到有效信息三类资料的价值排序从我的经验看资料的价值顺序大致是这样的历年真题 老师课上明确点名的例题 作业题 教材课后习题 参考书。真题的价值不用解释它直接告诉你题型、分值、深度。但注意真题要看的不是题目本身有多难而是它反复出现的骨架。比如某年考了矩阵连乘的填表另一年考了最长公共子序列的填表看着不一样其实都是网格型动态规划这一根骨头做题思路、填表顺序、复杂度分析全都通用。课上点名的例题是第二优先级因为老师愿意在课上花十分钟推导的东西往往就是他认为值得考的。作业题的用处在于查漏尤其是那些你当时抄答案混过去的题现在正好补上。教材课后题量大但质量参差适合作为熟练度的补充练习但不能作为主线。参考书我是这么用的只在某个知识点用教材看不懂时去翻一本讲得更啰嗦的书找那一段看完立刻回来绝不顺着参考书往下读。资料类型优先级主要用途使用建议历年真题最高摸清题型与分值先看题不看答案自己判断考察点老师点名例题高锁定必考范式动手推一遍别只看懂作业题中查漏补缺专挑当时做错的教材课后题中低熟练度训练限时做不求全参考书低补单一知识点只看那一段立刻回来1.3 复习优先级的判断逻辑判断一个知识点值不值得花时间我一般用两个维度考频和性价比。考频好理解就是它出现得多不多性价比指的是投入一小时能换来多少分。复杂度计算就是典型的超高性价比——基本是送分题公式固定练两小时就能稳拿。反过来NP完全性的严格归约证明性价比就偏低虽然概念必须懂但如果时间紧张把P、NP、NPC、NP-hard这四个概念和典型问题归类记牢就够了深究归约链条反而挤占了大题时间。这种判断背后有个很实际的逻辑突击阶段你的目标不是拿满分而是把会做但算错和根本没看这两种失分尽量消掉。前者靠练熟后者靠覆盖。所以我通常把时间切成三块——概念和计算占四成范式建模占四成图论算法流程占两成。这个比例不是死的你得根据自己学校的风格微调但整体思路是先把必考的稳住再冲有区分度的。2. 复杂度分析送分题还是隐藏的扣分坑2.1 渐进符号与常见复杂度排序渐进符号这块看着是概念题其实是整门课的地基。大O表示上界大Ω表示下界大Θ表示紧确界小o和小ω表示严格的不取等号的上界和下界。很多同学只记符号不记语义结果一做题就翻车。比如题目问3n² 5n 2 的紧确界是什么你要能立刻答出Θ(n²)并且顺手说明为什么常数和低阶项可以丢掉。丢掉低阶项和常数的逻辑很简单当n足够大时最高阶项会主导整个函数的增长前面的系数只是缩放不改变增长的量级。这也是复杂度分析的灵魂——它关心的不是具体跑多少秒而是输入规模翻倍时工作量怎么变。这一点我用生活类比来解释你看一个人爬楼梯累不累不看他每步迈多大而看楼梯有多少阶。阶数翻倍累的程度大致翻倍这跟一个人腿长腿短常数关系不大。复杂度排序必须背到条件反射O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)。考试里常让你把几个表达式排序或者判断n log n 是否快于 n²答错这种题特别冤因为它完全靠记忆。我建议你睡前默写两遍这个链条顺便配几个例子比如二分查找是O(log n)归并排序和堆排序是O(n log n)冒泡和插入是O(n²)朴素的斐波那契递归是O(2ⁿ)。2.2 递归式求解主定理与递归树递归式求解是复杂度部分的重点和难点核心工具就两个主定理和递归树。主定理适用于形如 T(n) aT(n/b) f(n) 的式子其中a是子问题个数n/b是子问题规模f(n)是分解和合并的代价。判断规则看 n^(log_b a) 这个量和 f(n) 谁更大如果 f(n) 明显更小答案就是 Θ(n^(log_b a))如果两者同阶可能差一个log因子答案要乘一个 log n如果 f(n) 明显更大且满足正则条件答案就是 Θ(f(n))。这个规则我用一个拔河的比喻记把 n^(log_b a) 看成左边队伍的力气把 f(n) 看成右边队伍的力气。左边压倒性赢结果听左边的势均力敌加个log再听右边压倒性赢结果听右边的。比死记公式好记多了。实测下来考试的递归式大多落在前两种情况第三种偶尔考但只要记得确认正则条件这一步就不会丢分。递归树则更适合那些不规整、不好套主定理的式子。它的思路是把递归展开成一棵树每层的代价加起来再对所有层求和。比如 T(n) 2T(n/2) n展开后每层代价都是n一共log n层总代价就是n log n正好对上归并排序。我建议你至少手画三棵递归树画到不假思索为止因为画图这个动作能暴露你对层数怎么算的真实理解程度。2.3 实操手算几道典型题光看规则不动手考场上一定手生。我当年的做法是拿一张纸把下面这几类各算三遍直到全对。第一类直接判断复杂度。比如给你一段双重循环外层从1到n内层从外层到n问时间复杂度。要一眼看出内层循环次数是 n (n-1) ... 1总和是 n(n1)/2所以是Θ(n²)。这类题的关键是别急着套结论先把循环次数推出来。第二类套主定理。比如 T(n) 9T(n/3) n这里 a9b3n^(log_3 9) n²而 f(n)n 更小所以答案是 Θ(n²)。再比如 T(n) T(2n/3) 1a1b3/2n^(log_{1.5} 1) n⁰ 1和 f(n)1 同阶所以答案是 Θ(log n)这正好对应每次缩到三分之二缩到1要log次。第三类画递归树。比如 T(n) 3T(n/4) n²用递归树展开能看到根节点代价n²往下一层是3个(n/4)²总和是(3/16)n²再往下等比缩小公比小于1求和收敛到常数倍的n²所以整体是Θ(n²)。这里能看出主定理和递归树互相印证做题时用哪个顺手用哪个。注意主定理不是万能的遇到 T(n) 2T(n/2) n log n 这种卡在中间的情况主定理直接套会出问题这时候老老实实画递归树更稳。3. 五大算法设计范式分治、动态规划、贪心、回溯、分支限界3.1 分治法识别信号与复杂度推导分治法的套路非常统一把问题分成若干规模更小的同类子问题分别求解再合并结果。三步是分、治、合。识别信号通常出现在题目里带二分折半归并划分这类词的时候。典型例子有归并排序、快速排序、二分查找、最大子数组、大整数乘法、最近点对。分治的复杂度分析几乎都要落到递归式上所以它和第二章是联动的。归并排序是 T(n)2T(n/2)O(n)解出O(n log n)二分查找是 T(n)T(n/2)O(1)解出O(log n)。这些推导要能随手写出来因为考试常让你写出递推式并求解。分治最容易出错的地方在于合并步骤的代价估计。很多人写递推式时把合并写成O(1)结果答案全错。判断合并代价的方法是合并时需要遍历或比较的子问题结果有多少个元素如果是把两个有序数组合成一个那代价就是O(n)。我见过太多人在这里丢分说到底还是没把分治的三步各花了多少想清楚。另外分治和动态规划的关系也值得留意分治的子问题互相独立、不重叠而动态规划的子问题会重叠这个区别是判断用哪种方法的第一信号。3.2 动态规划状态定义才是灵魂动态规划是这门课分值最高、也最容易拉开差距的部分。它的核心思想是用空间换时间——把重复计算的子问题结果存起来避免重复求解。但我必须强调动态规划真正难的不是写代码而是定义状态和推导状态转移方程。这一步想清楚了剩下就是填表。状态定义一般问自己两个问题我要记录什么信息才能做出下一步决策这个信息能不能用下标表示比如0-1背包状态 dp[i][j] 表示前i件物品、容量为j时能拿到的最大价值因为你要同时知道考虑到第几件和还剩多少容量。再比如最长公共子序列dp[i][j] 表示第一个串前i个字符和第二个串前j个字符的最长公共子序列长度。状态定义对了转移方程往往自然就出来了。状态转移方程的推导逻辑就是穷举最后一步的所有选择。背包问题最后一步要么不拿第i件要么拿第i件取两者的较大值。LCS最后一步要么两个字符相等可以一起匹配要么不等看放弃哪一个。这种穷举最后一步的思路能套用到绝大多数动态规划题上。填表顺序也很关键原则是用到的状态必须先算出来。背包通常按i从小到大、j从小到大LCS按i、j从小到大区间型问题如矩阵连乘、石子合并按区间长度从小到大。搞错顺序填出来的表就是错的。我当年就是在一道区间DP上栽过明明方程写对了结果因为填表顺序错答案全崩。问题状态定义转移方程核心填表顺序0-1背包前i件、容量j的最大价值取/不取第i件i升序j升序最长公共子序列前i、前j的LCS长度字符相等则1否则取maxi升序j升序矩阵连乘区间i到j的最少乘法数枚举分割点k区间长度升序最长递增子序列以第i个结尾的LIS长度枚举前面比它小的i升序3.3 贪心算法证明才是拿分点贪心算法的形式很简单每一步都选当前看起来最好的不回头。它比动态规划好写但难在证明。考试里如果只让你用贪心求某问题你写出算法只是第一步老师真正想看你证明这个贪心选择是安全的。所谓安全是指贪心做出的选择一定包含在某个最优解里且不会让剩下的问题变差——这就是贪心选择性质和最优子结构。拿活动安排来说策略是每次选结束时间最早且和已选活动不冲突的。为什么选结束最早因为结束越早留给后面活动的时间就越多这一步的直觉背后其实是交换论证假设最优解没选这个最早结束的活动而是选了另一个那么把那个换成最早结束的不会让后面的活动更差所以总可以换。这个交换论证是贪心证明的标准武器基本每道贪心证明题都能用。常见的贪心问题要背下策略活动安排按结束时间排序、哈夫曼编码每次合并最小的两个、最小生成树Prim任选起点不断加最近点、Kruskal按边权从小到大加且不成环、Dijkstra每次选离源点最近的未确定点。至于0-1背包贪心是错的这是经典陷阱因为按单位价值排序未必得到最优解必须用动态规划。这个反例考试超爱考一定要能说清楚为什么贪心失效。3.4 回溯与分支限界搜索树上的剪枝艺术回溯法的本质是深度优先地搜索解空间树走不通就退回上一层再试。它的框架非常固定递归函数里先判断是否到达边界再 enumerate 当前所有可能的选择做选择、递归、撤销选择。撤销选择这一步也就是回溯是它和普通递归的区别很多同学忘了撤销导致状态污染。典型题目有N皇后、图着色、子集和、全排列、旅行商。以N皇后为例按行放皇后每行尝试所有列用三个数组分别标记列、主对角线、副对角线是否被占用冲突就跳过走到第n行就是一个解。这里的剪枝冲突检测是效率的关键没有剪枝的回溯会退化成暴力枚举。分支限界法则是广度优先或优先队列地搜索并且用限界函数剪掉不可能产生最优解的分支。它和回溯最大的不同是搜索方式回溯深搜分支限界广搜或按界值优先。0-1背包的分支限界会用当前价值加上剩余物品全部装入的上界作为限界如果这个上界还不如当前已知最优解就剪掉。理解两者的区别考试里让你对比时就能直接说清楚。心得回溯和分支限界的手写题先把解空间树的形状画出来再写递归/队列框架最后加剪枝。顺序反了容易越写越乱。3.5 五大范式横向对比把这五个范式放在一张表里对比是我复习后期的杀手锏。因为考试经常出一段描述让你判断该用什么方法这时候你脑子里就必须有一张对照表。范式核心思想子问题关系典型问题拿分要点分治分而治之再合并独立、不重叠归并排序、最近点对递推式与合并代价动态规划存表避免重复计算重叠背包、LCS、矩阵连乘状态定义与填表顺序贪心每步选当前最优独立活动安排、哈夫曼、MST贪心正确性证明回溯深搜剪枝解空间树N皇后、图着色撤销选择与剪枝分支限界广搜/优先限界解空间树0-1背包、TSP限界函数设计我一般会盯着这张表再默问一遍如果题目里子问题会重叠用哪个如果要求最优解且能证明局部最优可推全局用哪个这种自问自答练几轮判断速度会快很多。4. 期末编程题怎么练从看懂到写出来4.1 编程题常见题型清单期末的编程题通常以手写伪代码或补全代码的形式出现极少让你现场跑程序。所以练习的重点不是调试而是把框架写对、把边界写对。常考题型其实就那几类排序类的归并和快排、动态规划的背包和LCS、图的最短路和最小生成树、回溯的N皇后和全排列、还有二分查找的各种变体。我建议你把这几类各手写三遍不看任何参考。第一遍看着模板抄第二遍合上模板默写第三遍限时十分钟内写完。这个渐进式练习能有效对抗看着会、写起来卡的毛病。手写的时候特别注意边界数组越界、递归终止条件、初始化值这些都是扣分重灾区。4.2 手写代码的套路伪代码优先很多人一上来就写C或Java的完整代码结果被语法细节绊住思路反而断了。我的做法是先写伪代码把逻辑骨架搭好再补具体语法。伪代码有个好处是它逼着你关注算法本身而不是分号和大括号。写归并排序时我就固定成三段分解取中点、递归左右两半、合并双指针归并。合并那一段是重点也是常考的手写点因为它展示了O(n)合并的具体做法。双指针归并的逻辑是两个指针各指向一个有序子数组的开头比较当前元素小的先放入临时数组指针后移直到一个用完再把剩下的接上。写动态规划时我固定成四段定义dp数组并说明含义、初始化边界、嵌套循环填表、返回答案。这四段写清楚即使代码有小瑕疵老师也能看出你思路完整。写回溯时固定成三段终止条件、遍历选择、回溯撤销。这几套模板练熟考试就能像搭积木一样拼出来。# 以最长公共子序列为例手写时的标准结构 def lcs(a, b): m, n len(a), len(b) # dp[i][j] 表示 a 前 i 个和 b 前 j 个的 LCS 长度 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而不是(m1)×(n1)二是下标写错导致越界。手写时我会在草稿边上标注下标从1开始对应字符下标i-1这个小习惯救过我至少两次。4.3 典型题实操从建模到伪代码拿0-1背包完整走一遍。题目给n件物品容量W每件有重量w和价值v求最大价值。第一步建模状态 dp[i][j] 表示前i件、容量j的最大价值。第二步写转移对第i件如果 j w[i]装不下dp[i][j] dp[i-1][j]否则可以装也可以不装取 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。第三步初始化dp[0][] 0dp[][0] 0。第四步填表顺序i从小到大j从小到大。第五步返回 dp[n][W]。再拿Dijkstra走一遍。它的数据结构我用两个数组dist记录源点到各点的当前最短距离visited记录是否已确定。流程是每次从visited为假的点里选dist最小的标记确定然后用它去松弛邻接点。注意Dijkstra不能处理负权边这是常考的概念点要能解释原因——因为它每次确定一个点后就不再更新负权边可能让已确定的点变得更好破坏了这个假设。最小生成树的Prim和Kruskal也要能写。Prim是不断加距离生成树最近的点适合稠密图Kruskal是按边权排