一个分治算法写完、样例也跑通之后，很多人第一个想问的问题不是“这个思路对不对”，而是“这个算法的复杂度到底是多少”。如果你已经看过前面两篇关于代入法和递归树法的分析，肯定有一个感受：代入法要先猜再证，递归树要一层层画，碰上复杂一点的递归式，都很费劲。这一篇专门讲第三件利器——用主方法求解递归式，这也是分治策略时间复杂度分析里最像“套公式”的一步。

主方法（Master Theorem）专门用来解形如 T(n) = aT(n/b) + f(n) 的递归式，它不需要展开递归树、不需要猜上界，直接把复杂度和 f(n) 与 n^(log_b a) 的增长关系对上号，三选一给出答案。这篇内容适合正在学算法的学生、准备面试的开发者，以及那些写了不少分治代码、却始终搞不清复杂度为什么是 O(n log n) 或 O(n^log_2 3) 的工程师。我会从标准形式的前提条件讲起，把三种情况的判定逻辑掰开，再配合一组可以直接“抄作业”的手算案例，最后把常见误区和排查过程完整列出来。

1. 主方法是什么：一个公式解决一类递归式

1.1 先说清楚主方法能解哪一类递归式

主方法不是万能的，它有非常明确的适用边界。它针对的是这种标准形式：

T(n) = aT(n/b) + f(n)，其中 a ≥ 1，b > 1，f(n) 是渐近正的函数。

拆开看就是：一个问题规模为 n，每次都分成 a 个大小约为 n/b 的子问题，递归地把子问题解决掉，再做合并或额外处理，这部分代价记作 f(n)。绝大多数经典分治算法都能写成这个形状，比如二分查找是 T(n) = T(n/2) + O(1)，归并排序是 T(n) = 2T(n/2) + O(n)，Strassen 矩阵乘法是 T(n) = 7T(n/2) + O(n^2)。

这里有几个前提必须满足。a 是子问题个数，必须是整数、至少为 1，而且不能随着 n 变化；b 是规模缩减比例，必须大于 1，体现“每次确实把问题变小了”；f(n) 是渐近正的，意思是当 n 足够大时它保持非负，不能是那种振荡到负数、或者压根不单调的函数。如果 a 或 b 不是常数，或者 f(n) 是阶乘、指数这类非多项式函数，主方法的标准形式就套不进去，得退回递归树或代入法。

1.2 为什么叫“主方法”：它是分治复杂度分析的主干

很多人第一次听到 Master Theorem 觉得很神秘，其实它只是把递归树法里看到的结果总结成了一条定理。我当时理解主方法时，有一个很直观的生活类比：假设你要把一笔钱分给若干个孩子，每个孩子再把分到的钱继续分下去。最后的财富分配，要么取决于最上面那一层的分法，要么取决于最低层每个叶子手里的钱，要么是每一层都差不多，取平均值。主方法的三种情况，对应的正是“哪一层主导总成本”的三种可能。

这个视角很重要，因为很多初学者死记三种判定条件，却不知道它们背后的含义。主方法之所以被广泛使用，是因为分治算法里递归式的模式高度规律化，只要确认递归式符合标准形式，再比较 f(n) 和 n^(log_b a) 的增长速度，就能直接写出复杂度，不需要重复地做递归树展开。后面我会专门用递归树视角证明这套逻辑为什么成立，这里先记住：主方法是“递归树观察结论的公式化”，不是凭空冒出来的魔法。

2. 用主方法求解前，先做这三步检查

2.1 第一步：把递归式改写成标准形式

我看到很多人在这一步就翻车了。题目给出的递归式经常不是标准样子，比如 T(n) = 2T(n/2) + n^2，或者 T(n) = 2T(n/4) + sqrt(n)，这些还算好；但如果你遇到 T(n) = 2T(n/2) + n log n，或者 T(n) = 3T(n/2) + n^2，就需要冷静下来，把里面的 a、b、f(n) 一个个摘出来。

具体做法是：先把递归式写成一模一样的标准形式 T(n) = aT(n/b) + f(n)，把子问题个数 a 写在系数上，把递归参数里的 n/b 标清楚，剩下的加减部分就是 f(n)。如果递归式里还混着取整符号，比如 T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + n，绝大多数情况下主方法的结论依然有效，因为取整带来的误差顶多影响常数因子，不影响渐近级数。这一点通常教材不会细讲，但我实际做题和推导算法时验证过很多次，可以直接用。

