一个分治算法写完、样例也跑通之后很多人第一个想问的问题不是“这个思路对不对”而是“这个算法的复杂度到底是多少”。如果你已经看过前面两篇关于代入法和递归树法的分析肯定有一个感受代入法要先猜再证递归树要一层层画碰上复杂一点的递归式都很费劲。这一篇专门讲第三件利器——用主方法求解递归式这也是分治策略时间复杂度分析里最像“套公式”的一步。主方法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 ≥ 1b 1f(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 2b 2c log_2 2 1基准线是 n^1 n如果 T(n) 3T(n/4) n那么 a 3b 4c log_4 3 ≈ 0.792基准线是 n^0.792如果 T(n) 4T(n/2) n那么 a 4b 2c 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 的“增长速度差”判断有两种标准一是判断差距是不是“多项式级别的差距”二是判断差距是不是“对数级别的差距”。因为主方法的三条情况恰好把这种比较分成了三大类情况 1f(n) 明显小于 n^c而且差距至少是多因子 n^εε 0这时叶子层占主导情况 2f(n) 和 n^c 差不多大允许差若干 log 因子这时每层成本基本一样情况 3f(n) 明显大于 n^c而且差距至少是多因子 n^ε同时满足某个正则约束这时根节点层占主导。初学的人最容易犯的错是把“f(n) n^c”直接当成情况 1。不对必须强调“多项式差距”。比如 f(n) n / 100n^c n虽然 n/100 和 n 有常数差距但指数相同这不是情况 1而是情况 2。又比如 f(n) n^0.5 log nn^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 2b 2c 1f(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^(k1) 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^(k1) n。最典型的例子就是归并排序T(n) 2T(n/2) O(n)。a 2b 2c 1f(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也属于情况 2k 1结果是 T(n) Θ(n log^2 n)。如果你在算法题里碰见类似结构可以直接套这个结论。这里要注意很多教材写情况 2 的结论是 Θ(n^c log n)其实那是 k 0 的特例。完整的结论是 Θ(n^c log^(k1) 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 3b 4c log_4 3 ≈ 0.792f(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这里 a2、b2、c1f(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 四个可直接照抄的完整推导案例我挑四个典型递归式把整个手算过程展开如下你可以照着这个顺序练习案例 1T(n) 9T(n/3) n第一步检查标准形式a 9b 3f(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 根本不够看。案例 2T(n) 2T(n/2) n前面说过c log_2 2 1f(n) n n^1正好是情况 2 的 k0。结论T(n) Θ(n log n)。这是归并排序和很多优秀分治算法的基础。案例 3T(n) 2T(n/4) n^0.5这里 a 2b 4c 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。案例 4T(n) 4T(n/2) n^2a 4b 2c log_2 4 2f(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 82T(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/4b 应该是 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 常见问题速查表现象可能原因处理方式递归式带取整担心不适用分治型递归式取整影响有限直接使用主方法结论通常不变T(n) T(n-1) n 无法套主方法不是分治型属于线性递推改用累加法/迭代展开f(n) 与 n^c 差了一个 log 因子不是多项式差距退回递归树法或换元法a、b 填反结果差了一个指数标准形式没有写清楚逐项抄写并用小数值验证f(n) 增长速度非常规阶乘、振荡不满足渐近正或多项式型回避主方法考虑递归树/代入法情况 3 忘执法正则条件只看了大小关系补验 a f(n/b) ≤ c f(n)这张表基本覆盖了我辅导、面试、实际代码评审中碰到过的所有主方法翻车场景。你可以把它收藏起来当自查清单用。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 1S_k 随 k 递增最大的层是最后一层也就是叶子层总成本约等于叶子数 n^c如果 p c那 a / b^p 1每层成本一样总成本是层数 log n 乘以单层成本如果 p c那 a / b^p 1S_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^(k1) 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 0f(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)后者呢a3,b3,c1,f(n)n log n属于情况 2f(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 还是做系统设计这套分析方法都值得你先花半小时亲手推一遍之后你会发现自己对复杂度的直觉都会变得不一样。