企业官网建设流程全解析

1. 复习算法分析之前，先弄清楚这门课到底在考什么

算法分析这门课有个很坑人的地方：它考的东西和大多数人以为要考的东西不是一回事。我见过太多人一头扎进代码里，把每个算法的实现敲了一遍，结果考场上遇到"证明 3n² + 5n = Θ(n²)"这种题还是写不出完整推导。反过来也有一类人，公式背得滚瓜烂熟，让他手写一个归并排序的合并过程却卡壳。这两种偏科都很致命。

1.1 算法分析考的是估算能力，不是编程能力

先把定位摆正。算法分析的核心问题只有一个：当输入规模 n 变大时，算法消耗的资源（时间、空间）以什么样的速度增长。注意是"速度"，不是"具体数值"。你在 2.4GHz 的机器上跑一次快排用了几毫秒，这件事在算法分析里几乎没有意义——换台机器、换个编译器、换个语言，数值全变了，但增长趋势不变。

这是个很重要的认知转变。它意味着复习时的重心应该放在三件事上：

• 能不能准确写出一个算法的耗时表达式（比如循环嵌套的乘法、递归式的展开）
• 能不能把这个表达式化简到渐进形式（抛弃常数、抛弃低阶项）
• 能不能对给定的递归式求出闭式解

至于代码能不能跑通，那是"算法实现"课的事，虽然两者有关系，但复习时间有限时，分析能力必须优先。

1.2 把全部内容分成三档：必须会推、必须会写、认得就行

我的做法是把整门课的内容切成三堆，投入的时间按比例分配：

这个划分不是随便定的。第一档的东西在考卷上占分最重，而且不同题目之间高度复用——主定理会用了，一半的递归式题都能秒杀；摊还分析里势能函数会设了，动态表和并查集的题就都能处理。第二档是"送分题"，但前提是你写过，光看不写考场上手会抖。第三档是"见过就不慌"，考到不会做也不影响及格线。

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 证明题的标准写法：从定义出发的三步走

考试里的证明题基本都是一个套路，我现在写成固定流程，做题时直接套：

1. 写出目标形式：要证 f(n) = O(g(n))，就先摆出"需要找到 c 和 n₀，使得 n ≥ n₀ 时 f(n) ≤ c·g(n)"。
2. 放大化简：把 f(n) 里的低阶项往高阶项上放大，把系数统一。常用手法是"对所有 n ≥ 1，有 n ≤ n²、1 ≤ n"这类不等式。
3. 反推常数：从化简结果倒推出 c 的具体值，再给一个 n₀ 的取值，最后写一句"因此取 c = ?，n₀ = ? 即可"。

举一个具体例子：证明 3n² + 5n + 7 = O(n²)。

对任意 n ≥ 1，有 5n ≤ 5n²，7 ≤ 7n²，所以 3n² + 5n + 7 ≤ 3n² + 5n² + 7n² = 15n²。取 c = 15，n₀ = 1，则对所有 n ≥ n₀ 有 3n² + 5n + 7 ≤ 15n²，即 3n² + 5n + 7 = O(n²)。

这套写法看起来笨，但阅卷时能拿全分，因为它把 c 和 n₀ 都明确了。很多人只写"显然最高次项是 n²，所以是 O(n²)"，在严格证明题里是会扣分的。

2.3 增长速度排序表与几个反直觉的例子

下面这张表建议默写下来，考场上能省很多时间（从慢到快）：

几个反直觉的点，考试爱考：

• 任何多项式都比任何指数慢。n^1000 和 1.001ⁿ 比，最终是指数更大。这个结论的「最终」很重要，n 很小的时候多项式确实更大。
• log(n!) = Θ(n log n)。用斯特林公式或者简单的积分夹逼都能证。这个结论在分析比较排序下界时反复用到。
• 2^(n+1) = O(2ⁿ)，因为 2^(n+1) = 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 ≥ 1，b > 1。令临界指数 c* = log_b a，比较 f(n) 和 n^(c*) 的量级：

三种情形的直觉是：比谁"更重"。如果递归产生的子问题总代价更重（情形一），答案由叶子层决定；如果两边一样重（情形二），答案在临界指数上多乘一个 log；如果顶层 f(n) 更重（情形三），答案就是 f(n)。

最容易踩的坑是三种情形之间的"缝隙"。经典的例子：