如果递归式完全没有标准形态，比如 T(n) = T(n-1) + n，这就不是分治型的，而是线性的递推，主方法不适用，应该考虑累加法或者公式法。所以第一步的本质是回答一个问题：这个递归式到底是不是分治采样、规模是不是按比例缩小？如果不是，就别硬套。

2.2 第二步：计算关键参考量 c = log_b a

把标准形式整理好之后，立刻计算 log_b a 的值，这个值是整个主方法的“分水岭”。它代表的是递归树最后一层叶子节点的个数级别，我稍微解释一下：一共递归了多少层？每层规模除以 b，所以层数是 Θ(log_b n)；每个叶子节点来自一条从根到叶子的路径，每个节点分裂成 a 个子节点，所以叶子总数是 a^(log_b n) = n^(log_b a)。因此 n^(log_b a) 是叶子层代价的数量级，它是和 f(n) 比大小的基准线。

举例来说，如果 T(n) = 2T(n/2) + n，那么 a = 2，b = 2，c = log_2 2 = 1，基准线是 n^1 = n；如果 T(n) = 3T(n/4) + n，那么 a = 3，b = 4，c = log_4 3 ≈ 0.792，基准线是 n^0.792；如果 T(n) = 4T(n/2) + n，那么 a = 4，b = 2，c = 2，基准线是 n^2。这个基础值一出来，后面比较才有意义。

这里有个小技巧：计算 log_b a 时，底数是多少其实无所谓，因为不同底数的对数只差一个常数倍，最终复杂度里会消掉。所以你不需要纠结 b 是 2 还是 4，只要指数 c 算得准就行。我一般直接用换底公式，或者闭上眼睛估算：如果 a 是 b 的 k 次方，那 c 就是 k，比如 8 和 2 组合，c = 3；如果中间有小数，就保留到小数点后两位足够判断和 f(n) 的相对大小了。

2.3 第三步：判断 f(n) 和 n^c 的“增长速度差”

判断有两种标准：一是判断差距是不是“多项式级别的差距”，二是判断差距是不是“对数级别的差距”。因为主方法的三条情况，恰好把这种比较分成了三大类：

• 情况 1：f(n) 明显小于 n^c，而且差距至少是多因子 n^ε（ε > 0），这时叶子层占主导；
• 情况 2：f(n) 和 n^c 差不多大，允许差若干 log 因子，这时每层成本基本一样；
• 情况 3：f(n) 明显大于 n^c，而且差距至少是多因子 n^ε，同时满足某个正则约束，这时根节点层占主导。

初学的人最容易犯的错，是把“f(n) < n^c”直接当成情况 1。不对，必须强调“多项式差距”。比如 f(n) = n / 100，n^c = n，虽然 n/100 和 n 有常数差距，但指数相同，这不是情况 1，而是情况 2。又比如 f(n) = n^0.5 log n，n^c = n^0.5，虽然后者是前者的 log 倍，但 log 增长率低于任何 n^ε，所以也不是情况 1。只有像 n^0.5 对 n^0.6、n 对 n^1.5 这种，指数本身有正差距的时候，才符合情况 1 或 3。

判断完之后，对照三种情况写结论即可。下面我就把三种情况分别拆开讲透。

3. 三种情况怎么判：别只背条件，要理解“哪一层买单”

3.1 情况 1：叶子层主导，T(n) = Θ(n^c)

判定条件是：f(n) = O(n^(c - ε))，其中 ε > 0。意思是 f(n) 的增长率不仅在量级上小于 n^c，而且至少差了一个多项式因子 n^ε，比如 n^0.5 对 n、n 对 n^2 这种。这种情况下，递归树每往上走一层，成本就在逐层递减，而且递减得很快，所有层的总成本加起来，也就和最底层（叶子层）的成本差不多。写成递归式就是 T(n) = Θ(n^c)。

经典例子是寻找最大值或最小值：把数组一分为二，分别找最大值，再比一次，T(n) = 2T(n/2) + O(1)。这里有 a = 2，b = 2，c = 1，f(n) = O(1)，而 1 = O(n^(1-ε))，随便取 ε = 0.5 都能成立。所以 T(n) = Θ(n)。这个结论很直观：虽然有递归和合并，但每层就做常数次比较，总共比较大约 2n 次，线性复杂度。

