1. 复习算法分析之前先弄清楚这门课到底在考什么算法分析这门课有个很坑人的地方它考的东西和大多数人以为要考的东西不是一回事。我见过太多人一头扎进代码里把每个算法的实现敲了一遍结果考场上遇到证明 3n² 5n Θ(n²)这种题还是写不出完整推导。反过来也有一类人公式背得滚瓜烂熟让他手写一个归并排序的合并过程却卡壳。这两种偏科都很致命。1.1 算法分析考的是估算能力不是编程能力先把定位摆正。算法分析的核心问题只有一个当输入规模 n 变大时算法消耗的资源时间、空间以什么样的速度增长。注意是速度不是具体数值。你在 2.4GHz 的机器上跑一次快排用了几毫秒这件事在算法分析里几乎没有意义——换台机器、换个编译器、换个语言数值全变了但增长趋势不变。这是个很重要的认知转变。它意味着复习时的重心应该放在三件事上能不能准确写出一个算法的耗时表达式比如循环嵌套的乘法、递归式的展开能不能把这个表达式化简到渐进形式抛弃常数、抛弃低阶项能不能对给定的递归式求出闭式解至于代码能不能跑通那是算法实现课的事虽然两者有关系但复习时间有限时分析能力必须优先。1.2 把全部内容分成三档必须会推、必须会写、认得就行我的做法是把整门课的内容切成三堆投入的时间按比例分配档位内容要求时间占比必须会推渐进记号定义题、递推式求解、主定理、摊还分析的三种方法能独立从零写出完整推导50%必须会写快排/归并/堆排/二分/图的遍历与最短路/常见 DP 的状态转移能默写伪代码并说清每一步在干什么30%认得就行Strassen、斐波那契堆、线性规划、近似算法的具体常数知道结论、知道复杂度、知道适用场景20%这个划分不是随便定的。第一档的东西在考卷上占分最重而且不同题目之间高度复用——主定理会用了一半的递归式题都能秒杀摊还分析里势能函数会设了动态表和并查集的题就都能处理。第二档是送分题但前提是你写过光看不写考场上手会抖。第三档是见过就不慌考到不会做也不影响及格线。1.3 我第一次复习时踩的坑把结论当推导说个我自己的教训。第一次复习的时候我把归并排序是 O(n log n)这句话当成知识点背下来了看到题目就往上套。结果遇到求 T(n) 2T(n/2) n 的解这种题我写了个答案 Θ(n log n)但让我解释为什么我说不出来。后来考试出了一道变体T(n) 2T(n/2) n²我还是想当然地写 n log n直接错。问题出在哪我只是记住了结论的形式没有掌握从递归式到闭式解的那条推导链。一旦系数或者非递归项变了我的结论就崩了。后来我强迫自己每道递归式题都用递归树完整推一遍再写答案虽然慢但两周之后速度和准确率一起上来了。所以这一篇我打算按地基—核心工具—范式的分析侧重—图与数据结构—摊还—NP—落地执行的顺序把复习路径讲清楚重点放在那些看起来会但一动笔就卡住的地方。2. 渐进记号这块地基没打牢后面全是空中楼阁渐进记号是整门课的语言。语言不通后面所有推导都是在背天书。这一章我想把定义、证明套路和几个反直觉的坑讲透。2.1 O、Ω、Θ 的定义到底在说什么三个记号的定义必须能一字不差地写出来O大 O上界存在正常数 c 和 n₀使得对所有 n ≥ n₀都有 0 ≤ f(n) ≤ c·g(n)。记作 f(n) O(g(n))。Ω大 Omega下界存在正常数 c 和 n₀使得对所有 n ≥ n₀都有 0 ≤ c·g(n) ≤ f(n)。Θ大 Theta紧界f(n) O(g(n)) 且 f(n) Ω(g(n)) 同时成立。这里有个很多人栽过的细节c 必须是正常数。如果允许 c 取负数或者 0整个定义就废了。还有 n₀ 的存在意义是从某一项开始永远成立——前几项爱怎么乱怎么乱不影响渐进结论。这两点经常被出成判断题。另外要区分小 o 和小 ω。f(n) o(g(n))指的是对任意正常数 c都存在 n₀ 使 f(n) c·g(n)n ≥ n₀也就是 f 的增长严格慢于 g。大 O 只要求存在某个 c小 o 要求对所有 c。这个差别经常被用来出题比如问 2n o(n²) 对不对对2n O(n²) 对不对也对但 n² o(n²) 对不对不对只能写成 O。2.2 证明题的标准写法从定义出发的三步走考试里的证明题基本都是一个套路我现在写成固定流程做题时直接套写出目标形式要证 f(n) O(g(n))就先摆出需要找到 c 和 n₀使得 n ≥ n₀ 时 f(n) ≤ c·g(n)。放大化简把 f(n) 里的低阶项往高阶项上放大把系数统一。常用手法是对所有 n ≥ 1有 n ≤ n²、1 ≤ n这类不等式。反推常数从化简结果倒推出 c 的具体值再给一个 n₀ 的取值最后写一句因此取 c ?n₀ ? 即可。举一个具体例子证明 3n² 5n 7 O(n²)。对任意 n ≥ 1有 5n ≤ 5n²7 ≤ 7n²所以 3n² 5n 7 ≤ 3n² 5n² 7n² 15n²。取 c 15n₀ 1则对所有 n ≥ n₀ 有 3n² 5n 7 ≤ 15n²即 3n² 5n 7 O(n²)。这套写法看起来笨但阅卷时能拿全分因为它把 c 和 n₀ 都明确了。很多人只写显然最高次项是 n²所以是 O(n²)在严格证明题里是会扣分的。2.3 增长速度排序表与几个反直觉的例子下面这张表建议默写下来考场上能省很多时间从慢到快增长级别典型代表说明常数1与 n 无关对数log n二分查找、平衡树的树高多对数log² n、log^k n比 log n 慢很多但仍是多对数级多项式根号级√n试除法判素数线性n数组遍历线性对数n log n归并排序、堆排序平方 / 立方n²、n³冒泡排序、Floyd指数2ⁿ、3ⁿ暴力枚举子集阶乘n!全排列超阶乘nⁿ少见但要知道几个反直觉的点考试爱考任何多项式都比任何指数慢。n^1000 和 1.001ⁿ 比最终是指数更大。这个结论的「最终」很重要n 很小的时候多项式确实更大。log(n!) Θ(n log n)。用斯特林公式或者简单的积分夹逼都能证。这个结论在分析比较排序下界时反复用到。2^(n1) O(2ⁿ)因为 2^(n1) 2·2ⁿ常数 2 不影响。但2^(2n) ≠ O(2ⁿ)因为 2^(2n) (2ⁿ)²是平方关系。log(n^k) k log n Θ(log n)对数的底数和幂次都会退化成常数所以对数的底一般不用写。这几条我当初是抄在纸条上贴桌角的做题时对不上就回去翻。3. 递推式求解复习里投入产出比最高的模块如果只能挑一个模块重点突破我选递推式求解。原因很简单分治算法的复杂度分析本质就是解递推式而分治题在考卷里出现频率极高。这个模块掌握了能同时吃掉好几道题。3.1 代入法、递归树、主定理各自什么时候用三种方法不是互相替代的关系而是适用场景不同代入法猜测 数学归纳适合你已经猜到了答案形式需要严格验证的场合。步骤是先猜 T(n) O(g(n))再用归纳假设代入原式推导。坑点在于归纳假设里的常数要和结论里的常数匹配很多推导卡壳是因为常数取值留的余量不够。递归树法适合看得见结构的递推式尤其是 aT(n/b) f(n) 这种。做法是把递归按层展开算出每层的总代价再把所有层的代价求和通常是个等比数列最后加上叶子层的代价。主定理适合标准形式 aT(n/b) f(n)直接用公式。速度最快但有适用条件条件不满足时必须退回递归树或者代入法。我的习惯是先用主定理试20 秒内能套上就用套不上立刻转递归树递归树求和遇到麻烦再考虑代入法做严格证明。3.2 主定理的三种情形与失效时的补救主定理的标准形式是T(n) aT(n/b) f(n)其中 a ≥ 1b 1。令临界指数 c* log_b a比较 f(n) 和 n^(c*) 的量级情形条件结论情形一f(n) O(n^(log_b a - ε))ε 0T(n) Θ(n^(log_b a))情形二f(n) Θ(n^(log_b a) · log^k n)k ≥ 0T(n) Θ(n^(log_b a) · log^(k1) n)情形三f(n) Ω(n^(log_b a ε))ε 0且满足正则条件 a·f(n/b) ≤ c·f(n)某个 c 1T(n) Θ(f(n))三种情形的直觉是比谁更重。如果递归产生的子问题总代价更重情形一答案由叶子层决定如果两边一样重情形二答案在临界指数上多乘一个 log如果顶层 f(n) 更重情形三答案就是 f(n)。最容易踩的坑是三种情形之间的缝隙。经典的例子T(n) 2T(n/2) n log n。这里 a 2b 2临界指数 log₂2 1f(n) n log n。它比 n¹ 大但不是多项式级别的更大n log n 和 n 的比值是对数级不满足 n^ε 形式所以情形一和情形三都不适用情形二要求 f(n) Θ(n log^k n) 形式但这里 f(n) n log n看上去 k 1 好像能用——可是情形二的结论是 Θ(n log² n)而实际答案也确实是 Θ(n log² n)。这一题其实能用情形二的推广形式处理但严格来说标准表述有争议考试里最好用递归树推一遍。T(n) 2T(n/2) n / log n。这个连情形二都套不上因为 n / log n 和 n 的关系是除以 log不是多项式级别的差。只能靠递归树答案是 Θ(n log log n)。我的建议是凡是在临界指数附近贴边的递推式一律用递归树自己推一遍再对答案。主定理用多了会产生依赖考场上一遇到变体就抓瞎。3.3 手推递归树的完整过程与验算技巧拿 T(n) 3T(n/4) cn² 走一遍完整流程。第一层代价 cn²产生 3 个规模 n/4 的子问题。 第二层每个子问题代价 c(n/4)²共 3 个总代价 3c(n/4)² (3/16)cn²。 第三层3² 9 个规模 n/16 的子问题总代价 9c(n/16)² (9/256)cn² (3/16)²cn²。 依此类推第 i 层总代价是 (3/16)^i · cn²。树的高度从 n 缩到 1 需要 log₄ n 层。叶子层有 3^(log₄ n) n^(log₄ 3) ≈ n^0.792 个叶子每个代价 Θ(1)所以叶子层总代价 Θ(n^0.792)。把内部层求和(3/16)^i 是公比 3/16 1 的等比数列总和收敛到 cn² · 1/(1 - 3/16) (16/13)cn² Θ(n²)。叶子层是 Θ(n^0.792)比 n² 小被吸收掉。结论T(n) Θ(n²)。验算技巧用主定理交叉核对。a 3b 4临界指数 log₄3 ≈ 0.792f(n) cn² Ω(n^(0.792ε))取 ε 1 即可还满足正则条件 3c(n/4)² (3/16)cn² ≤ c·cn²取 c 3/16 这种小于 1 的常数。情形三成立答案 Θ(n²)和递归树一致。这个两条路互相验证的习惯救过我好几次。有一次考试我时间紧只用了主定理结果 a 和 b 抄错了位置如果用递归树估一下层代价就能发现不对劲。4. 分治、动态规划、贪心分析的重点各不相同三大算法范式的代码结构差别很大它们的复杂度分析切入点也不一样。把这一点分清楚遇到新题就知道该往哪儿看。4.1 分治复杂度几乎完全由递推式决定分治算法的复杂度分析基本可以机械化写出 T(n) aT(n/b) D(n) C(n)其中 D(n) 是划分代价C(n) 是合并代价。然后解这个递推式。几个必须记住的结论归并排序T(n) 2T(n/2) Θ(n) → Θ(n log n)二分查找T(n) T(n/2) Θ(1) → Θ(log n)Strassen 矩阵乘法T(n) 7T(n/2) Θ(n²) → Θ(n^(log₂7)) ≈ Θ(n^2.807)而朴素矩阵乘法是 Θ(n³)快速幂T(n) T(n/2) Θ(1) → Θ(log n)最大子数组的分治解法T(n) 2T(n/2) Θ(n) → Θ(n log n)注意 Strassen 这个例子。为什么从 8 次乘法降到 7 次就能把指数从 3 降到 2.807因为 log₂8 3log₂7 ≈ 2.807指数上差一点点当 n 很大时差距就拉开了。这也是乘法次数决定递归分支数的典型体现。分治里有个容易被忽略的分析点划分是否均匀。如果每次划分都极不均匀比如快排按固定首元素划分遇到有序数组递推式会退化成 T(n) T(n-1) Θ(n) → Θ(n²)。这就是为什么分析快排不能只给一个答案必须分最好、最坏、平均三种情况。4.2 动态规划状态数乘单次转移代价DP 的复杂度分析公式很干脆总复杂度 状态总数 × 每个状态转移的代价空间复杂度通常是状态总数逐个对照问题状态数单次转移代价时间复杂度空间复杂度0-1 背包nWO(1)O(nW)O(W)滚动数组最长公共子序列mnO(1)O(mn)O(mn)矩阵链乘n²O(n)O(n³)O(n²)编辑距离mnO(1)O(mn)O(mn)最长递增子序列nO(n)O(n²)O(n)钢条切割nO(n)O(n²)O(n)Floyd 最短路n²O(n)O(n³)O(n²)这张表里最能考人的是背包问题的 O(nW) 到底算不算多项式。答案是不算因为 W 是数值而不是输入长度——输入里表示 W 只用 log W 个二进制位。这类复杂度叫伪多项式是 NP 完全性那一章的经典考点。还有一个常见陷阱是 LIS。朴素 DP 是 O(n²)但用二分 贪心可以做到 O(n log n)。复习时两个版本都要会因为考试可能问能不能更快也可能问用 DP 怎么写。4.3 贪心正确性证明和复杂度是两条独立的评分线贪心算法最容易出问题的不是复杂度而是正确性证明。复杂度分析对贪心来说反而是最简单的部分活动选择按结束时间排序后线性扫描排序 O(n log n) 扫描 O(n) → O(n log n)哈夫曼编码n 个字符每次从小顶堆取两个最小值共 n-1 次合并每次 O(log n) → O(n log n)分数背包按单位价值排序 O(n log n) 线性装填 O(n) → O(n log n)最小生成树的 Kruskal排序 O(E log E) 并查集 O(E α(V)) → O(E log E)真正难的是证明。贪心正确性证明有两条主流路线交换论证Exchange Argument假设存在一个最优解与贪心解不同把最优解中第一个与贪心选择不同的部分做交换证明交换后不会变差由此推出贪心解也是最优的。贪心选择性质 最优子结构先证第一步的贪心选择一定包含在某个最优解中再证做完这个选择后的子问题仍然具有最优子结构。哈夫曼编码的证明用的是交换论证。这里提醒一句不要把贪心的证法套到 DP 上也不要用 DP 的证法套贪心。很多人在考场上写设 dp[i] 表示……来证贪心阅卷老师一看就知道概念混了。5. 图算法里的复杂度一半的坑在图怎么存图算法的复杂度表达式几乎都带 V 和 E 两个变量而具体结果和图的存储方式强相关。这一章重点讲这个对应关系。5.1 邻接矩阵与邻接表的复杂度差异维度邻接矩阵邻接表空间Θ(V²)Θ(V E) 或 Θ(V 2E)无向图判断两顶点是否有边Θ(1)平均 O(deg(v))最坏 O(V)遍历某顶点的所有邻居Θ(V)Θ(deg(v))适用场景稠密图、需频繁判边稀疏图、需频繁遍历邻居用 C 语言描述的话邻接表通常长这样typedef struct Edge { int to; int weight; struct Edge *next; } Edge; Edge *adj[100005]; /* adj[u] 挂的是 u 的所有出边 */ void add_edge(int u, int v, int w) { Edge *e (Edge *)malloc(sizeof(Edge)); e-to v; e-weight w; e-next adj[u]; adj[u] e; }用邻接表做 BFS 或者 DFS复杂度是Θ(V E)因为每个顶点访问一次、每条边访问两次无向图。用邻接矩阵做同样的遍历复杂度会变成Θ(V²)因为每次找邻居都要扫一整行。这个差异在稀疏图上是指数级的差距考场上一旦写错存储方式对应的复杂度整道题的分析都作废。5.2 最短路与最小生成树的复杂度对照下面这张表建议连实现方式一起记算法数据结构时间复杂度能否处理负权BFS 单源最短路无权图队列 邻接表Θ(V E)不涉及Dijkstra邻接矩阵 线性查找Θ(V²)不能Dijkstra邻接表 二叉堆O((V E) log V)不能Dijkstra邻接表 斐波那契堆O(E V log V)不能Bellman-Ford边表Θ(VE)能不能有负环Floyd-Warshall邻接矩阵Θ(V³)能不能有负环Prim邻接矩阵Θ(V²)权重可负Prim邻接表 二叉堆O(E log V)权重可负Kruskal边表 并查集O(E log E)权重可负两个常见误区第一Dijkstra 的复杂度写法有多个版本取决于用邻接矩阵还是邻接表、用线性查找还是堆。答题时最好写清楚前提否则容易和标准答案对不上。第二Bellman-Ford 的 O(VE) 看似比 Dijkstra 慢很多但它的优势是能处理负权边。这一点经常被出成对比题。5.3 并查集与摊还分析O(α(n)) 是怎么来的并查集是单个操作看似 O(log n)整体却是接近常数的典型例子。三种实现方式的复杂度差异非常大实现单次操作复杂度说明朴素无优化O(n)链式退化只按秩合并O(log n)树高受控只路径压缩摊还 O(log n)均摊下来不错路径压缩 按秩合并摊还 O(α(n))几乎常数α 是反阿克曼函数反阿克曼函数 α(n) 增长极慢对任何现实中的 n哪怕 n 是 10^80α(n) ≤ 4。所以工程上直接把它当常数看。这里引出摊还分析的概念摊还代价是把一系列操作的代价平均到每次操作上而不是单次操作的最坏代价。路径压缩的代价实际上预支到了之前的查找操作上后面再查就快了。这个思路在下一章展开。另外说个实现细节的坑路径压缩在递归实现里容易爆栈。C 语言写并查集时路径压缩的递归版本深度可能到 O(log n)但实际竞赛题目里 n 可能有 10⁶递归会 Segment Fault。稳妥写法是两层循环的迭代版本先把路径上的点存到一个临时数组再统一挂到根上。6. 摊还分析与随机化分析别等到考前一晚才看摊还分析是很多人复习时的盲区因为它不像递推式那样有固定套路需要一点构造思维。但它在考卷上的出现频率不低而且一旦学会就是稳拿的分。6.1 聚集法、记账法、势能法三种思路三种方法解决的是同一个问题只是叙述角度不同聚集法Aggregate Method直接算 n 个操作的总代价上界再除以 n 得到摊还代价。最直观适合结构简单的场合。记账法Accounting Method给每种操作定价实际代价低于定价的操作把差额存进银行实际代价高于定价的操作从银行取钱。要求银行余额永不为负。适合操作类型差异大的场合。势能法Potential Method定义一个势能函数 Φ把数据结构在第 i 次操作后的势能记为 Φ_i摊还代价定义为 c_i Φ_i - Φ_{i-1}。只要 Φ_i ≥ Φ_0 恒成立摊还代价就是真实总代价的上界。最通用公式化程度最高。考试时怎么选我的经验是题目给出的数据结构如果状态变量清晰比如元素个数、容量、树的秩优先用势能法因为它最不容易漏项而且阅卷时推导过程一目了然。6.2 动态表扩容的摊还代价推导拿最经典的动态数组扩容走一遍势能法。设定表有 num 个元素capacity 个槽位插入一个元素当 num capacity 时容量翻倍拷贝所有元素。先算朴素代价最坏情况下某次插入要拷贝 capacity 个元素单次代价 O(n)n 次插入最坏 O(n²)。但实际不是这样。用聚集法看容量从 1 翻倍到 2、4、8、……、2^k第 i 次扩容容量从 2^(i-1) 翻到 2^i的拷贝代价是 2^(i-1)。n 次插入的总拷贝代价 ≤ 1 2 4 ... 2^(k) 2n。加上 n 次基本插入总代价 3n所以摊还代价是 O(1)。用势能法交叉验证定义 Φ 2·num - capacity要求这个值非负需要保证表至少半满。插入元素不触发扩容时真实代价 1势能增加 2摊还代价 1 2 3。触发扩容时真实代价 num 1搬 num 个元素 插入 1 个势能从 2·num - num num 变成 2(num1) - 2num - …… 算下来摊还代价是个常数。两条路结论一致都是 O(1)。这个推导特别值得手写三遍因为势能函数的形式是考点不同的教材会用不同的势能有的用 2·num - capacity有的用 num - capacity/2只要最后的结论是常数阶就都对。6.3 随机化算法的期望复杂度怎么算随机化算法的分析要把随机性和复杂度结合起来思路是对随机选择取期望。随机化快排每次随机选主元。期望比较次数是 2n ln n ≈ 1.39 n log₂ n所以期望时间复杂度 Θ(n log n)。推导的关键是定义指示器随机变量 X_ij 表示第 i 小和第 j 小元素是否被比较过然后求总期望。这个指示器变量法几乎每年都考。随机化选择算法RSelect期望 Θ(n)。全域哈希从哈希函数族随机选一个函数每次操作期望 O(1)。跳表插入/查找期望 O(log n)空间期望 O(n)。这里有一个认知上的关键点随机化算法的期望是对算法内部的随机选择取的不是对输入分布取的。这个区别在论述题里经常被问到。比如随机化快排对任何输入都是 Θ(n log n) 的期望复杂度不需要假设输入随机——这比平均情况分析要强因为平均情况分析依赖输入分布假设。7. NP 完全性用最少时间拿到该拿的分NP 完全性这一章的性价比其实很高概念不多但一旦理解清楚选择题和证明题都能稳定得分。它的问题是初学者容易在几个概念上绕不出来。7.1 P、NP、NPC、NP-Hard 的关系与常见误解类别定义直觉P能在多项式时间内求解的判定问题好算NP能在多项式时间内验证一个给定的解是否正确的判定问题好验证NP-Hard所有 NP 问题都能多项式归约到它的问题至少和 NPC 一样难NP-Complete (NPC)同时属于 NP 和 NP-HardNP 里最难的那批必须先纠正一个误解NP 不是非多项式Non-Polynomial的意思而是非确定性图灵机多项式时间Nondeterministic Polynomial。这个误解带来的连锁错误非常可怕——有人会认为NP 比 P 难其实 P ⊆ NP 是确定的P 是不是等于 NP 才是那个悬而未决的问题。另一个误解是归约的方向。要证问题 X 是 NPC要做的是证明 X ∈ NP给一个多项式时间的验证算法把一个已知的 NPC 问题 Y归约到 X即 Y ≤_p X。方向不能反。很多人会写成把 X 归约到 SAT那就变成了在证 X 属于 NP-Hard 的反面逻辑上是错的。记忆口诀要证新问题难就把老难题搬过来。7.2 归约题的答题模板归约题的评分点通常有三条按这个模板写不会漏第一步描述从已知 NPC 问题 Y 的任意实例到目标问题 X 的实例的转换函数 f并说明这个转换能在多项式时间内完成。第二步证明Y 有解 ⟺ f(Y) 有解。这一步分两个方向正向Y 有解 → X 有解和反向X 有解 → Y 有解。第三步说明既然 Y 是 NPC而 Y ≤_p X则 X 是 NP-Hard再结合 X ∈ NP得 X 是 NPC。第二步是拿分的关键两个方向都要写只写一个方向的话一半的分就没了。7.3 经典归约链一定要背下来下面这条链子建议默写考场上至少有方向SAT → 3-SAT → 团问题 → 顶点覆盖 → 独立集 → 哈密顿回路 → 旅行商问题TSP具体对应关系3-SAT ≤_p 团问题每个子句造一个三角形三个顶点跨子句的连接由变量一致性决定。团问题 ≤_p 顶点覆盖G 有大小为 k 的团 ⟺ 补图有大小为 V-k 的顶点覆盖。顶点覆盖 ≤_p 独立集G 有大小为 k 的顶点覆盖 ⟺ G 有大小为 V-k 的独立集。3-SAT ≤_p 哈密顿回路用变量 gadget和子句 gadget构造图。哈密顿回路 ≤_p TSP把边权设为 1 和 2问是否存在总权不超过 V 的环游。链子里的每个箭头都值得自己动手推一遍。不用全推挑三四个重点推剩下的知道结论就行。8. 把复习落到纸上手推、错题本、模拟最后讲讲执行层面的东西。前面全是知识这一章全是方法。8.1 手推比看答案重要得多算法分析这门课有个特点看懂和会写之间有巨大的鸿沟。递归树的三层求和眼睛一扫哦等比数列收敛手上写的时候发现公比算错了势能法的推导看着讲义行云流水自己设势能函数的时候发现不知道从哪里下手。我的做法是准备一沓白纸每道递推式题、每道摊还题、每道归约题都从空纸开始推。推完之后对照答案只标记我在哪一步卡住了不标记我答案对不对。因为答案对可能是蒙的卡住的步骤才是真正的漏洞。具体到每个模块的手推量递推式至少推 20 道覆盖主定理三种情形 两种失效情况摊还分析至少推 10 道动态表、并查集、栈操作各来几道归约至少推 5 道完整的两方向证明图算法复杂度把上面那张表默写三遍能对着图说出每个算法的时间复杂度8.2 错题本只记卡住的点错题本不是抄题目抄题目是浪费时间。我记的是卡住的位置和当时脑子里的错误想法比如2023-11-05T(n) 2T(n/2) n log n。我先套了主定理情形二写成 Θ(n log² n)但不确定对不对。问题在于我没搞清楚情形二的 k 到底怎么取。后来用递归树推了一遍每层代价 n(log n - i)共 log n 层和是 n·(log n ... 1) Θ(n log² n)结论碰巧对但推导路径是错的。教训贴边的递推式必须用递归树验一遍。这种记录方式的好处是每次翻错题本看到的是思维漏洞而不是某道题。复习后期时间紧张翻错题本比重新刷题效率高好几倍。8.3 考前一周的具体安排我给自己排的七天平摊下来大概是这样天数内容目标第 1 天渐进记号 递推式手推 15 道任意递推式能在 5 分钟内出答案第 2 天主定理三种情形 失效情况对照递归树能判断一道题该用哪种方法第 3 天分治 DP 复杂度分析把对照表默写看到算法能立刻说出复杂度第 4 天图算法复杂度 并查集写一遍 C 实现存储方式与复杂度的对应关系不乱第 5 天摊还分析三种方法重推动态表能独立设出势能函数第 6 天NP 完全性 归约推三道完整证明归约方向不写反第 7 天完整模拟一套卷限时找时间分配的问题第 7 天的模拟特别重要。算法分析的题有个隐蔽的坑证明题写起来非常占时间。一道完整的主定理失效证明可能要写二十分钟。如果前面在选择题上磨蹭太久后面的大题就写不完。我一般会先扫一遍全卷把分值高而且自己有把握的大题先做选择题放最后。最后再分享一个小技巧考场上遇到不会的递推式先写递归树的前三层。很多时候写着写着就看出来等比数列的公比了比干坐着想快得多。这个动作本身也有分——阅卷老师看到你有分析过程即使最后的 Θ 写错了过程分也能拿到一些。还有一个我个人踩过的坑不要把 Θ 和 O 混着用。题目问最坏情况下快排的复杂度如果你写 O(n²)严格来说也对但更准确的答案是 Θ(n²)。如果题目明确要求用 Θ 记号给出紧界写 O 就会扣分。这个细节看起来小实际上每年都有人栽在上面。