期末复习这件事最怕的就是翻开书感觉哪里都是重点合上书又觉得哪里都没记住。《算法设计与分析》尤其如此它不像文科科目可以靠背诵解决问题也不像纯数学课只靠推导就能拿分。这门课考察的是你用计算机思维拆解问题、设计策略、证明正确性的综合能力光靠考前突击刷题往往事倍功半。作为带过好几轮算法课程的“过来人”我见过太多同学在期末复习时踩进同一个坑把大量时间花在反复看教材定义上却忽略了真正能拉开分差的经典例题与关键模型。这篇复习指南就是冲着这个痛点来的。我不是要把教材目录给你复述一遍而是把《算法设计与分析》期末试卷里最常出现的考点、最典型的解题套路、最容易丢分的细节全部拆开揉碎讲清楚。无论你是刚开始复习还是一轮过完想查漏补缺这篇文章都能当成你的“冲刺清单”来用。先提醒一句算法这门课看十遍例题不如亲手做一遍。所以下面每一章我都会把“知识点是什么”和“考场上怎么做”放在一起讲你最好拿纸笔跟着推一遍。1. 考前先做减法把时间花在最容易拿分的地方1.1 期末考卷里最常见的考点权重分布《算法设计与分析》这门课覆盖内容看起来庞杂但落到期末试卷上出题范围其实是高度集中的。我根据这几年多个学校、多个版本的期末考题统计不严谨但很有代表性的权重结构大概是下面这个样子。分数占比最高的永远是动态规划第二是分治法这两块加起来能占35分到40分按100分满分估算。紧接着是贪心算法与回溯法通常以证明题或算法设计题出现。图算法最小生成树、最短路径与排序/选择算法属于必考基础题一般放在中段位置难度不会太大。剩下的分数会分散在算法复杂度分析、递归方程求解、一些经典算法如KMP、堆排序、STL相关的基础题上。结合热搜词里频繁出现的“算法设计与分析”“数据结构与算法”“计算机算法设计与分析”这些关键词可以判断这门课的核心逻辑线是“设计策略 复杂度分析”而不是简单的“背诵算法步骤”。期末试卷上很多题目看着是让你“写出某算法步骤”实际上打分点里有一半落在“你如何解释该算法为什么正确、复杂度为什么是这个数量级”。1.2 明确最优复习顺序从基础复杂度爬到核心策略前期复习别一上来就啃动态规划。建议先搞定复杂度分析方法尤其是递归方程的求解方法因为在考试中不管考哪个算法你都需要写出它的时间复杂度和空间复杂度。这个东西不会单独成一个章节考察但每一个大题的最后一步都暗暗扣着它。第二个复习梯队是分治法和排序算法。这两个知识点是“算法设计与分析”的根基理解了分治思想后面学动态规划和回溯法的时候会有明显的顺滑感。第三个梯队是动态规划与贪心算法这两个都是期末大题的常客需要你熟练掌握类型的判断和状态转移方程的构造。最后再看回溯法与分支限界法这类题目现在越来越喜欢结合具体问题如N皇后、图着色来出考察的是你在约束条件下的搜索策略设计能力。这么排的意义很简单复杂度分析是贯穿全程的“弹药”分治是基础思维模板动态规划和贪心是拉分核心回溯和分支限界是锦上添花。先把前两项吃透再学后面的难点效率比漫无目的地按目录复习高得多。2. 复杂度分析所有算法题的“隐藏必考题”2.1 时间复杂度计算的三个层级期末复习复杂度不要只背“O(n2)”比“O(nlogn)”慢。试卷上的复杂度题一般以三种形态出现。第一形态是分析循环嵌套。单层循环是O(n)双层循环是O(n2)三层循环是O(n3)。但严谨的分析需要看循环变量的变化规律比如for(int i1;in;i*2)这种循环虽然形式上是一层实际复杂度是O(logn)。具体计算方法是看循环变量到终止条件需要执行多少次i从1翻倍到n一共需要log2(n)次。第二形态是分析递归算法的复杂度。经典例子是计算斐波那契数列第n项的朴素递归写成T(n)T(n-1)T(n-2)O(1)直接展开得到的是指数级复杂度O(2^n)。如果你在卷子上只写“指数级”通常只能拿一半分最好能写出递归树推导过程让阅卷老师看到你知道为什么是指数级。第三形态是根据代码逻辑构造复杂度下界。比如比较排序的最坏时间复杂度下界是Ω(nlogn)这个结论经常在选择题或判断题里出现。你需要理解它不是指某个具体算法而是基于决策树模型的通用结论。2.2 递归方程求解主定理法必须吃透递归方程求解是期末高挂科率的头号杀手。推导递归树的方法即便你理解了实际操作中也容易出错。我的建议是直接掌握主定理方法Master Theorem只要形式对得上几秒钟就能算出结果。主定理核心内容并不复杂。对于形如T(n)aT(n/b)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 * logn)。情形三如果f(n)Ω(n^(log_b_a ε))且af(n/b)≤cf(n)成立则T(n)Θ(f(n))。考试常考的三个例子归并排序的T(n)2T(n/2)O(n)属于情形二结果是O(nlogn)二分查找的T(n)T(n/2)O(1)属于情形二结果是O(logn)而某些不均衡分治如T(n)T(n-1)O(1)则不能直接套主定理b的取值为1不能应用主定理这时用递归树或代换法更快捷。2.3 空间复杂度别在最后一步丢分空间复杂度是很多同学在期末考试时最容易忽视的内容。举例来说归并排序的空间复杂度不是O(1)因为在合并过程中需要临时数组它的额外空间是O(n)。快排的空间复杂度严格说是O(logn)到O(n)不等因为是由递归栈深度决定的。如果卷子上要求“分析空间复杂度”你只写了O(1)就会被扣分。3. 分治法从“递归三要素”到高频考题3.1 分治算法必须满足的三个条件期末考分治时题目一般不给现成算法让你分析而是给你一个具体问题让你“请设计一个O(nlogn)的算法解决”。这种题型拼的是你对分治框架的理解。一个合法的分治算法需要满足三个条件原问题能拆分成规模更小、结构相同的子问题子问题的解能够合并成原问题的解拆分与合并的计算代价足够小。如果子问题不能独立求解或者合并过程复杂度太高分治法就不适用。以经典题“最大子段和”为例来说明分治的拆分逻辑。给定一个整数数组找和最大的连续子段子数组。扫描一遍的DP解法复杂度是O(n)非常好用。但如果你用分治法来解思路是把数组从中间分成两半那么最大子段和要么完全在左半边要么完全在右半边要么跨越中间位置。跨中间的情况要从中间出发向左、向右分别找最大后缀和与最大前缀和两者相加即可合并复杂度记为O(n)。于是T(n)2T(n/2)O(n)应用主定理得到O(nlogn)。考场上如果要求用分治法解这道题你既要写拆分逻辑也要写合并递归方程和主定理推导两步缺一不可。3.2 经典分治题目快查从二分查找到大整数乘法期末分治部分出现的最大概率题目是二分查找、归并排序、快速排序、最近点对和棋盘覆盖。二分查找虽然简单但它能引出“分治策略应用前提数据有序”这一考点。归并排序的合并过程是算法细节考试可能会让你补全代码或写合并步骤。快速排序则最爱考最坏情况分析当每次选取的枢纽都是最大或最小元素时划分极不均衡递归方程退化为T(n-1)O(n)复杂度为O(n2)。这题的坑在于很多同学知道快排是O(nlogn)就直接套结论忽略了它最坏情况是O(n2)导致分尽失。大整数乘法是分治中的进阶题期末偶尔会作为大题考察。将两个n位大整数一分为二朴素分治需要4次递归乘法复杂度是O(n2)不优于普通竖式乘法。关键优化在于把递归次数从4次减到3次具体做法是计算a*c、b*d与(ab)*(cd)通过(ab)*(cd)-a*c-b*d得到中间交叉项从而得到T(n)3T(n/2)O(n)主定理算出O(n^log_2_3)≈O(n^1.585)。这道题当年考察时很多同学能写出拆分方案但不会用三个乘法代替四个乘法。这个优化点是标准的得分点你复习时一定要专门记下来。3.3 写分治法代码时的递归基与边界处理很多同学并不是不懂分治思想而是写递归代码时总是忽略边界条件。期末如果要求“写出分治算法的伪代码”请记住一个原则递归基必须覆盖最小可能输入。以二分查找为例递归基就是lowhigh时返回-1以及mid位置元素恰好等于target时返回mid。缺少lowhigh的判断程序会无限递归栈溢出。快排的递归基是区间长度小于等于1时直接返回。归并排序的递归基是区间长度为1时无需合并。这些细节在笔试中很划算写清楚能有效拿步骤分因为阅卷老师一眼就能看出你是否真的掌握了递归的边界设计。4. 动态规划期末大题的最强“得分担当”4.1 从暴力递归到DP表的递推思路动态规划这门课的核心逻辑不难难在拿到题目时如何从问题的描述中识别出“能DP”的信号并且准确地定义状态和写出状态转移方程。期末复习如果只有半天时间我建议你死磕下面的方法论而不是无限刷题。第一步判断是否适合使用DP。适合动态规划的问题有两个关键特征最优子结构和重叠子问题。最优子结构的意思是问题的最优解可以由子问题的最优解组合而成。重叠子问题的意思是如果把暴力递归展开不同的递归分支会反复计算同一个子问题。这两个条件同时成立时就可以用DP表或记忆化搜索进行优化。第二步定义状态。这一步是区分“看懂答案”和“自己能做出来”的分水岭。状态定义没有一个固定的万能公式常见策略是问自己改到最后一步时需要记录的信息是什么以0-1背包为例我需要知道当前考虑到了第几个物品背包剩余容量是多少所以状态定义为dp[i][j]表示前i个物品放入容量为j的背包能获得的最大价值。以最长公共子序列为例我需要知道字符串A处理到哪个位置、B处理到哪个位置所以状态定义为dp[i][j]表示A[1..i]和B[1..j]的最长公共子序列长度。第三步写状态转移方程和初始化。这一步考察你是不是真的懂“最后一步”发生了什么。以最长公共子序列为例如果A[i]等于B[j]那么dp[i][j]dp[i-1][j-1]1如果不相等则在dp[i-1][j]与dp[i][j-1]中取较大值。这个转移方程的推导逻辑本质上是分类讨论讨论的是最后一个字符是否相同。4.2 必刷经典模型矩阵连乘、LCS、0-1背包矩阵连乘矩阵链乘法是动态规划大题里最经典的题目之一。题目描述是给定一系列矩阵A1, A2, ..., An要求完全加括号的方式使得标量乘法次数最少。状态定义dp[i][j]表示计算Ai到Aj的最小代价。转移方程的核心是枚举分隔点kdp[i][j]min(dp[i][k]dp[k1][j]p[i-1]*p[k]*p[j])其中p是各矩阵的维度链。这道题考察的难点是你能否写出循环顺序区间长度从小到大而不是起点从小到大的盲目遍历。三重循环中外层枚举区间长度内层枚举起点最内层枚举分隔点复杂度O(n3)。如果实现顺序写错就直接拿不到结果卷面上通常也会有需要填表的过程检查你是否理解填表方向。0-1背包问题几乎每张试卷都会以某种形式出现要么是直接考要么是套了一层壳。最常见的是要求写出动态规划表、回溯找到选择的物品集合。如果你在卷子上只写出了dp数组的计算没有写回溯求具体方案的步骤通常会被扣掉后面一小半分数。回溯求方案的做法是从dp[n][capacity]往前倒推如果dp[i][j]由dp[i-1][j]转变而来说明第i个物品没选如果dp[i][j]由dp[i-1][j-w[i]]v[i]转变而来说明第i个物品被选中。注意这种回溯方法只适用于“每个物品选或不选”的0-1背包完全背包不能用同样的逻辑直接判断。4.3 滚动数组优化卷面上能加分的优化说明动态规划大题有些老师会在题目最后设置一问“请说明如何降低空间复杂度”。以0-1背包为例朴素二维dp状态的空间复杂度是O(n*capacity)但状态转移只依赖于i-1行所以可以用一维数组倒序遍历容量将空间降到O(capacity)。为什么必须倒序遍历因为正序遍历会覆盖掉dp[i-1][j-w[i]]的旧值导致一个物品被重复使用那就从0-1背包退化成完全背包了。这个原因考场上一定要写清楚这比单纯背代码有价值得多。4.4 题型识别技巧什么题会伪装成DP期末考试不会直白地说“请用动态规划解决XX”而是给出实际问题让你自行判断。最常见的是最长递增子序列、编辑距离字符串转换的最少操作次数、数字三角形最优路径、硬币找零最少硬币数量。判断方法如果问题是“求最优值、求方案数、求最少操作/最大收益”并且满足子问题重叠十有八九是DP。反过来说如果问题是“求具体方案的内容、求完整的路径”那么DP往往只完成了一部分追击策则需要用回溯或贪心。这里有一个需要留意的点硬币找零这道题如果问的是“最少需要多少枚硬币凑出amount”这确实是动态规划但如果问的是“能否用贪心得到最优解”则不再是无脑DP了。有些硬币面值下贪心是对的比如人民币面值有些面值下贪心是错的比如硬币面值为1、5、11时凑15贪心会选111111共5枚而最优解是555共3枚。期末复习时记住这个经典反例对理解贪心和DP的区别非常有帮助。5. 贪心算法会证明比会设计更重要5.1 贪心策略的正确性证明套路期末考试贪心算法的特点是代码往往几行就能写完难的是你是否说清楚“为什么贪心解一定是最优的”。如果题目只要求写算法思路和复杂度你可能还觉得简单。一旦要求“证明该贪心策略是最优的”一大批学生就会卡住。通用的证明框架是贪心交换法与最优子结构论证。贪心交换法假设存在一个最优解与贪心解不同找到其中最靠前的不同决策位置通过交换将该最优解调整为贪心解的形式且总代价不增加从而说明贪心解也是最优解。最优子结构论证证明贪心选择之后剩余问题仍然是同类型的子问题并且子问题的最优解可以原封不动地拼接到贪心选择之后。以活动选择问题为例经典规则是按活动结束时间从早到晚排序优先pick结束最早的可行活动。证明思路是如果存在一个最优解不用结束最早的活动a1那么该最优解中第一个被选的活动ak的结束时间一定不早于a1的结束时间因此在最优解中把ak替换为a1后续活动依然可以按照原安排进行总活动数量不变或更优于是贪心解不差于任意最优解。5.2 用最小生成树和Dijkstra理解“贪心为什么成立”图算法中最小生成树是贪心策略的经典应用场景。Prim算法从任意顶点出发每次选择连接当前已选集合与未选集合的最小权边。Kruskal算法则按权值从小到大遍历所有边若边的两端不在同一连通分量中则合并。期末考这两种算法时除了要求手算模拟过程还经常让你比较它们的适用场景Prim适合稠密图且无向图Kruskal适合稀疏图且无向图。Prim的复杂度在有邻接矩阵时是O(n2)用优先队列可优化到O((nm)logn)。Kruskal的复杂度主要取决于排序边为O(mlogm)。Dijkstra单源最短路径算法也是贪心策略的运用。它的贪心体现在“每次选择当前距离源点最近且未访问的节点并将其标记为已确定”然后松弛其邻居。正确性依赖于只要图中所有边权非负当前最近的未访问节点的距离一定已经是最短距离无法再被其他路径优化。期末考题常在这里设置陷阱——如果把Dijkstra用在含负权边的图上就会得到错误结果因为存在某一节点被标记访问后通过负权边绕路过来的更短路径无法再被考虑。这个点如果出现在“判断正误”或者“描述该算法的局限”里是直接送分题。5.3 贪心和动态规划的分界点一道题让你彻底清醒“给定面额为1、5、11要凑15元用最少硬币数。”由这个问题可以引出贪心失效的例子。但真正有价值的做法是用同一道题对比DP和贪心两个角度。贪心策略“优先用最大面值”会得到111111共5枚而DP求解会找到555共3枚。这说明贪心算法不能保证全局最优而动态规划枚举了所有可能的状态一定找到最优解。期末考试经常以这种“对比分析”的方式出题要求你分别用贪心和DP给方案并解释为什么结果不同。你要答的关键是贪心不具备回溯能力一旦做了局部最优选择就无法回头DP通过表记录所有子问题答案保证全局最优。6. 回溯法与分支限界法搜索策略的考场实战6.1 解空间树、约束函数、限界函数的写法回溯法期末考点主要集中在画出解空间树、设计约束函数、计算搜索过程的剪枝。经典题N皇后问题解空间是一棵n叉树深度为n第i层代表第i行皇后放在哪一列。约束函数是检查当前列是否与前面所有行在同一列或同一对角线上。回溯过程的伪代码核心是对每一层尝试所有可选分支满足约束则继续递归否则立即剪枝。N皇后这道题需要一个关键细节判断对角线冲突时用“行列号的差值相等”来判断左对角线用“行列号的和相等”来判断右对角线。如果能在卷面上写出这个判定条件阅卷老师能一眼看出你是真的理解棋盘搜索而不是背模板。图着色问题同样重要。给定无向图和k种颜色判断是否存在合法着色方案。回溯搜索顺序通常选顶点顺序展开约束函数是“当前顶点颜色不能与任何已着色邻居相同”。这道题在期末考试中的进阶考法是让你优化选择顺序比如优先选择度最大的顶点进行着色这个策略能显著减少搜索分支。我建议你在复习时把“优先选择约束最紧的分支”这一思想写进解题步骤这会被视为具备工程直觉的加分项。6.2 分支限界法与回溯法的区别分支限界法常和回溯法放到同一道题中比较。回溯法是深度优先策略核心目标是找到所有可行解或最优解效率依赖剪枝函数。分支限界法是广度优先或以最小耗费优先通常使用优先队列实现的策略它在搜索过程中维护当前代价限界bound一旦某节点的下界已经当前超过已找到的可行解的上界就直接剪掉该分支。常见于旅行商问题、0-1背包的优化等。期末如果要求“用分支限界法解决0-1背包”你要写清楚的是如何计算节点的价值上界。常用上界是当前价值加上剩余物品的“按单位重量价值排序后取部分物品”得到的分数背包最优值。这个上界利用的是0-1背包的最优值不会超过同样物品条件下完全背包的最优值。写清楚这一步分数基本上不会差。6.3 规模不大时回溯法就是“笨但正确”的选择回溯法的时间复杂度往往是指数级所以在期末考试中通常只要求你画出搜索树的前几层或者写出具体实例的完整搜索步骤。但这门课的现实意义在于当问题规模可控时回溯法是最容易实现、最不容易出错、甚至可以并发加速的精确求解方案。比如期末考题“子集和问题给定集合{2,5,8,13}问是否存在和为15的子集”用回溯法只需要展开二叉树搜索写起来非常快。要注意的是从根到叶子结点的状态流转中剪枝条件不仅包括“当前和是否已经超过目标”也包括“当前和加上剩余元素是否已经无法达到目标”。这个逻辑直接对应了回溯法最常见的优化思路。7. 排序与选择算法分值不大但必须全拿7.1 常见排序算法的复杂度、稳定性一页速查排序算法在《算法设计与分析》期末试卷中单独出大题的频率不高但在选择、填空和判断里出现的概率接近100%。你需要记住这些结论。快速排序平均与最优时间复杂度O(nlogn)最坏O(n2)不稳定归并排序所有情况O(nlogn)稳定空间复杂度O(n)堆排序所有情况O(nlogn)不稳定原地排序空间O(1)插入排序O(n2)平均O(n2)最好O(n)稳定适合近排序数组冒泡排序O(n2)稳定最好O(n)选择排序O(n2)不稳定空间O(1)。热搜词里反复出现“冒泡排序算法c”“排序算法”“堆排序算法”说明这是初学者最容易花时间又拿不到效果的板块。其实期末复习排序时不需要把每种排序都手写一遍重点是能用语言描述算法过程写上复杂度结论并在给定序列上手算1-2趟排序结果。比如快排第一趟结束后枢轴坐在哪个位置堆排序建堆后的堆数组长什么样这些是判卷时最爱做“采分点”的地方。7.2 手算排序过程最容易踩的坑手算快排第一趟时最常见的错误是忘记“每次递归时基准值位置左边的元素都小于等于基准值右边都大于等于基准值”这个核心要求。很多同学只做了一次左右交换就停了其实应该继续递归处理左右两侧。对堆排序手算常见错误是建堆后最后的堆顶元素与堆尾元素交换位置后你还需要重新调整堆结构而不是直接进入下一轮。归并排序的手算需要注意合并过程中临时数组的使用顺序要在纸上真实模拟“两个有序数组合并谁小先放谁”。如果你复习时间紧张建议手算至少3种快排第一趟、堆排序建堆过程、归并排序完整过程的1-2轮。这能帮助你从“懂概念”升级为“能得分”。7.3 冒泡排序复杂度优化最好的优化也得是O(n)有些试卷会在排序算法部分设置一道“设计优化”或“补全代码”的题目。典型的是给冒泡排序加上“本轮是否发生交换”标志位如果没有发生交换提前终止。这个标志位优化看起来很聪明但它最坏情况仍然是O(n2)最好情况才能达到O(n)。不要一看到优化就写O(nlogn)这是考场上常见的失分原因。这要求审题时注意原题给的算法是什么。这里不需要写代码只需在描述算法步骤时说明“当一轮扫描中没有任何元素交换说明序列已经有序可以提前退出”。8. 经典算法补充KMP、堆、二分与STL相关细节8.1 KMP算法到底在考什么KMP是《数据结构》与《算法设计与分析》交叉覆盖的内容期末偶尔会在填空或简答题中出现。关键是理解next数组或前缀函数的意义它表示当当前字符失配后模式串应该跳回到哪个位置继续匹配。这样可以保证文本串指针不回退从而把朴素匹配的O(n*m)复杂度优化到O(nm)。复习KMP时要做三件事会用前缀函数计算next数组手算一个模式串的next数组并标注能解释为什么KMP正确性依赖于“已匹配前缀的后缀与前缀相同”这一性质。如果你没有太多时间深入学习在卷子上遇到KMP题时即使不要求写出完整代码也请务必写出时间复杂度O(nm)和“主串指针不回退”这两个关键点。8.2 二分查找的变体与边界条件二分算法在热搜词中出现了“二分算法”“二分查找算法”说明同学们搜索量很大。期末复习二分时常见的失分点在于右边界取值和循环不变式不清楚。我建议采用一种健壮写法左闭右闭区间int l0, rn-1; while(lr) { int midl(r-l)/2; if(nums[mid]target) return mid; else if(nums[mid]target) lmid1; else rmid-1; }。注意mid计算使用l(r-l)/2来防止整数溢出这个细节即使写伪代码也建议体现出来。二分查找常考的变体还有查找第一个大于等于目标值的位置lower_bound、查找第一个大于目标值的位置upper_bound。这两个函数在C的STL里也是期末选择题的热门关键词。如果你能在SPL上写伪代码时要特别注意是左闭右开还是左闭右闭统一使用一种区间表示可以避免考场手忙脚乱。8.3 STL与高级数据结构的基础考点部分版本《算法设计与分析》期末试题会考察标准库中与算法密切相关的内容。热搜词中多次出现C相关词比如“冒泡排序算法c”。虽然这门课一般不直接考STL源码但可能会要求在算法题里说明“用优先队列实现堆排序的过程”或“用map实现计数”。建议复习时把priority_queue、sort、unique、lower_bound/upper_bound、next_permutation这几个常见函数的时间复杂度记一下。sort用的是快排与插入排序混合算法IntroSort平均与最坏均为O(nlogn)next_permutation按字典序生成下一个排列复杂度O(n)。这些零碎知识点往往就是选择题和填空题的快速送分点。9. 考试答题模板与常见失分点复盘9.1 算法设计大题的“标准答案姿势”期末算法设计大题评分通常按“思想、步骤、伪代码、正确性论证、复杂度分析”五项给分。哪怕你一时间想不出完美解法也千万不要只写一句话“这题可以用DP做”。我建议你按下面的模板组织答案。算法思想写一两句话即可说明使用了什么设计策略分治/DP/贪心/回溯。算法步骤分条列出每次操作的具体含义要写清楚。伪代码使用缩进与箭头符号主要分支必须写完整。正确性论证不要求严格归纳法证明但至少要说明为什么该策略能够保证可行性或最优性比如利用最优子结构、贪心选择性质等。复杂度分析先写时间再写空间要体现递推式的来源。完整的思路能让你即使最终答案错了也能靠前面的思想和步骤拿到大量步骤分。9.2 期末最容易丢分的5个细节第一个细节是复杂度符号混淆。O(nlogn)和O(n log n)本身没区别但有人会把O(n2)写成O(n^2)卷面上问题不大更大的是把O(logn)和O(nlogn)搞混这会在分析堆排序时造成致命错误。第二个细节是递归基错误。写分治或DP递归时漏掉n0或n1的边界会导致“递归不终止”或“数组越界”。第三个细节是DP初始化错误。0-1背包的dp[0][j]0和dp[i][0]0看起来简单但转移时下标从1开始遍历容易在写伪代码时忽略物品重量为0的情况。第四个细节是贪心证明缺位。题目要求证明贪心正确性时很多学生只写了“贪心选择明显最优”这一句话在阅卷里基本拿不到分。必须提及交换论证或剪支证明。第五个细节是忽略非法输入或输入规模极小的情形。考试中的算法设计题要求在空数组或只有一个元素的输入下也能成立。写分治算法时一定要明确递归基的返回条件写DP时循环边界不能越界。9.3 如何利用近三年期末真题快速自测真题不是让你随便翻翻答案。我推荐一个“三遍自测法”。第一遍不限时通读整套试卷把不会的题目标记出来对照答案搞懂思路。第二遍限时90分钟模拟正式考试训练做题节奏。第三遍只做错题和不确定的题目并在每道题旁边写出该题对应的核心知识点和解题套路。经过这三遍你基本能覆盖这门课80%以上考点。关于真题来源很多学校会把往年试卷挂在教务处系统或学院资料库里或者教研室开放给老师做教学参考。如果你能找到上一届学长学姐的回忆版哪怕不够完整也很有价值。重点不在于卷面整洁而在于比照回忆版题目反推“出题老师偏好哪个章节、哪个题型”这一点比你刷十道“你以为的重点”更高效。10. 考前24小时的冲刺清单最后一天不要再去啃那些你一直没搞懂的高难度题目。这个时候最理性的做法是把复杂度分析方法、DP的状态转移模式、贪心的证明框架、回溯的剪枝条件快速过一遍然后动手默写几道典型题的伪代码。比如归并排序的merge流程、LCS的转移方程、0-1背包的dp表更新规则、N皇后的回溯递归函数。这些重者已经写在肌肉记忆里的内容才是你上考场最稳定的拿分项。我强烈建议你在考前一天的晚上用一张A4纸做“记忆卡片”正面写分治、动态规划、贪心、回溯四种策略的适用条件与典型题目反面写排序算法复杂度表与主定理三条情形。考前90分钟只看这张纸。当年我考试的时候就靠这张纸在进考场前稳住了心态。另外考前一定不要通宵。算法分析的考试对逻辑清晰度要求极高熬夜后的思维迟缓会让你在状态转移方程和边界判断上犯平时根本不会犯的低级错误。保持7小时以上睡眠宁可少刷一套题也不要让大脑在考场上处于混沌状态。这些看起来与课本无关的细节实际上对你的分数影响极大。还有一个小技巧分享给大家遇到一道完全没思路的大题时先试着写几个最基础的情况比如n1、n2时答案是什么。很多时候把这些小规模实例的答案列出来你就能反推出来状态转移规律或分治拆分方式。我在期末复习和实际考场上都用过这个方法虽然不能保证每次都灵但它至少能帮你从“无从下笔”变成“有内容可写”而只要能写出正确的小规模结果就能拿到不少步骤分。希望这篇复习指南能在冲刺阶段帮到你记住算法设计与分析这门课考察的是思维而非记忆多画图、多假设、多验证你一定能过。