为什么每层成本是递减的？从递归树看，第 0 层（根）成本是 f(n)；第 1 层有 a 个节点，总成本是 a f(n/b)；第 k 层总成本是 a^k f(n/b^k)。当 f(n) 本身远小于 n^c 时，这个等比数列的公比小于 1，相加的和收敛到首项的常数倍；但同时叶子层数量是 n^c，反而成了最大的项，所以总复杂度由叶子层决定。我当年学到这里的时候，惊讶于“合并代价那么小，真正花时间的是每个叶子问题的处理”，后来看实际代码，确实最底层的循环大多占了大头。

3.2 情况 2：每层成本相当，T(n) = Θ(n^c log^(k+1) n)

判定条件是：f(n) = Θ(n^c log^k n)，其中 k ≥ 0。也就是说，f(n) 和 n^c 之间只是差一些 log 因子，没有多项式级别的差距。这时候每一层的总成本都差不多，一个递归树有 Θ(log n) 层，所以总成本就是 n^c 乘以 log n，如果本来就带一个 log^k，那最后就是 n^c log^(k+1) n。

最典型的例子就是归并排序：T(n) = 2T(n/2) + O(n)。a = 2，b = 2，c = 1，f(n) = n，正好是 n^1 log^0 n，属于情况 2，所以 T(n) = Θ(n log n)。这也是所有基于比较的排序算法的最优下界之一，归并排序能达到这个界。另一个常见例子是 T(n) = 2T(n/2) + n log n，这时代价 f(n) = n log n，也属于情况 2（k = 1），结果是 T(n) = Θ(n log^2 n)。如果你在算法题里碰见类似结构，可以直接套这个结论。

这里要注意，很多教材写情况 2 的结论是 Θ(n^c log n)，其实那是 k = 0 的特例。完整的结论是 Θ(n^c log^(k+1) n)，因为每个节点层都有 Θ(n^c log^k n) 的消耗，乘上 Θ(log n) 层，k 就要加 1。初学者只用 n log n 套所有情况，看到 T(n)=2T(n/2)+n log n 时容易写错，实际上多一个 log。

3.3 情况 3：根节点层主导，T(n) = Θ(f(n))

判定条件是：f(n) = Ω(n^(c + ε))，且 a f(n/b) ≤ c' f(n)（c' < 1）对足够大的 n 成立。这个正则条件看起来莫名奇妙，但你必须检查。它保证的是：递归树从根往下，每一层的成本至少要小于上一层的某个常数比例，也就是说成本在逐层递减，总和被根节点层 f(n) 掌控，不会出现越往下成本越大的怪事。

经典例子是 T(n) = 3T(n/4) + n^2。a = 3，b = 4，c = log_4 3 ≈ 0.792，f(n) = n^2。n^2 相对 n^0.792 大得多，差了一个多项式因子 n^1.2，所以候选情况 3。接着检查正则条件：3 * (n/4)^2 = 3n^2 / 16 ≤ c' n^2，取 c' = 1/2（或任何大于 3/16 小于 1 的常数）都成立。结论就是 T(n) = Θ(n^2)。

再举个例子，T(n) = 2T(n/2) + n^2，这里 a=2、b=2、c=1，f(n)=n^2 比 n^1 大，显然属于情况 3，最终复杂度 Θ(n^2)。也就是说，如果合并代价是平方级，那递归拆分完全不重要，顶层的代价直接把整个算法压死。这个结论对实际做算法优化很有参考价值：合并操作的复杂度直接决定总复杂度上限，优化合并往往是收益最大的地方。

正则条件什么时候会出问题？我见过一个反例：T(n) = 2T(n/2) + n^2 / log n。这里 f(n) 虽然比 n 大，但大了不到一个多项式因子（差的是 n / log n 而不是 n^ε），所以严格来讲不属于情况 3，也不能用情况 1 或 2，主方法在这个递归式上直接失效。遇到这种情况，应该用递归树法手动展开求和。

4. 手算梳理：从递归式到答案的完整流程与案例

4.1 四个可直接照抄的完整推导案例

我挑四个典型递归式，把整个手算过程展开如下，你可以照着这个顺序练习：

案例 1：T(n) = 9T(n/3) + n

第一步检查标准形式：a = 9，b = 3，f(n) = n。第二步算参考量：c = log_3 9 = 2，所以 n^c = n^2。第三步比较：f(n) = n 明显小于 n^2，而且差了一个多项式因子 n，满足情况 1。结论：T(n) = Θ(n^2)。直觉上，每一层节点数疯狂膨胀，叶子层总数达到 n^2，合并代价 n 根本不够看。

案例 2：T(n) = 2T(n/2) + n

