算法设计与分析这门课期末复习的时候最折磨人的地方在于课本上的定理证明看起来都懂一到手写代码和推导复杂度就卡壳复习题刷了一堆考试换个包装又不认识了。我带过几届学弟学妹复习也自己踩过各种坑最后总结出一套还算好用的打法——不追求把整本书背下来而是抓住复杂度分析 五大算法思想 图论 字符串这几根主线把每类题目的模板、证明套路和易错点固化下来。这篇内容就是把这套复盘思路完整摊开讲从知识地图怎么画、每类算法的核心考点在哪、手写代码怎么保证不丢分到考场上时间怎么分配都尽量说到能直接照着用的程度。不管你是刚学完一学期、脑子里还是一团浆糊还是已经复习过一轮、想找地方查漏补缺下面的内容都能对着看。核心关键词就两个算法、算法设计与分析我会围绕这门课期末最常考的题型来讲代码以 C 和伪代码为主因为我发现大部分学校的期末卷子还是这两种写法最吃香。1. 复习前的整体打法与知识地图拆解很多人复习算法第一反应是打开课本从第一章开始看看到算法的定义就直接困了。我强烈建议别这么干。这门课的知识结构是网状的第一章的定义、第二章的数学基础、后面的分治和动态规划其实是同一套东西在不同场景下的应用你线性地看只会越看越乱。正确做法是先花半小时把整门课的知识地图画出来知道每一块在考卷上大概占多少分再决定投入多少精力。1.1 先搞清楚考卷长什么样再决定怎么复习不同学校的卷子风格差异极大有的偏证明、有的偏手写代码、有的偏选择填空。我统计过自己和几个朋友遇到的卷子大致可以分成三类第一类是重推导型会有大量复杂度计算、递推式求解、正确性证明手写代码题只有一两道第二类是重实现型选择填空加四到五道编程题证明题基本没有或者只要求说思路第三类是混合型各占一半。你先去找学长学姐要一份往年卷判断自己属于哪一类复习的重心就完全不一样了。如果是重推导型那你必须把主定理、递归树、交换论证这些证明工具练熟代码能看懂就行如果是重实现型那就把每个经典算法的手写模板背到肌肉记忆证明题只记住结论和一句话思路即可。最怕的是明明考重实现你花三天啃NP完全性证明最后编程题模板忘了那就亏大了。这个判断我建议在第一轮复习开始前就做完花不了多少时间但能省下大量无效劳动。提示找往年卷的时候顺便把老师的出题习惯记下来——他是喜欢考书上原题还是喜欢改参数、换场景。这两者的复习策略完全不同。1.2 一张知识地图从复杂度到 NP 完全性把这门课拆开主干其实就这么几块我按考试出现频率排个序复杂度分析渐进记号、递推式求解、最好/最坏/平均情况分析。几乎每张卷子都有而且它是后面所有题的地基。分治归并排序、快速排序、二分查找、最大子段和、逆序对计数、大整数乘法。动态规划LCS、LIS、0-1背包、完全背包、编辑距离、矩阵连乘、区间DP。贪心活动安排、哈夫曼编码、单源最短路Dijkstra 也有贪心思想、跳跃游戏。回溯与分支限界N 皇后、子集和、装载问题、图的着色。图算法最短路Dijkstra / Bellman-Ford / Floyd、最小生成树Prim / Kruskal、拓扑排序、关键路径。字符串KMP 的 next 数组、简单模式匹配。NP 完全性P、NP、NPC 的定义归约的基本概念一般只考概念题。你会发现分治、动态规划、贪心这三块本质上都是在回答同一个问题怎么把大问题拆成小问题只是拆法和求解顺序不同。把这条线抓住复习效率会高很多。1.3 三轮复习法时间怎么排最划算我自己的实践是把复习分成三轮每轮目标不同具体安排如下表轮次时间占比核心目标主要动作第一轮40%建立框架、补基础过一遍知识地图把每类算法的思想和模板抄一遍第二轮40%刷题、找漏洞按题型分类刷题错题单独整理第三轮20%模拟、固化模板限时做往年卷把代码模板默写到不看笔记第一轮千万不要追求全都会你的目标是知道有这么个东西知道它在哪一章。第二轮才是真正长本事的时候重点是分类刷题——同一类题连着做五道比五类题各做一道效果好得多。第三轮就干一件事默写模板限时模拟。注意三轮不是严格分开的第二轮的错题要回填到第一轮的框架里第三轮发现模板记不住也要回头补。复习是个循环收敛的过程别把它当成流水线。2. 复杂度分析所有题目的地基先啃下这块硬骨头复杂度分析是这门课里最数学的部分也是很多人第一个卡壳点。但我要说句实在话期末考试里的复杂度分析远没有课本写得那么吓人翻来覆去就那几个套路。你只要把渐进记号的含义、递推式求解的三种方法、以及几类常见结构的复杂度算清楚这一块基本可以拿满分。2.1 渐进记号别死背定义要会看增长量级大 O、大 Ω、大 Θ 这三个记号课本上的定义是用极限和常数写的看着很唬人。其实你只要记住一句话它们描述的不是运行多少秒而是当输入规模 n 变大时运行时间的增长趋势。大 O 是上界最多这么快大 Ω 是下界至少这么快大 Θ 是紧确界差不多就这么快。举个生活化的例子你请客吃饭大 O 相当于花销不超过 500 块大 Ω 相当于至少花 200 块大 Θ 相当于大概 300 到 350 之间。考试常考的是给你两个函数判断 f(n) O(g(n)) 是否成立。这时候你不需要严格证明直接看最高次项n³ 100n² 是 O(n³)因为 n² 项在 n 变大后被 n³ 压住了。100n 是 O(n²)也是 O(n³)因为大 O 只要求上界不要求最紧。真正容易错的是对数。log n 比任何正的幂函数都慢n log n 介于 n 和 n² 之间这几个必须形成条件反射。还有一个坑2^(2n) 和 2^n 是两个不同的量级别以为底数不同无所谓——指数不同就是天壤之别2^(2n) (2^n)²而常数底数不同比如 2^n 和 3^n在某些严格定义下确实是同量级但考试一般不考这么细。2.2 递推式求解三件套代入法、递归树、主定理递推式是复杂度分析的重头戏比如 T(n) 2T(n/2) n 这种。求解方法有三种我建议都掌握因为题目有时会指定方法。代入法猜测 归纳证明先猜一个解比如猜 T(n) O(n log n)然后假设对更小的规模成立代入验证。这个方法考的是你的数感猜的能力靠多做题积累。写的时候要注意归纳假设的严谨性别跳步。递归树法把递归展开成一棵树每一层的代价加起来。以 T(n) 2T(n/2) n 为例第一层代价 n第二层两个节点各 n/2、合计 n第三层合计还是 n……一共有 log n 层所以总代价是 n log n。这个方法特别直观考试里画棵树 写几行求和就能拿分性价比很高。主定理Master Theorem这是最省事的工具形式是 T(n) aT(n/b) f(n)比较 n^(log_b a) 和 f(n) 的大小如果 f(n) 比 n^(log_b a) 小多项式级别则 T(n) Θ(n^(log_b a))如果两者同阶则 T(n) Θ(n^(log_b a) · log n)如果 f(n) 更大且满足正则条件则 T(n) Θ(f(n))。拿归并排序举例T(n) 2T(n/2) na2b2n^(log_2 2) n和 f(n) n 同阶所以 T(n) Θ(n log n)。再拿二分查找举例T(n) T(n/2) 1a1b2n^(log_2 1) n⁰ 1和 f(n)1 同阶所以 T(n) Θ(log n)。这两个是最常考的务必记牢。注意主定理有空隙第一种和第三种情况之间如果 f(n) 不是多项式级别地大于或小于主定理不适用这时候得用递归树。考试里如果出了这种题多半是老师想看你是否知道主定理的局限。2.3 常考复杂度速查表背下来能省一半时间下面这张表是我复习时的救命表考试前反复看基本覆盖了所有会考的算法算法最好平均最坏空间冒泡排序O(n)O(n²)O(n²)O(1)插入排序O(n)O(n²)O(n²)O(1)归并排序O(n log n)O(n log n)O(n log n)O(n)快速排序O(n log n)O(n log n)O(n²)O(log n)堆排序O(n log n)O(n log n)O(n log n)O(1)二分查找O(1)O(log n)O(log n)O(1)Dijkstra堆优化—O((nm) log n)O((nm) log n)O(nm)FloydO(n³)O(n³)O(n³)O(n²)KMPO(nm)O(nm)O(nm)O(m)快速排序最坏 O(n²) 这个点几乎年年考原因也很清楚当每次划分都极度不平衡比如已经有序且总取第一个元素做基准时递归深度退化成 n。理解了这个原因你就能顺带答出随机化基准或三数取中的优化方向。3. 分治与排序类核心考点实战分治是这门课里最漂亮的一类思想把问题分成若干个规模更小的子问题分别求解再合并结果。听起来简单但考试里的分治题往往在合并这一步做文章合并写不好分治就成了摆设。这一节把排序、查找和几个经典分治题讲清楚。3.1 归并排序先把模板刻在脑子里归并排序是分治的标准范例考试要求手写的时候很多人卡在合并函数上。我把最稳的写法列出来注意mid的取法、临时数组的边界、以及最后把剩余元素补进去的处理void mergeSort(vectorint a, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(a, l, mid); mergeSort(a, mid 1, r); vectorint tmp; int i l, j mid 1; while (i mid j r) { if (a[i] a[j]) tmp.push_back(a[i]); else tmp.push_back(a[j]); } while (i mid) tmp.push_back(a[i]); while (j r) tmp.push_back(a[j]); for (int k 0; k tmp.size(); k) a[l k] tmp[k]; }这里有几个细节值得强调。第一mid l (r - l) / 2比(l r) / 2更安全虽然数组下标一般不会溢出但养成习惯没坏处。第二if (a[i] a[j])里的等号决定了排序的稳定性归并排序是稳定排序加等号才能保证相等元素保持原相对顺序这个点经常出判断题。第三复杂度 T(n) 2T(n/2) n用主定理套出来是 Θ(n log n)务必会推。3.2 快速排序划分是灵魂复杂度过坑是重点快速排序的代码比归并短但细节更多核心是划分partition。我用的是最经典的挖坑法Hoare 划分的一个变体int partition(vectorint a, int l, int r) { int pivot a[l]; while (l r) { while (l r a[r] pivot) r--; a[l] a[r]; while (l r a[l] pivot) l; a[r] a[l]; } a[l] pivot; return l; }划分完基准左边的都不大于它右边的都不小于它然后递归处理左右两段。考试常问的坑有三个为什么平均是 O(n log n)、为什么最坏是 O(n²)、为什么要随机化。平均情况的分析思路是每次划分的位置是随机的期望意义下左右两段规模比较均衡递归深度 O(log n)每层总代价 O(n)合起来 O(n log n)。最坏情况就是每次都取到最大或最小值做基准递归变成链状深度 n总代价 O(n²)。随机化的意义就是把最坏情况从必然变成概率极低让期望复杂度稳定在 O(n log n)。实操心得手写快排的时候while里面的边界判断l r一定不能丢否则数组里有等于基准的元素时会死循环或者越界。这是我在纸上写代码时翻过车的地方。3.3 二分查找的三种变体别只会最基础那种基础二分查找大家都熟但考试往往考变体比如找第一个大于等于目标的位置lower_bound和找最后一个小于等于目标的位置upper_bound。我建议直接记下面这个统一模板它比各种花哨写法好记// 找第一个 target 的下标 int lowerBound(vectorint a, int target) { int l 0, r a.size(); // 注意 r 取 size左闭右开 while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; }这个模板的关键是区间定义成左闭右开[l, r)循环条件是l r最后返回l。把改成就能得到找第一个大于 target的位置。很多人记不住二分是因为每次都用不同的区间定义混着写必然出错。统一成一种练熟就行。分治经典题里最大子段和和逆序对计数是高频考点。最大子段和的分治思路是最大子段要么完全在左半边要么完全在右半边要么横跨中点。前两种递归求解第三种从中点向两边扩展求最大值然后三者取大。复杂度 T(n) 2T(n/2) O(n) O(n log n)。逆序对计数则是在归并排序的合并过程中顺便统计当右边的元素被取出时左边剩下的元素个数就是它构成的逆序对数。这个技巧特别巧妙理解了就忘不掉而且它就是归并排序的副产品代码改动极小。4. 动态规划状态定义定生死转移方程见真章动态规划是这门课最容易失分、也最能拉开差距的部分。我见过太多人题目看懂了、思路也有了但状态一写错后面全盘皆输。这一节我把 DP 的通用解题流程拆开再配合几道必考经典题。4.1 动态规划四步法照着走不会跑偏我总结的 DP 四步法是这样的定义状态明确dp[i]或dp[i][j]到底表示什么。这一步是灵魂写代码前先在纸上用一句话写清楚。找转移方程当前状态由哪些更小的状态推出来怎么推。确定边界和初始化最小的子问题答案是什么dp数组初始值怎么设。确定遍历顺序保证算当前状态时依赖的状态已经算好了。这四步里第一步最难也最关键。判断状态定义对不对有个简单标准能不能从子问题的答案唯一地推出当前答案。如果不能说明状态维度不够得加一维。4.2 四道必考经典题逐个击破最长公共子序列LCS给定两个字符串求它们最长的公共子序列长度。状态定义dp[i][j]表示s1前 i 个字符和s2前 j 个字符的 LCS 长度。转移方程分两种情况如果s1[i-1] s2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])。边界是dp[0][*] dp[*][0] 0。时间复杂度 O(nm)。最长递增子序列LIS经典做法是dp[i]表示以第 i 个元素结尾的最长递增子序列长度转移是遍历所有j i若a[j] a[i]则dp[i] max(dp[i], dp[j] 1)复杂度 O(n²)。优化版用二分 贪心能做到 O(n log n)考试如果没要求优化写 O(n²) 就够了。0-1 背包dp[j]表示容量为 j 时能装的最大价值转移是逆序遍历容量dp[j] max(dp[j], dp[j-w[i]] v[i])。这里逆序是重点因为要保证每个物品只被用一次。如果是完全背包物品可以无限取就改成顺序遍历这个对比几乎是必考。编辑距离dp[i][j]表示把s1前 i 个字符变成s2前 j 个字符的最少操作数。转移考虑插入、删除、替换三种操作取最小值。这道题的状态定义和 LCS 很像可以一起记。4.3 区间 DP 与滚动数组进阶但常考区间 DP 的典型是矩阵连乘和石子合并。状态一般是dp[i][j]表示区间[i, j]的最优解转移是枚举分割点 kdp[i][j] min(dp[i][k] dp[k1][j] cost)。遍历顺序上必须按区间长度从小到大来因为长区间依赖短区间。滚动数组则是空间优化的常用手法。当dp[i][j]只依赖dp[i-1][*]时可以把第一维压掉只留一维数组。0-1 背包就是典型例子。考试里如果能主动提出空间优化往往是加分项。注意用滚动数组时一定要想清楚遍历方向。0-1 背包逆序、完全背包顺序这个差别就是物品能不能重复用的直接体现别记混了。5. 贪心算法与正确性证明选对策略还要证明它对贪心算法写起来最短但它的坑在于——有时候贪心是错的你得能判断出来。考试里贪心题的难点从来不是代码而是为什么这么贪是对的也就是正确性证明。5.1 贪心的适用条件和两种证明套路贪心能用的前提是问题具有两个性质贪心选择性质每一步的局部最优能导向全局最优和最优子结构大问题的最优解包含子问题的最优解。证明局部最优能推出全局最优常用两种方法交换论证法假设存在一个最优解和贪心解在某一步不同通过交换它们的某两个选择证明交换后不会变差从而说明存在一个包含贪心选择的最优解。这个证明写起来有固定套路先设符号、再交换、最后说明不劣练三五道就能上手。归纳法对步骤数做归纳证明每一步之后贪心解都可以扩展成某个全局最优解。5.2 三道经典贪心题覆盖 90% 考法活动安排问题给定若干活动的起止时间求最多能参加几个。贪心策略是按结束时间从早到晚排序能选就选。为什么按结束时间排而不是开始时间因为结束越早留给后面活动的时间越多。这个为什么经常作为简答题考。哈夫曼编码每次从集合里取两个权值最小的节点合并直到只剩一个。它保证加权路径长度最小是贪心正确性的经典案例。手写的时候用优先队列小顶堆实现复杂度 O(n log n)。跳跃游戏 II求跳到末尾的最少步数。贪心策略是在当前能到达的范围内选一个能跳最远的位置作为下一跳。这道题在热词里也出现了属于近年高频题思路是维护当前步数能覆盖的最远边界边界到了就步数加一。5.3 贪心的常见误区避开就是赚最常见的误区是看到最优化就上贪心。最典型的反例是 0-1 背包——如果你按单位价值排序做贪心会得到错误答案因为物品不能拆分正确解法是动态规划。这个对比是考试常考的概念题一定要能举例说明。第二个误区是排序依据选错。活动安排按结束时间但有的题看着像活动安排实际要按开始时间或者按区间长度得具体分析。判断依据是你的排序规则能否保证不会因为当前选择而丢失更优的未来。第三个误区是证明写得太随意。考试里如果题目明确要求证明贪心策略的正确性你光写因为每次都选最优的所以全局最优是拿不到分的必须用交换论证或归纳法把逻辑走完。6. 图算法高频考点三大最短路 两棵生成树图论部分的特点是算法多、细节杂但每年考的其实就是那么几个。我把它拆成最短路、最小生成树、拓扑排序三条线来讲每条线配上对比表和手写要点。6.1 最短路三兄弟Dijkstra、Bellman-Ford、Floyd 怎么选这三个算法经常放在一起考核心是什么场景用哪个。我整理成下面这张对比表算法适用场景负权边复杂度核心思想Dijkstra单源、非负权不支持O(n²) 或 O((nm)log n)贪心每次选最近的未访问点Bellman-Ford单源、可有负权支持O(nm)对所有边松弛 n-1 轮Floyd多源任意两点支持无负环O(n³)动态规划枚举中间点Dijkstra 不能用负权边的原因是它基于已确定的点不会再有更短路径这个贪心假设负权边会破坏这个假设。Bellman-Ford 能检测负环如果在第 n 轮还能松弛说明存在负环。Floyd 的三重循环里中间点 k 必须放在最外层这个顺序不能换因为它的本质是只允许经过前 k 个点作为中间点的 DP。手写 Dijkstra 的朴素版时核心是维护一个dist数组和visited数组每轮找未访问的最小dist点用它去松弛邻居复杂度 O(n²)。如果图稀疏用优先队列优化到 O((nm) log n)。6.2 最小生成树Prim 和 Kruskal 的分工Prim 算法像 Dijkstra从一个点出发每次把距离已生成树最近的点加入适合稠密图复杂度 O(n²)。Kruskal 则是按边权从小到大排序用并查集判断两个端点是否已经连通不连通就加入适合稀疏图复杂度 O(m log m)。这两棵生成树的题经常考为什么 Kruskal 要用并查集和为什么 Prim 适合稠密图。前者因为要频繁判断连通性并查集的近 O(1) 操作是关键后者因为 Prim 是点驱动的稠密图里点的操作次数固定为 n²边多也不怕。6.3 拓扑排序与关键路径AOE 网必考拓扑排序针对有向无环图DAG做法是维护入度数组每次取入度为 0 的点删掉它的出边并更新邻居入度。如果最后输出的点数少于总点数说明有环。这个判断有无环的应用经常考。关键路径是基于 AOE 网边表示活动的网络的要算每个事件的最早发生时间和最晚发生时间两者相等的就是关键活动串起来就是关键路径。计算过程分四步正向求最早时间、逆向求最晚时间、算活动的最早/最晚开始时间、找差值为 0 的活动。这套流程背熟之后考试就是套公式。7. 回溯、分支限界与剪枝暴力搜索的优雅版本回溯和分支限界本质上都是有技巧的暴力枚举区别在于回溯用深度优先、分支限界用广度优先或优先队列。考试主要考回溯问题一般出现在 N 皇后、子集和、装载、着色这类组合优化题上。7.1 回溯框架三要素一模板回溯有三个要素路径已经做的选择、选择列表当前能做的选择、结束条件到达决策树底层。模板几乎是固定的void backtrack(路径, 选择列表) { if (满足结束条件) { 记录结果; return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } }做选择和撤销选择成对出现这是回溯的灵魂。理解了这一点写回溯就像套公式。7.2 N 皇后剪枝怎么剪才到位N 皇后的约束是同列、同对角线不能有两个皇后。列冲突用一个col数组判断两条对角线分别用主对角线 row - col n和副对角线 row col判断。这三个数组就是剪枝的关键——它们让每层递归在选择时就能快速排除冲突位置而不是生成完整排列后再验证。复杂度上N 皇后的搜索空间是 n!但剪枝后实际访问的节点数远小于这个。考试如果问剪枝的效果你可以说剪枝是在搜索树的内部节点提前判断并剪掉不可能产生解的分支从而减少无效搜索。7.3 分支限界与剪枝的取舍分支限界法适合求解最优化问题它用一个界限函数估计当前节点可能达到的最优值如果估出来的界比当前已有的最优解还差就剪掉这个节点。比如 0-1 背包的分支限界用剩余物品全按单位价值贪心装来估计上界一旦上界不超过当前最优就剪枝。考试里分支限界一般只考思路和界限函数的构造很少要求完整手写。理解上界估计 剪枝这个核心就够了。8. 字符串与 KMPnext 数组一次搞懂8.1 next 数组到底在记什么KMP 的精髓是 next 数组它记录的是当模式串第 j 位失配时应该回退到哪个位置继续匹配。next 数组的物理含义是模式串的前缀和后缀相等的最大长度。比如模式串ababnext[4]对应abab的最长相同前后缀长度是 2ab。手算的时候从前往后推a没有真前后缀next 值为 0ab没有0aba是 1aabab是 2。写代码时用自己匹配自己的方式求vectorint buildNext(string p) { int m p.size(); vectorint nxt(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] j; } return nxt; }这个版本求出的nxt[i]表示以 i 结尾的子串的最长相同前后缀长度匹配时用j nxt[j-1]回退。不同教材的 next 数组定义略有差别有的从 -1 开始考试时要看清题目的定义这点特别重要。你们学校用哪种你对照课本确认一遍。8.2 KMP 匹配过程与复杂度的直观解释匹配时主串指针 i 从不回退只有模式串指针 j 在失配时回退到nxt[j-1]。因为 i 只增不减整个过程 O(n)加上构建 next 的 O(m)总复杂度 O(nm)。这个主串指针不回退就是 KMP 相对朴素匹配 O(nm) 的优势所在考试问你KMP 为什么快答这一点就能得分。9. 答题技巧与考场实战策略复习到位了考场上还得会拿分。这一节讲的是非知识性的技巧但往往比知识点还值钱。9.1 手写代码题怎么保证不丢分手写代码题评分一般是按点给分所以你要主动把得分点露出来。我的经验是先写函数签名和注释说明参数含义再写核心逻辑最后补边界条件。不要一上来就写代码先花半分钟在草稿上理清思路。具体的几个要点变量名写清楚i、j这种通用没问题但别用a、b这种无意义的名字循环边界要明确尤其是和的取舍递归写清楚终止条件如果时间不够把思路用注释写出来往往也能拿一半分。9.2 证明题怎么写才有分证明题的评分看的是逻辑链条完整性不是结论对不对。写之前先把要证的命题和已知条件列出来然后一步一步走。交换论证的固定句式是先假设最优解和贪心解在某一步不同再构造交换最后说明交换后目标函数不变差。写的时候用假设……构造……因为……所以……这种连接词让阅卷老师一眼看到你的逻辑。提示如果实在证不出来把相关定义和已知结论写上去有时能拿步骤分。别空着。9.3 时间分配别在一道题上耗死以 120 分钟、总分 100 分、10 道题为例平均每题 12 分钟但题目难度不均。我的建议是先花 2 分钟扫一遍全卷把会做的标记出来先做有把握的。选择填空争取在 20 分钟内完成代码题每道控制在 15 分钟以内留 15 分钟检查。遇到卡壳超过 5 分钟的题先跳过等做完其他题再回来。考场心态很关键一道题做不出来不代表别的题也做不出来。10. 常见问题与排查复习路上的坑一次说清复习到后期问题往往集中在几个地方。我把最常见的问题整理成速查表问题现象可能原因解决办法复杂度算不对主定理空隙情况没判断改用递归树或检查 f(n) 与 n^(log_b a) 是否同阶DP 状态写不出来状态维度不够问自己子问题答案能否唯一推出当前答案不够就加维贪心写成错的排序依据选错用交换论证验证找反例测试快排死循环边界条件写漏检查while里的l rKMP 和课本对不上next 定义不一致对照课本确认 next 起点是 0 还是 -1图论算法混淆适用场景没分清记对比表重点记负权和单源/多源回溯超时剪枝不到位增加可行性剪枝提前排除冲突手写代码总出错逻辑没理清就写先在草稿写思路再落笔代码这张表里的每一条都是我在实际复习和考试里踩过的。比如快排那个死循环当年考场上我盯着代码看了三分钟才发现是边界条件的问题出考场一查才知道有多简单。再比如 next 数组不同教材定义不同我第一遍看课本、第二遍看别人的博客两套定义混在一起结果两道题全错。还有个特别容易忽略的点复习题里的简单题往往是陷阱。比如写出冒泡排序的代码看着简单但如果老师要求你顺便分析最好情况复杂度很多人会忘记最好情况是 O(n)当数组已经有序且加了提前退出标志时。复习的时候简单题也要想一遍老师可能怎么加料。实操心得复习后期把每类算法的考点清单写在一张纸上——模板、复杂度、适用场景、易错点、可能加料的地方就这五栏。考试前一天只看这张纸比翻课本高效十倍。我个人在实际复习和带人复习的过程里最大的体会是算法这门课不是靠背书能过的它靠的是把每一类问题的思考方式变成肌肉记忆。你看到最大子段和能条件反射地想到分治和 DP 两种解法看到单源最短路能立刻区分有没有负权看到最优化问题能先判断是 DP 还是贪心——到了这个程度考试就是走流程。至于那些手写代码的模板别指望考前突击从复习第一天开始每天默写两三个到考试那天闭着眼都能写出来。最后再分享一个小方法把你觉得最难的那道题用最笨的方式讲给室友听讲得他听懂了你就是真懂了。