1. 把“算法设计与分析”这门课到底考什么先弄明白很多人一拿到复习资料就开始从第一页翻翻到分治就卡住翻到动态规划直接放弃——这种复习方式基本等于白给。算法设计与分析这门课跟数据结构不一样数据结构考的是“你会不会用”算法设计与分析考的是“你为什么这么用以及这么用到底花多少代价”。说白了它考的是三种能力把现实问题抽象成数学模型的能力、选出合适算法策略的能力、以及对算法效率做定量分析的能力。这三样缺一样期末卷子上就会露馅。我当年复习这门课的时候先做的第一件事不是背算法而是把整学期的PPT目录抄了一遍然后对着目录问自己四个问题这部分会出计算题吗会出证明题吗会出编程题吗还是只考个概念填空把每个知识点按这四类打标签之后复习的优先级瞬间就清楚了。算法设计与分析的期末考试本质上是一场“有限时间内拿分最大化”的博弈你得把时间投在那些一定会考、且你能拿稳的题型上。这份复习题整理的核心价值就是帮你把散落在教材、课件、作业里的考点重新串成一条线。它适合三类人第一类是平时没怎么听课、现在想靠突击及格的第二类是基础还行、想冲高分拿奖学金的第三类是要考研、把这门课当作专业课底子的。不管你是哪一类下面的内容都按“先建地图、再攻堡垒、最后排雷”的顺序来你可以按自己的进度跳着看但我建议至少把复杂度分析和动态规划这两块啃透因为它们是整张卷子的地基。提示复习算法课最忌讳“看懂会做”。看懂别人的解法只需要三分钟自己独立写出状态转移方程可能要三十分钟。复习时一定要合上答案自己推一遍。2. 复杂度分析整张卷子的地基先把它焊死2.1 渐进记号与常见复杂度量级复杂度分析是这门课的“普通话”不会它后面所有题你都只能写个大概。期末考试里最常考的是大O记号但你要清楚它只是上界还有大Ω下界和大Θ紧确界。举个生活化的例子你说“从家到公司最多花一小时”这是大O说“最少也要半小时”这是大Ω说“差不多就是四十分钟上下”这才是大Θ。考试里让你证明 f(n)Θ(g(n))你就要分别证上界和下界两步都不能少。常见量级从小到大排列必须背得滚瓜烂熟复杂度名称n1000时的量级感觉O(1)常数阶瞬间完成O(log n)对数阶约10次操作O(n)线性阶1000次操作O(n log n)线性对数阶约10000次O(n²)平方阶100万次O(2ⁿ)指数阶天文数字不可接受O(n!)阶乘阶比指数还恐怖这里有个坑要提醒大O记号里的常数系数和低阶项全部丢弃。3n²5n100 就是 O(n²)别手贱把5n留着。但反过来证明题里如果题目给了具体常数你得用定义去证不能直接“显然”。证的套路就是找一对常数 c 和 n₀使得当 n≥n₀ 时 f(n)≤c·g(n)。这个 n₀ 怎么找把不等式写出来解就行通常取个保守值比如 n₀1 或 n₀某个临界点。2.2 主定理递归式求解的万能钥匙分治算法的复杂度几乎都以递归式形式出现比如 T(n)2T(n/2)O(n)。这时候主定理就是你的救命稻草。主定理的形式是 T(n)aT(n/b)f(n)其中 a≥1、b1。关键是比较 f(n) 和 n^(log_b a) 这两个函数的增长速度如果 f(n) 增长得更慢也就是 f(n)O(n^(log_b a-ε))那 T(n)Θ(n^(log_b a))。如果两者同阶也就是 f(n)Θ(n^(log_b a))那 T(n)Θ(n^(log_b a)·log n)。如果 f(n) 增长得更快且满足正则条件那 T(n)Θ(f(n))。对着归并排序验证一下T(n)2T(n/2)O(n)a2b2n^(log_2 2)n和 f(n)n 同阶属于第二种情况所以 T(n)Θ(n log n)。这就对上了。二分查找 T(n)T(n/2)O(1)a1b2n^(log_2 1)n⁰1和 f(n)1 同阶第二种情况但 log n 次幂是 Θ(log n)所以是 O(log n)也对了。注意主定理不是万能的遇到 T(n)2T(n/2)n log n 这种“差一点点”的情况主定理直接用不了得用递归树或代入法。考试如果出这种多半是陷阱要么用递归树展开要么题目其实可以用其他方法。递归树法是我最推荐的手算方法因为它直观。把递归式一层层展开画成树每层的代价加起来最后求和。比如 T(n)2T(n/2)n第一层代价 n第二层两个 n/2 加起来还是 n一共 log n 层所以总代价 n log n。这个方法不怕记错公式画出来就一目了然。3. 四大算法设计策略逐个击破3.1 分治法把大问题切成小问题分治的三个步骤是分解、解决、合并。它的适用条件是子问题相互独立、且子问题和原问题结构相同。典型题目有归并排序、快速排序、二分查找、最大子数组和、最近点对问题。最大子数组和是期末卷上的常客。分治思路是把数组从中间劈开最大子数组要么全在左半边要么全在右半边要么横跨中点。前两种递归求解第三种从中间向两边扫描求最大和三者取最大。这个题最容易错的地方是“横跨中点”那一步的写法必须是向左连续累加取最大、向右连续累加取最大然后相加不能跳着选。我见过太多人在这里丢掉一半分。快速排序的分治要点在划分partition。考试如果让你手写 partition 过程记住选定基准后用双指针从两端向中间夹左边找比基准大的右边找比基准小的交换直到相遇。它的平均复杂度是 O(n log n)但最坏情况已经有序且每次选第一个元素做基准退化到 O(n²)。这也就是为什么工程实现里要随机选基准或者三数取中。3.2 贪心法每一步都选当前最优贪心的核心是局部最优能否推出全局最优这是它跟动态规划最大的区别。贪心不能回退所以用之前必须证明它的贪心选择性质。经典题目有活动安排、哈夫曼编码、最小生成树的 Prim 和 Kruskal、单源最短路径的 Dijkstra。活动安排问题的套路是按结束时间升序排序然后依次选不冲突的活动。为什么按结束时间排而不是开始时间因为结束越早留给后面的时间越多。这个证明考试可能让你写思路是用交换论证假设最优解里第一个活动不是结束最早的把它换成结束最早的那个不会让解变差所以存在一个包含贪心选择的最优解。哈夫曼编码是构造最优前缀码的贪心算法。步骤是每次取频率最小的两个节点合并新节点频率为两者之和重复直到只剩一个节点。考试经常让你画哈夫曼树并算带权路径长度 WPL。计算方法是每个叶子节点的频率乘以它的深度边数全部加起来。这里最容易错的是把深度数成节点数深度是从根到叶子的边数根节点深度为0。心得判断能不能用贪心先问自己“我能不能构造一个反例让局部最优变差”。如果能构造出来就不是贪心能解的得转动态规划。比如0-1背包问题贪心按单位价值排序会翻车而分数背包贪心就正确差别就在于能不能拆分物品。3.3 动态规划期末大题的主力军动态规划是这门课分量最重的部分没有之一。它的两大要素是最优子结构和重叠子问题。解题四步走定义状态、写状态转移方程、确定初始条件和边界、确定计算顺序自底向上填表或自顶向下记忆化。0-1背包是最经典的DP题。状态定义 dp[i][j] 表示前 i 个物品、容量为 j 时的最大价值。转移方程是不放第 i 个物品dp[i][j]dp[i-1][j]放第 i 个物品前提是 j≥w[i]dp[i][j]dp[i-1][j-w[i]]v[i]两者取最大。这个题考试常见变形是让你手填整个表格一定要画对行和列i 从1到nj 从0到W逐行填每一步都写清楚取的是哪种情况过程分比结果分还重要。最长公共子序列LCS也是高频题。dp[i][j] 表示字符串A前i个和字符串B前j个的LCS长度。当 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])。时间复杂度 O(mn)空间可以用滚动数组优化到 O(min(m,n))。考试如果问你如何回溯出具体的子序列就从右下角往左上走相等就记录并斜着走否则往数值大的方向走。def lcs(a, b): m, n len(a), len(b) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): 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稍微绕一点状态 dp[i][j] 表示从第 i 个矩阵乘到第 j 个矩阵的最小乘法次数转移是枚举分割点 kdp[i][j]min(dp[i][k]dp[k1][j]p[i-1]*p[k]*p[j])。这个题的难点在理解维度数组 p 的含义p[i-1] 是第 i 个矩阵的行数p[i] 是列数三个数相乘就是这次合并的代价。填表顺序是按区间长度从小到大因为长区间的解依赖短区间的解。3.4 回溯与分支限界暴力也要有章法回溯法本质是带剪枝的深度优先搜索走不通就回头。经典的N皇后、图的m着色、子集和、旅行商问题都能用。写回溯要注意三点解空间树的形状、约束函数剪掉不可行的分支、限界函数剪掉不可能更优的分支。以N皇后为例解空间是每行放一个皇后冲突判断是同一列、同一主对角线、同一副对角线。主对角线的特征是 row-col 相等副对角线是 rowcol 相等用两个布尔数组就能 O(1) 判冲突。这个技巧考试非常爱考记住它比每次循环判冲突快得多。分支限界跟回溯的区别在于搜索方式回溯是深度优先分支限界通常用广度优先或优先队列最小耗费优先。0-1背包可以用分支限界做每个节点算出上界用分数背包的贪心值作为松弛如果上界不如当前最优解就剪掉。考试里的分支限界题通常给一个小规模例子让你画搜索树关键是上界的计算和剪枝的时机画清楚了就稳。4. 高频算法专题考来考去就这些4.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)稳定否稳定性这个考点特别爱出。所谓稳定就是相等的元素排序后相对顺序不变。冒泡和插入稳定因为它们是相邻交换不会跨越相等元素选择排序不稳定因为它在交换时可能把前面的相等元素甩到后面去。考试如果问你“哪个排序适合对多关键字排序”答案就是稳定排序先按次关键字排再按主关键字排稳定性保证次关键字的结果不被破坏。堆排序的建堆过程是难点。从最后一个非叶子节点下标 n/2-10-indexed开始依次向下调整sift down。调整的过程是跟左右孩子中较大的那个比较如果比孩子小就交换然后继续往下。建堆的时间复杂度是 O(n)不是 O(n log n)这个结论很多人记反了。堆排序的完整过程是建大顶堆、把堆顶跟最后一个元素交换、堆大小减一、重新调整重复 n-1 次。4.2 图算法最短路径与最小生成树图算法在期末里的地位仅次于DP。最短路径两个算法必须分清楚适用场景Dijkstra 用于非负权图的单源最短路Bellman-Ford 能处理负权边但不能有负环Floyd 求所有点对最短路。Dijkstra 用优先队列优化后是 O((VE)log V)手算题里通常是给你一张图让你一步步标出距离。Dijkstra 的核心是“每次从未确定的点里选距离最小的确定下来然后用它松弛邻居”。手算时一定要画表格列出每个顶点的当前最短距离和是否已确定每选一个点就更新一次。这个表格过程分给得很大方别偷懒只写最终答案。最小生成树的 Prim 和 Kruskal 也是必考。Prim 从一个点出发每次选连接已选集合和未选集合的最小边适合稠密图Kruskal 把所有边排序每次选不构成环的最小边适合稀疏图。Kruskal 判环用并查集考试里可以用手动方式把已选的边连起来看会不会成环。两个算法的结果都是最小生成树但过程不同考试经常同时问两个你得分清楚。注意最小生成树针对的是连通无向图最短路径针对的是有向或无向图两者目标不同。别把 Prim 和 Dijkstra 搞混它们长得很像但一个求总权最小一个求单源距离最短。4.3 字符串匹配KMP 算法的 next 数组KMP 是期末里最容易考倒人的一个因为它那个 next 数组的定义就有好几种版本。主流教材如《算法导论》的变体用的是“最长公共前后缀长度”版本也有的用“前缀函数”或者“失配后跳转位置”。复习时一定要以你们老师课件上的定义为准因为不同定义算出来差一位。以最长公共前后缀版本为例对于模式串 Pnext[i] 表示 P[0..i] 的最长相等前后缀长度。手算方法是next[0]0或-1看定义然后逐个字符比较相等就加一不相等就回退到 next[前一个] 继续比。KMP 的匹配过程是主串指针 i 不回溯模式串指针 j 失配时跳到 next[j-1]。def build_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j-1] if p[i] p[j]: j 1 nxt[i] j return nxt考试里KMP的常见问法是给一个模式串求它的 next 数组或者给主串和模式串问匹配过程中指针怎么移动。前者是纯计算后者考理解。我当年的经验是next 数组一定要练到手算五六个不同模式串都不出错考试才敢下笔。这个没有捷径就是练。5. 期末题型拆解与实战套路5.1 计算题和证明题的得分技巧计算题通常是复杂度分析、递推式求解、DP填表、图算法手算、排序过程模拟这几类。这类题的特点是过程分占比极高哪怕最后结果算错只要你表格填了、公式写了、思路对了至少能拿七成分。所以考试时千万不要空着把你能想到的推导都写上去。复杂度计算的常见套路是先写出基本操作执行次数的求和式然后用求和公式算。比如双重循环for i in 1..n: for j in 1..i:总次数是 12...nn(n1)/2O(n²)。三重循环要注意内层跟外层的关系别傻乎乎地都乘成 n³。遇到for j in 1..n step 2这种步长不为1的次数是 n/2别算成 n。证明题主要有两类证明贪心选择性质交换论证、证明最优子结构反证法或归纳法。交换论证的模板是“假设最优解 OPT 中第一个选择不是贪心的选择 g我把 OPT 里的那个选择换成 g证明换完之后解不会变差所以存在包含 g 的最优解”。归纳法证最优子结构就是假设规模小于 n 时成立推出规模为 n 时也成立。这两种模板背下来遇到证明题往里套就行。5.2 编程题把伪代码写规范编程题一般让你写出算法的伪代码或者核心代码语言不限。评分看的是思路清晰、边界处理、复杂度合理。我建议用类似 Python 或 C 的伪代码写缩进清楚变量名有意义。几个加分细节写清楚输入输出、处理空输入和边界情况、在注释里标出时间空间复杂度。比如让你写快速排序规范写法是先写 partition再写 quicksort 主体最后说明平均 O(n log n)、最坏 O(n²)。如果题目要求原地排序就强调不用额外数组。如果要求稳定就说明快排不稳定需要换归并。这些细节能体现你真的理解算法而不是背代码。DP编程题的常见坑是数组下标越界和初始化错误。记住凡是用到 dp[i-1] 或 dp[i-1][j-w] 的地方i 和 j 都要从1开始循环第0行和第0列作为初始条件单独填。空间优化题滚动数组要注意内层循环的遍历方向0-1背包必须从大到小遍历容量完全背包从小到大这个方向搞反了结果就全错。心得写DP代码前先在纸上把状态表和初始条件列出来确认无误再动手。我见过太多人在考场上直接开写写到一半发现状态定义错了整道题推倒重来时间全浪费了。6. 常见踩坑清单与考场时间分配6.1 那些年我们一起踩过的坑复习和考试里的坑其实高度可预测我整理成一张速查表考前扫一遍坑表现正确做法主定理乱用遇到 f(n) 不是多项式形式还硬套先看是否满足三种情况的前提不满足用递归树贪心当DP用0-1背包按单位价值排序贪心不能解0-1背包必须DPDP遍历方向错0-1背包容量从小到大0-1背包从大到小完全背包从小到大next数组版本混用了两种定义对不上答案以自己老师课件定义为准稳定性判断错以为选择排序稳定选择排序不稳定相邻交换的才稳定复杂度丢项算出来O(n²)写成O(n²n)渐进记号下只保留最高阶项递归式边界漏忘写T(1)O(1)递归式必须带边界条件才完整还有一个隐形的大坑是时间分配。期末卷子通常计算题多、编程题少但编程题分值高。我的建议是拿到卷子先花两分钟通览一遍把最有把握的题先做了把需要长时间推导的DP题留到后面。计算题控制在每题8到10分钟编程题每题15到20分钟最后留15分钟检查。绝对不要在一道卡住的题上死磕超过5分钟先跳过回头再想。6.2 考前最后三天的冲刺策略如果你现在离考试只剩三天别再从头看书了按这个顺序冲第一天把复杂度分析和四大策略的模板过一遍每个策略手推两道典型题第二天专攻DP把0-1背包、LCS、矩阵链、最长递增子序列这四个题的表格各填三遍练到肌肉记忆第三天做两套往年真题掐时间模拟然后对答案找漏洞。对于基础特别薄弱的同学优先保底分的题型是复杂度排序、排序算法对比表、Dijkstra手算、next数组、简单的DP填表。这几个题型几乎是送分题只要复习到位就能稳稳拿到。难度高一点的证明题和分支限界如果时间不够可以战略性放弃把精力投在能拿稳的地方。我个人在实际复习中的体会是算法这门课最有效的复习方式就是“手写”。看懂一千遍不如自己默写一遍算法流程。尤其是DP和KMP光看不练一定会翻车。我当年就是靠着把每个高频算法在草稿纸上默写了不下十遍最后考场上看到题目基本是条件反射。复习资料再详细也只是地图真正走路的人还得是你自己把这份资料当作索引配合你们老师的课件和作业题一起用效果会翻倍。