前面说过，c = log_2 2 = 1，f(n) = n = n^1，正好是情况 2 的 k=0。结论：T(n) = Θ(n log n)。这是归并排序和很多优秀分治算法的基础。

案例 3：T(n) = 2T(n/4) + n^0.5

这里 a = 2，b = 4，c = log_4 2 = 0.5，所以 n^c = n^0.5。f(n) = n^0.5 和 n^c 相等，属于情况 2。结论：T(n) = Θ(n^0.5 log n)。注意，这个递归式来自某些能“把问题缩得很快”的分治策略，比如在二维平面上某些分治求最近点对的处理。合并代价等于根节点代价，每层都一样，最后多出 log n。

案例 4：T(n) = 4T(n/2) + n^2

a = 4，b = 2，c = log_2 4 = 2，f(n) = n^2 和 n^c 相等，也是情况 2。结论：T(n) = Θ(n^2 log n)。这个例子通常用于说明“子问题翻 4 倍、规模减半、合并平方级”会发生什么——与合并排序不同，它在 n^2 基础上再多一个 log 因子，实际跑起来 n 稍大就会很吃力。

这四个例子覆盖了三种情况的两两分总。我强烈建议你在草稿纸上按“三步走”格式写几遍，而不是只看结论。

4.2 快速判断的经验技巧：先估量级，再抠细节

手算多了之后，我总结了一个很省事的办法：看到递归式先不急着算 log_b a，而是先问三个问题——合并代价 f(n) 像什么函数（常数、n、n log n、n^2）？叶子总数 n^c 大概是什么量级？这两个量级谁大、差多少？

如果 f(n) 是常数而叶子数是 n，那肯定是情况 1；如果 f(n) 和叶子数都是 n，那是情况 2；如果 f(n) 是 n^2 而叶子数是 n 或 n log n，那是情况 3。这个方法对常见递归式几乎 10 秒就能出答案。

另一个技巧是关于 log 因子的处理：只要 f(n) 和 n^c 的比值是 log^k n（不是 n^ε），就归入情况 2；只要比值对数多一个因子就多一个 log。做多了你会发现，绝大部分递归式其实都属于这三种情况中的某一类，真正需要抠“ε 到底存不存在”的题目已经算竞赛性质的了。

4.3 用主方法时，怎么顺手验证答案

主方法给了你一个结论，但你最好别直接拿去交差。我自己的习惯是，求完 T(n) = Θ(...) 之后，立刻用代入法或者小规模展开验证一下。不是要重新证明，而是取 n = 2, 4, 8 代进去，感受递归式增长方向对不对。

比如你算出 T(n) = Θ(n log n)，可以拿归并排序的例子快速验证：n = 8，2T(4) + 8 = 2 * 24 + 8？如果已知 T(4)=12，那 T(8)=32，约等于 n log n 的 5.3 倍量级，方向是对的。这个验证过程虽然简陋，但能拦住绝大多数“算错了指数”的低级错误——尤其是 a、b 填反的时候，只有代入数值才能暴露问题。

5. 常见误区与排查过程实录

5.1 误区一：把 a 和 b 认反，或者取整信息影响判断

我见过不止一个同学把 T(n) = 2T(n/4) + n 里的 b 看成 2，因为心里默认分治都是二分。但递归式里明明是 n/4，b 应该是 4。a、b 认错直接影响 c = log_b a，也就直接影响最终复杂度。比如刚才那个递归式，正确的 c = log_4 2 = 0.5，但有人算 c = log_2 2 = 1，把结论从 Θ(n^0.5 log n) 错判成 Θ(n log n) 甚至 Θ(n)。避免方法只有一个——每次都把标准形式写在纸上，逐项对号入座。

取整符号的问题，很多教材直接忽略。我的经验是：T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + n 这类递归式，主方法依然适用，结论不变，因为取整导致的误差最多是常数倍。但如果是 T(n) = T(n-1) + n 这种线性递推，虽然也叫递归，但它不是分治型，规模只是减 1 而不是除以 b，主方法完全失效，应该用累加法得到 Θ(n^2)。

5.2 误区二：忽视“多项式差距”，乱用情况 1 和 3

主方法的前后两种判定条件里，ε 是关键。很多人只记了“f(n) 比 n^c 小就用情况 1”，结果遇到 f(n) = n / log n、n^c = n 这种，误判成情况 1。实际上 f(n) 和 n^c 之比是 1/log n，它确实小于 1，但差距不是多项式差距，而是对数差距。对数增长速度小于任何 n^ε，所以这个递归式主方法套不了，需要用递归树：第一层 cost n/log n，之后每层减半，总代价约等于 Θ(n)。对，答案是 Θ(n)，但不是情况 1 的结论。

