1. 这门课的复习框架先看清考试到底在考什么算法设计与分析这门课我当年复习的时候也是一头雾水。教材动辄四五百页从分治到动态规划从贪心到回溯每一章好像都能出题但真要说清楚期末到底考什么很多同学反而支支吾吾。其实这门课的考试题型非常固定基本就是选择题、简答题、证明题极少数学校会加一道编程题或者算法设计题。选择题考的是知识覆盖面简答题考的是概念理解和对比分析证明题则直接检验你能不能把一个算法的正确性、复杂度边界讲明白。先把整门课的核心知识模块在脑子里搭一个框架比一上来就刷题重要得多。我建议把所有内容归成四大块第一块是算法分析基础包括渐近记号、复杂度计算、递推关系求解这部分是选择题和证明题的常客第二块是经典算法设计策略也就是分治、动态规划、贪心、回溯、分支限界这五类策略各自有典型题目和适用场景简答题最爱在这里做对比第三块是图算法包括最小生成树、最短路径、拓扑排序、最大流等选择题喜欢在这里挖坑第四块是复杂度理论和难解性问题比如P、NP、NPC这些概念简答题几乎每年必考。我见过很多同学复习时喜欢按章节从头到尾刷结果刷到第八章就忘了第一章。更好的方式是按题型反过来推先把历年真题里选择题涉及的知识点画出来你会发现高频考点就集中在主定理、排序稳定性、图算法的复杂度这几个地方然后再集中精力攻克证明题的几种通用套路。这种“考点驱动的复习法”比“教材驱动的复习法”效率高得多尤其是期末周时间紧张的时候。复习顺序上我个人强烈建议先把证明题的套路搞定。为什么因为证明题是这门课区分度最大的题型也是拿分最难的地方但它恰恰是最有规律可循的——递推求解、正确性证明、复杂度下界翻来覆去就那么几招。把证明题的框架打通之后再去看选择题和简答题你会觉得那些概念题基本是降维打击因为选择题和简答题本质上考验的是你对同一套逻辑的掌握程度只是输出形式不同而已。还有一个容易被忽略的要点一定要搞清楚自己学校用的教材是哪一版以及老师上课的课件和作业题覆盖了哪些范围。不同学校的算法课内容差异不小有的偏重理论证明有的偏重代码实践有的则重点讲机器学习场景下的算法设计比如热词里那个“基于机器学习的音乐风格分类算法设计与实现”。如果老师上课重点讲过某个方向的选题期末考大概率也会往那个方向倾斜。2. 选择题高频考点与真题思路拆解2.1 复杂度计算与渐近记号选择题的送分题与陷阱题选择题里最基础也最常考的就是复杂度计算。给你一段代码或者一个递推式让你判断时间复杂度是O(nlogn)还是O(n^2)这类题其实是送分题但每年都有人错。问题大多出在没搞清楚渐近记号的区别上。O记号表示上界Ω记号表示下界Θ记号表示紧确界。选择题最喜欢在这里做文章比如问一个算法的平均复杂度是O(n^2)但最坏情况是O(n^2)还是Θ(n^2)很多同学在这类表述问题上翻车。记住O只说明不会超过某个量级至于到底是不是这个量级要结合具体代码逻辑来判断。如果题目明确说“最坏情况下”通常用Θ或者直接说O(n^2)也不算错但严谨的题目会区分平均、最好、最坏三种情况。循环嵌套的复杂度判断也是个高频考点。两层循环嵌套并不一定就是O(n^2)还得看内层循环的步长和终止条件。比如for(i1;in;i*2)这种循环执行次数是logn而不是n这就是经典的O(nlogn)题目素材。我建议遇到循环嵌套类选择题时不要用眼睛凭感觉老老实实在草稿纸上写几项看看循环变量增长规律几秒钟就能判断出来比瞪眼猜可靠得多。2.2 排序算法对比必考但容易混淆的知识点排序算法这块选择题的出题角度特别集中时间复杂度、稳定性、最好最坏情况对比、原地排序与否。我当年考试的时候光排序相关的选择题就出了三四道。先说一下稳定性的概念和记忆方法。稳定排序意味着相等元素的相对顺序在排序前后保持不变。常见的稳定排序有插入排序、冒泡排序、归并排序、基数排序不稳定的有选择排序、希尔排序、快速排序、堆排序。记忆窍门是快速排序在划分时可能把相等元素交换到两边所以不稳定堆排序在堆调整时无法保证相等元素的相对位置选择排序每次选最小的和当前位置交换时可能破坏稳定性这些理解清楚了就比死记硬背强。复杂度这块堆排序和归并排序的复杂度都是O(nlogn)但堆排序空间复杂度是O(1)归并排序需要O(n)的额外空间快速排序平均O(nlogn)但最坏O(n^2)。选择题经常给一个应用场景让你选排序算法比如内存有限且需要稳定排序这时候最优解就是归并排序的变体如果内存极紧张就得牺牲稳定性选堆排序。这些都是典型的综合考察方式。2.3 图算法与经典数据结构常被忽略的丢分区图算法相关内容是选择题丢分的重灾区因为很多学校上课时图算法讲得很赶学生印象不深。但其实图算法的选择题规律很强考点就那么几个。第一个高频考点是遍历复杂度。DFS和BFS在邻接表表示下复杂度都是O(VE)在邻接矩阵表示下都是O(V^2)这个结论必须刻在脑子里。选择题会给出具体的图规模和表示方式让你算复杂度只要记住这两个结论基本就不会错。第二个高频考点是Dijkstra算法、Bellman-Ford算法、Floyd算法的适用条件。Dijkstra不能处理负权边Bellman-Ford能处理负权边但不能有负权环Floyd能处理任意两点间的最短路径但复杂度是O(V^3)。选择题经常在这里出混合选项比如“Dijkstra算法不能处理负权边因此不能用于含负权边的图”这种半对半错的表述就是等着粗心的同学往里跳。第三个考点是拓扑排序和最小生成树的性质。Prim算法和Kruskal算法的区别、在有向无环图上拓扑排序一定存在、最小生成树不唯一等情况都是选择题的好素材。复习图算法的时候把Kruskal和Prim的过程在纸上各模拟一遍画出每一步选的边考场上遇到选择题就稳了。3. 简答题必背核心概念会背更要会对比3.1 分治、动态规划与贪心三者的区别和联系简答题中最经典的题目就是让你比较分治、动态规划和贪心算法的异同。这种题看起来很开放实际上有固定的答题套路。我建议从四个维度去组织答案:最优子结构、子问题重叠、贪心选择性质、求解过程方向。分治法的核心思路是“分-解-合”把问题拆成互不相交的子问题分别求解然后合并结果。典型例子是归并排序和快速排序。分治的适用条件是子问题独立不存在重叠子问题。动态规划的核心是“重叠子问题最优子结构”它把一个大问题分解成相互依赖的子问题通过填写表格避免重复计算。典型例子是0-1背包、最长公共子序列。和分治相比动态规划的子问题不是相互独立的而是大量重叠。贪心的特点是每一步都做出当前看起来最优的选择并且不回头。贪心能用的前提是两个性质贪心选择性质和最优子结构。贪心和动态规划最大的区别在于贪心不从子问题的最优解出发而是直接在当前状态做一个局部最优决策所以它更快但是适用面更窄。回答这种对比题时不要简单罗列定义最好能举例说明同样的一个场景在三种策略下的不同处理方式。比如一个找零问题贪心可能直接选面额最大的硬币动态规划则会考虑所有硬币的组合方式。能用例子说明白阅卷老师的体验会好很多。3.2 分治与动态规划之外的必备概念P、NP、NPC问题简答题里另一大必考点就是P、NP、NPC问题的概念辨析。很多同学看到这三个缩写就头皮发麻其实理解起来并不难关键是找到生活化的类比。P类问题就是能在多项式时间内求解的问题比如排序、最短路径。NP类问题不是“非多项式时间”问题而是“能在多项式时间内验证一个解是否正确”的问题比如一个数独盘面填好了验证它是否合法很容易但找出正确填法可能很难。NPC问题则是NP中最难的一类只要能多项式时间解决任意一个NPC问题就意味着所有NP问题都能多项式时间解决。这个考点爱出的简答题方向包括为什么说P不等同于NP“NP难问题”和“NPC问题”的区别在哪里回答时要先给出严格定义然后指出P是NP的子集NPC属于NP且NP中的任何问题都能多项式归约到它。NP难问题则不一定属于NP只要能归约到它即可卡在这里的同学很多。还有一道常见的简答题是让你判断某个具体问题是P问题还是NP问题或者给出一个搜索问题的例子说明验证和求解的区别。这类题考察的不是背定义而是对定义的理解程度。3.3 各算法设计策略的适用场景总结简答题还可能直接问你某个问题最适合用什么策略反过来也会问你动态规划和贪心的选择性质有什么不同这种题考的是场景匹配能力。我整理了记忆口诀分治适合子问题独立动态规划适合子问题重叠且有最优子结构贪心适合有贪心选择性质回溯适合没有最优子结构、需要穷举搜索的组合优化问题分支限界适合在解空间树上找到最优解。考试时如果给一个具体问题比如旅行商问题你应该知道它是NP难问题常规做法用回溯或分支限界用动态规划的话状态压缩可以做但复杂度仍然指数级。另外简答题还经常让学生写出某个算法的基本步骤。比如让你写Dijkstra算法的步骤或者描述哈夫曼编码的构造过程。这种题不难但一定要写得有条理用“初始化-循环-终止”的格式组织答案。平时复习时每个经典算法至少要能写出两三句话的核心流程不能只看懂不做总结。4. 证明题的通用方法从递推到正确性4.1 递推关系求解代入法、递归树与主定理证明题里最基础的一类是给定递推式让你求出渐近复杂度。这类题本质上不是“证明”而是“计算”但很多学校把它放在证明题里因为需要严格推导。常用的方法有三种代入法、递归树法、主定理。代入法就是先猜复杂度上界然后用数学归纳法验证。比如T(n)2T(n/2)n你先猜T(n)O(nlogn)然后假设T(n/2)满足条件代入递推式验证T(n)是否满足。代入法的关键是归纳假设的强度要够如果你猜了个上界却推不出来通常是因为猜得太紧或者太松需要调整参数。递归树法是画出递归调用的树形结构把每层的代价加起来。比如T(n)T(n/3)T(2n/3)n画递归树会发现每层代价是n但树的深度是O(logn)到O(log_{3/2}n)之间最后能推出T(n)O(nlogn)。递归树法比较直观但书写过程较长考试时如果时间紧张可以用主定理做快速判断再用递归树写推导过程。主定理是最快的工具适用于形如T(n)aT(n/b)f(n)的递推式。判断f(n)和n^{log_b a}的增长关系如果f(n)多项式意义上小于n^{log_b a}则复杂度为Θ(n^{log_b a})如果f(n)Θ(n^{log_b a}log^k n)则复杂度为Θ(n^{log_b a}log^{k1}n)如果f(n)多项式意义上大于n^{log_b a}且满足正则条件则复杂度为Θ(f(n))。用主定理时要注意n/b要不是整数时怎么处理以及主定理不适用时f(n)和n^{log_b a}之间差距不是多项式级别要改用递归树。4.2 算法正确性证明循环不变式与归纳法证明一个算法是正确的这门课最常考的是两种方法循环不变式和数学归纳法。它们本质上是一回事只是表述角度不同。循环不变式的证明分三步初始化循环开始前性质成立、保持如果某次迭代前性质成立那么这次迭代后仍然成立、终止循环结束时不变式能推出算法输出正确。以插入排序为例循环不变式是“每一轮迭代结束后子数组A[1..j-1]已经排好序并且包含原数组前j-1个元素”。初始化时j2只有一个元素显然有序保持阶段每次把A[j]插入到前面的有序序列中子数组仍然有序终止时jn1整个数组有序。数学归纳法则更常用于递归算法的正确性证明比如证明二分查找正确或者证明快排的递归版本正确。思路是先证明基本情况然后假设递归调用子问题得到正确答案证明在当前层利用这些答案能得到整个问题的正确答案。写这类证明题时我建议把“假设递归调用返回的结果正确”作为归纳假设明确写出来不要含糊带过这是阅卷时最容易扣分的地方。很多同学在证明正确性时容易犯的错误是只举例说明“这个例子能跑通”而没有给出一般性证明。考试答题时一定要写成“对任意输入规模mn归纳假设成立则对规模n……”这样的形式哪怕你的算法描述复杂也要把归纳框架搭起来再填充细节。4.3 证明贪心算法正确性交换论证法的实战套路如果你们学校考试喜欢出真正有分量的证明题那大概率是证明某个贪心算法能得到全局最优解。这类题也是最让学生头疼的因为贪心算法的“局部最优”看起来就很可疑凭什么证明它全局最优这里有一个万能且常用的方法交换论证法也就是exchange argument。交换论证法的核心逻辑是假设某个最优解和贪心算法得到的解不同找出它们最早的差异位置然后证明可以把最优解换成贪心选择的那个决定而不损害解的优度。反复这样替换最终能把最优解变成一个跟贪心解完全一致或至少同样好的解从而说明贪心解也是最优的。以活动选择问题为例贪心策略是每次选结束时间最早的活动。证明时取一个最优解A它第一个选的活动是a而贪心选的第一个活动是最早结束的g。因为g的结束时间早于或等于a所以可以直接把最优解中的a换成g剩下的活动选择空间不会变差。重复这个过程就得到了一个与贪心解相同的最优解因此贪心解是最优的。哈夫曼编码的证明也是类似思路只是替换时需要考虑叶节点的深度调整稍显复杂。除了交换论证法还有一种常见的证明套路是“剪枝法”也就是说明没有必要考虑贪心没有选择的那些分支它们可以通过某种变换化为等价的贪心选择。剪枝法写起来更简洁但对抽象的直观要求更高。我的经验是先试着用交换论证法写下每一步替换把替换的不等式写清楚一般都能拿分。4.4 复杂度下界证明信息论与对手策略部分高级算法课还会考下界证明比如证明基于比较的排序算法时间复杂度下界是Ω(nlogn)。这道题的核心是信息论n个元素的排列有n!种可能每次比较最多获得1比特信息即两种结果因此至少需要log2(n!)次比较才能区分所有排列。用斯特林公式约掉阶乘log2(n!)≈nlogn-nlog2eO(logn)因此下界是Ω(nlogn)。另一类下界证明用对手策略adversary argument比如证明寻找最大元素至少需要n-1次比较。思路是让对手每次给出一个“不利于算法”的比较结果让需要被确认的信息尽可能晚地确定下来然后分析最少需要多少次比较才能让某个元素从未输给任何其他元素。考试时这类题一般作为加分题知道基本逻辑能写出几步就能得分不必过度担心。5. 复习中的常见问题与考场技巧5.1 常见卡点与思路排查我每次给学弟学妹答疑都会遇到一些重复出现的问题这里整理成了一张速查表你可以对着自己的薄弱环节快速定位。现象可能原因排查建议选择题判断复杂度总错循环步长变化没看出来在草稿纸代几个值观察循环变量增长是线性还是对数主定理用不对忘记比较f(n)和n^{log_b a}或差距不满足多项式级别先算log_b a再用极限比较f(n)/n^{log_b a}的量级证明贪心正确性没思路没找到“最早的差异位置”先把贪心解和最优解各自的前几个选择写出来找出第一个不同点动态规划和贪心分不清没验证贪心选择性质尝试构造一个反例如果能找到反例就不能用贪心简答题写不长缺少对比维度和例子每个核心概念至少要准备一个典型例子答题时先写定义再写例子还有一个大家特别容易踩的坑复习时只看不做或者只做选择题不做证明题。我有一个坚持很多年的练习办法——合上书本拿出一张白纸把每个经典算法的伪代码、复杂度、正确性证明思路各写一遍。写不出来就翻书再合上再写直到能默写为止。这个过程很枯燥但效果奇好因为期末考场上你真的会发现自己手写算法和证明的速度快得飞起。5.2 考场时间分配与答题模板根据我自己当年期末考和后来看别人考试的经验算法课的考试时间通常很紧张基本没有多少检查时间所以答题的节奏感很重要。我建议用这样的时间分配选择题控制在20到30分钟简答题控制在30到40分钟剩下的时间全部给证明题和算法设计题。千万不能在一道选择题上纠结超过3分钟那样后面证明题肯定来不及。证明题答题时哪怕时间不够没法写出完整证明也要把关键的框架写出来先写归纳假设或循环不变式的定义再写初始化和保持步骤的关键不等式。阅卷的时候这些步骤都是得分点写出来比空着强一百倍。不要试图只给一个“显然成立”的结论老师回答说我就没见过哪个“显然”是真的显然。另外证明题需要的是“推导链”。推导链上每一步之间必须有明确逻辑关系比如“因为A所以B又由C可知D”。如果你写出来的推导跳步太大老师很可能看不下去直接扣分。宁可写得啰嗦一点也要把每一步的理由写清楚。我考试的时候习惯在每个关键步骤旁边用括号标注依据比如由归纳假设、由主定理情况2这样既方便自己检查也方便老师给分。5.3 从复习到应用的延伸算法题与机器学习场景现在很多学校的算法课期末也会有一道综合应用大题比如热词里那个“基于机器学习的音乐风格分类算法设计与实现”。这种题看起来跟传统算法课不太搭但本质上还是在考算法设计与分析的基本功特征提取相当于数据预处理分类器训练是一个优化问题评估模型的准确率又涉及复杂度分析。如果你遇到这种综合题核心思路是把机器学习流程映射到经典算法框架里。比如音乐风格分类可以先用滑动窗口从音频中提取特征这是典型的“分治合并”思想然后训练一个K近邻分类器这本质上是搜索问题可以用KD树把查询复杂度从O(n)降到O(logn)评估模型时讨论时间和空间复杂度这就是算法分析的老本行。逻辑严密地讲清楚每一步的算法选择和复杂度得分不会差。就算你的学校不考这种综合题我也建议学有余力的同学找个小项目练手比如用Python写一个简单的音乐分类demo。理由很简单算法设计与分析这门课不只是应付考试它是后续机器学习、数据挖掘、计算机视觉等一系列课程的地基。考试之前练个小项目你会发现那些看似抽象的概念比如动态规划、贪心选择、时间复杂度优化全都能在真实场景中落地理解会一下子加深很多。最后再说一个我踩过的坑。有一年期末复习我花了很多时间死记硬背各种算法的伪代码结果考试时发现简答题考的是“比较动态规划和贪心的特点并举例说明”我明明知道这两个概念但因为没有提前准备好对比性的表达写出来的答案逻辑混乱没拿高分。从那以后我复习每一章都会用“这个概念和易混淆概念的区别是什么”“这个算法的证明套路是什么”“这个算法的典型例题是什么”三个问题来串内容。整个复习过程就变成了一个不断自问自答的过程效果真的不错。你可以试试这个方法把功夫花在考前考场上自然会轻松很多。