• T(n) = 2T(n/2) + n log n。这里 a = 2，b = 2，临界指数 log₂2 = 1，f(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 = 3，b = 4，临界指数 log₄3 ≈ 0.792，f(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 = 3，log₂7 ≈ 2.807，指数上差一点点，当 n 很大时差距就拉开了。这也是"乘法次数决定递归分支数"的典型体现。

分治里有个容易被忽略的分析点：划分是否均匀。如果每次划分都极不均匀（比如快排按固定首元素划分，遇到有序数组），递推式会退化成 T(n) = T(n-1) + Θ(n) → Θ(n²)。这就是为什么分析快排不能只给一个答案，必须分最好、最坏、平均三种情况。

4.2 动态规划：状态数乘单次转移代价

DP 的复杂度分析公式很干脆：

总复杂度 = 状态总数 × 每个状态转移的代价（空间复杂度通常是状态总数）

逐个对照：

这张表里最能考人的是背包问题的 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)

真正难的是证明。贪心正确性证明有两条主流路线：

1. 交换论证（Exchange Argument）：假设存在一个最优解与贪心解不同，把最优解中第一个与贪心选择不同的部分做交换，证明交换后不会变差，由此推出贪心解也是最优的。
2. 贪心选择性质 + 最优子结构：先证第一步的贪心选择一定包含在某个最优解中，再证做完这个选择后的子问题仍然具有最优子结构。

哈夫曼编码的证明用的是交换论证。这里提醒一句：不要把贪心的证法套到 DP 上，也不要用 DP 的证法套贪心。很多人在考场上写"设 dp[i] 表示……"来证贪心，阅卷老师一看就知道概念混了。

5. 图算法里的复杂度，一半的坑在"图怎么存"

图算法的复杂度表达式几乎都带 V 和 E 两个变量，而具体结果和图的存储方式强相关。这一章重点讲这个对应关系。

5.1 邻接矩阵与邻接表的复杂度差异

用 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 最短路与最小生成树的复杂度对照

下面这张表建议连实现方式一起记：

两个常见误区：

第一，Dijkstra 的复杂度写法有多个版本，取决于用邻接矩阵还是邻接表、用线性查找还是堆。答题时最好写清楚前提，否则容易和标准答案对不上。

第二，Bellman-Ford 的 O(VE) 看似比 Dijkstra 慢很多，但它的优势是能处理负权边。这一点经常被出成对比题。

5.3 并查集与摊还分析：O(α(n)) 是怎么来的

并查集是"单个操作看似 O(log n)，整体却是接近常数"的典型例子。三种实现方式的复杂度差异非常大：

反阿克曼函数 α(n) 增长极慢，对任何现实中的 n（哪怕 n 是 10^80），α(n) ≤ 4。所以工程上直接把它当常数看。

这里引出摊还分析的概念：摊还代价是把一系列操作的代价平均到每次操作上，而不是单次操作的最坏代价。路径压缩的代价实际上"预支"到了之前的查找操作上，后面再查就快了。这个思路在下一章展开。

另外说个实现细节的坑：路径压缩在递归实现里容易爆栈。C 语言写并查集时，路径压缩的递归版本深度可能到 O(log n)，但实际竞赛题目里 n 可能有 10⁶，递归会 Segment Fault。稳妥写法是两层循环的迭代版本，先把路径上的点存到一个临时数组，再统一挂到根上。

6. 摊还分析与随机化分析，别等到考前一晚才看

摊还分析是很多人复习时的"盲区"，因为它不像递推式那样有固定套路，需要一点构造思维。但它在考卷上的出现频率不低，而且一旦学会就是稳拿的分。

6.1 聚集法、记账法、势能法三种思路

三种方法解决的是同一个问题，只是叙述角度不同：

1. 聚集法（Aggregate Method）：直接算 n 个操作的总代价上界，再除以 n 得到摊还代价。最直观，适合结构简单的场合。
2. 记账法（Accounting Method）：给每种操作"定价"，实际代价低于定价的操作把差额存进"银行"，实际代价高于定价的操作从银行取钱。要求银行余额永不为负。适合操作类型差异大的场合。
3. 势能法（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(num+1) - 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 的关系与常见误解

必须先纠正一个误解：NP 不是"非多项式"（Non-Polynomial）的意思，而是"非确定性图灵机多项式时间"（Nondeterministic Polynomial）。这个误解带来的连锁错误非常可怕——有人会认为"NP 比 P 难"，其实 P ⊆ NP 是确定的，P 是不是等于 NP 才是那个悬而未决的问题。

另一个误解是归约的方向。要证问题 X 是 NPC，要做的是：

1. 证明 X ∈ NP（给一个多项式时间的验证算法）；
2. 把一个已知的 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-05，T(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 考前一周的具体安排

我给自己排的七天平摊下来大概是这样：

第 7 天的模拟特别重要。算法分析的题有个隐蔽的坑：证明题写起来非常占时间。一道完整的主定理失效证明可能要写二十分钟。如果前面在选择题上磨蹭太久，后面的大题就写不完。我一般会先扫一遍全卷，把分值高而且自己有把握的大题先做，选择题放最后。

最后再分享一个小技巧：考场上遇到不会的递推式，先写递归树的前三层。很多时候写着写着就看出来等比数列的公比了，比干坐着想快得多。这个动作本身也有分——阅卷老师看到你有分析过程，即使最后的 Θ 写错了，过程分也能拿到一些。

还有一个我个人踩过的坑：不要把 Θ 和 O 混着用。题目问"最坏情况下快排的复杂度"，如果你写 O(n²)，严格来说也对，但更准确的答案是 Θ(n²)。如果题目明确要求"用 Θ 记号给出紧界"，写 O 就会扣分。这个细节看起来小，实际上每年都有人栽在上面。