这类错误特别隐蔽，因为答案差的不多，但分析路径错了。我在帮人排查递归式时，第一步永远会问：“你确认过 f(n) 和 n^c 的差距是多项式级吗？”如果对方一脸茫然，那就先补这一课。

5.3 误区三：情况 3 忘掉正则条件，直接写结论

情况 3 之所以多了一个条件 a f(n/b) ≤ c' f(n)，是为了保证递归树的成本从根往下逐层递减。绝大多数正常的 f(n) 都能满足这个条件，但确实有反例。比如某些 f(n) 是振荡函数或分段函数时，正则条件可能失效，这时即使 f(n) 远大于 n^c，主方法结论也不成立。实际做题中这类递归式很少见，但我建议你在递归式中出现非常规 f(n)（带 sin、分段、随机项）时，主动检查一遍正则条件，不要偷懒。

还有一种情况值得注意：f(n) 是多项式但带有负系数，导致它在某段值为负。这违反了渐近正的前提，主方法就用不了。真正工程中出现这种递归式，往往意味着你的代价函数没建对模型，要回去重新审视递归式的写法和问题分解方式。

5.4 常见问题速查表

这张表基本覆盖了我辅导、面试、实际代码评审中碰到过的所有主方法翻车场景。你可以把它收藏起来当自查清单用。

6. 三种情况背后的原理：为什么主方法总是对的

6.1 用递归树重新发现主方法

如果只看定理，会感觉主方法是一个黑盒；但回到递归树，一切都很自然。递归树每一层有 a^k 个节点，每个节点的规模是 n/b^k，所以第 k 层的总成本是：

S_k = a^k f(n/b^k)

把 f 约等于 n^p 的形式代入（这里 p 代表 f 的增长指数），就得到 S_k ≈ a^k (n/b^k)^p = n^p (a / b^p)^k。注意比较 a 和 b^p 的大小，其实就是比较 p 和 log_b a = c 的大小：

• 如果 p < c，那 a / b^p > 1，S_k 随 k 递增，最大的层是最后一层，也就是叶子层，总成本约等于叶子数 n^c；
• 如果 p = c，那 a / b^p = 1，每层成本一样，总成本是层数 log n 乘以单层成本；
• 如果 p > c，那 a / b^p < 1，S_k 随 k 递减，最大的层是根节点层，总成本约等于 f(n)。

这个推导把三种情况本质上统一为“等比数列是递增、持平、还是递减”。我建议每个人都亲自推一遍这个公式，一旦推完，主方法就不再是死记硬背的三条规则，而是一个你自己能从零构造的结论。

6.2 情况 2 的 log 因子从哪来

很多人好奇，为什么情况 2 的复杂度会多出 log n。用上面的等比公式看，当 p = c 时，每层成本是同一个常数，递归树一共有 log_b n 层，总成本就是常数乘以层数，自然带 log n。如果 f(n) 本身还带 log^k n，那每层还要乘一个 log^k，再乘层数 log n，就变成 log^(k+1) n。

这解释了一个非常常见的困惑：为什么 T(n) = 2T(n/2) + n 是 O(n log n)，而 T(n) = 2T(n/2) + 1 是 O(n)。两者差别不在于“谁更快”，而在于每层成本是否和叶子层的增长速度持平。前者的 n 在每一层都出现，乘了 log n 层；后者的 1 只在叶子层的 n^1 面前不值一提。

6.3 主方法不是万能的：知道边界比知道公式更值钱

主方法失效的场景主要有三类：一是 f(n) 与 n^c 不可比，比如前面说的 n/log n 对 n；二是递归式里 a 或 b 非常数，比如随机化算法里的 T(n) = T(random number) + O(n)；三是 f(n) 增长快于任何多项式，比如 f(n) = 2^n。第一类推荐递归树，第二类需要概率分析加代入法，第三类往往说明你的问题分解方式有某种“爆炸性”代价，主方法不适用，但在实际系统里遇到这种复杂度，通常意味着算法设计本身需要改。

明白主方法的适用边界，能帮你节省大量时间。我遇到过一个实际项目，某同事在设计并行程序时写了一个分治合并逻辑，递归式是 T(n) = 2T(n/2) + n^1.5，用主方法秒出 Θ(n^1.5)，但这个结论太吓人了——合并代价 n^1.5 注定了数据规模稍大就跑不动。他后来反思，真正的优化点是合并里那个 O(n^1.5) 的操作，而不是递归拆分。这个例子说明主方法不仅算复杂度，还能帮你定位瓶颈在哪一层。

7. 影响范围与实际应用：从刷题、面试到工程选型

7.1 面试与笔试中主方法的核心价值

在算法面试和笔试场景里，主方法几乎是复杂度分析的默认工具。面试官问你“这个分治算法复杂度是多少”，你只要把递归式写出来，然后用主方法三步走，10 秒内给出结论，面试官就知道你对分治有系统训练。而且很多经典算法题的复杂度证明，其实就是主方法的直接应用，比如二分查找的 T(n) = T(n/2) + O(1) 属于情况 2？不对，这里要算一下：a = 1, b = 2, c = log_2 1 = 0，f(n) = O(1) = n^0，所以是情况 2，结论是 Θ(log n)。看，二分查找为什么是 log n，用主方法一算就通。

又比如快速排序的平均复杂度是 T(n) = 2T(n/2) + O(n)，直接套主方法得到 O(n log n)。当然快速排序最坏情况失衡时不满足这个递归式，但平均情况下的主方法结论完全够用。在面试中能把“为什么快排平均是 n log n、最坏却可能是 n^2”讲清楚，绝对加分。

7.2 算法设计中的复杂度选型

主方法的影响范围不止于纸面推导。当你设计一个新的分治算法，比如设计大规模排序、最近点对、大整数乘法、Strassen 矩阵乘法时，你可能要在两种分解策略之间选。策略 A 的递归式是 T(n) = 2T(n/2) + O(n)，策略 B 是 T(n) = 3T(n/3) + O(n log n)。两者都满足主方法形式：前者 Θ(n log n)，后者呢？a=3,b=3,c=1,f(n)=n log n，属于情况 2？f(n)=n^1 log^1 n，结果 Θ(n log^2 n)。策略 B 明显更差。有了这套比较方法，你不需要实际跑大数据量，就能在方案评审时推翻一个看似精巧但复杂度劣化的设计。

实际项目中我还常用主方法判断“加入缓存或不加入缓存”的影响。比如某个分治算法在每个递归节点做一次 O(1) 查询，那是情况 1，整体线性；如果把节点查询改成 O(n) 扫描，递归式变成情况 2，整体 O(n log n)。多出的一个 log 在大数据下可能就是跑 1 秒和跑 10 秒的差别。

7.3 学主方法的最佳姿势：先推一遍，再背结论

我的个人体会是，理解主方法一定要按“递归树推到公式”的顺序来，不要上来就背“三条判定”。推一遍之后，你会对 a、b、c 的意义有肌肉记忆，以后再看到任何递归式，大脑自动会浮现出“等比数列递增/持平/递减”的图形。这个方法比背公式牢固得多，因为万一哪天你忘了结论，你随时可以从递归树推回来。

接下来还想提一个容易忽略的学习技巧：把主方法、递归树、代入法三者看成一套工具。主方法是第一选择，因为它最快；主方法不适用时退到递归树，因为递归树能给出一个估计值；最后用代入法严格证明结论。三者配合使用，才是分治策略时间复杂度分析的正确打开方式。很多人只背主方法，遇到不能套的就束手无策，这是很可惜的。

8. 写在最后：一个帮你减少踩坑的小习惯

回到开头那个问题——一个分治算法写完以后，复杂度到底是多少？我的经验是，只要递归式没过分离谱，主方法 90% 的情况都能直接给出答案，真正的问题往往出在递归式本身没写对。我帮人 review 算法方案时，最常看到的情况不是不会用主方法，而是把递归式写错了：有的把 a 写成子问题翻倍的数量，却忘了子问题里还包含共享的中间计算；有的把 b 记成了 1/2，结果算出 c 变成负数；还有的在 f(n) 里漏掉了常数因子，把情况 2 判成了情况 1。

所以我最后想分享的习惯是：每次用主方法前，先把递归式大声念一遍——“规模 n 的问题，拆成 a 个规模 n/b 的子问题，额外开销是 f(n)”。念完再对照标准形式填空，基本不会填错。这个动作看起来很简单，但真的能让你少走很多弯路。不管是应付考试、刷 LeetCode 还是做系统设计，这套分析方法都值得你先花半小时亲手推一遍，之后你会发现自己对复杂度的直觉都会变得不一样。