主定理（Master Theorem）是算法分析中绕不开的一座桥——它不生产代码，但决定你写的递归函数到底快不快；它不参与调试，却在你提交作业前最后一秒告诉你：这个时间复杂度，老师会扣分。我带过七届算法课，也帮三十多个团队做过性能压测方案，见过太多人把T(n) = 2T(n/2) + n背成“O(n log n)”就收工，结果上线后发现数据量翻十倍，响应延迟飙到8秒——不是公式错了，是根本没搞懂主定理的适用边界、隐含前提、以及那三个Case背后的真实数学约束。
主定理不是速查表，而是一套有严格定义域的“递归时间复杂度判别器”。它只适用于形如 T(n) = aT(n/b) + f(n) 的分治型递推式，其中 a ≥ 1, b > 1 为常数，f(n) 是渐近正函数。这三个参数不是随便代入的符号，而是对实际算法结构的精确建模：a 是子问题个数，b 是规模缩减因子，f(n) 是合并开销。很多人卡在第一步——连自己写的递归到底符不符合主定理的前提都判断不清，就急着套Case 1/2/3，结果算出来一个“O(n²)”，实际运行却是指数级爆炸。这就像用欧姆定律去算交流电路里的阻抗，公式没错，但前提错了。
这篇内容专为两类人准备：一类是正在啃《算法导论》第三章、被Case 2中那个log_b a 和 log n 的幂次关系绕晕的本科生；另一类是写完归并排序、快速排序、线段树或FFT封装后，想真正说清“为什么它是O(n log n)”而不是“书上这么写的”的工程师。我不讲证明（那属于数学分析课），只讲怎么用、在哪用、为什么这里不能用、换种写法为什么又可以用了——全是我在真实项目里反复验证过的判断逻辑、手算技巧和避坑清单。下面从最常被忽略的“适用性诊断”开始，一层层拆开主定理的壳。
1. 主定理的适用边界与结构建模本质
1.1 什么情况下根本不能用主定理？
这是所有误用的起点。主定理不是万能钥匙，它只开三类门：等规模划分、固定子问题数、合并开销可显式表达。一旦偏离这三条，强行套用就会得出荒谬结论。我整理了6种典型“伪分治”结构，它们看起来像T(n) = aT(n/b) + f(n)，实则完全不满足主定理前提：
规模缩减不均匀：比如快排最坏情况下的 T(n) = T(n−1) + T(1) + Θ(n)，这里子问题规模是 n−1 和 1，不是 n/b 形式，b 不存在；更隐蔽的是随机化快排的期望递推式 E[T(n)] = (1/n)∑_{k=0}^{n−1} [E[T(k)] + E[T(n−1−k)]] + Θ(n)，它连确定性递推都不是，主定理直接失效。
子问题个数不固定：二分搜索看似是 T(n) = T(n/2) + Θ(1)，但它只递归进入一个分支，a = 1；而某些动态规划优化（如四边形不等式优化）中，决策点数量随输入变化，a 不是常数，主定理无法建模。
f(n) 不是渐近正函数：比如 T(n) = 2T(n/2) + sin(n)，sin(n) 在无穷区间内变号且无下界，不满足 f(n) = Ω(n^ε)（ε > 0）这一隐含要求；实际工程中更常见的是 T(n) = 4T(n/2) + n² log n，这里 f(n) 含对数因子，已超出标准主定理覆盖范围，必须升级到“主定理推广形式”或Akra-Bazzi方法。
b 不是常数：某些自适应分治（如按数据分布切分的桶排序变种），划分点依赖于输入值，导致 n/b 中的 b 随n波动，此时递推式本质是非齐次变系数，主定理的数学基础崩塌。
递归深度非对数级：T(n) = T(√n) + Θ(1) 这类“平方根递归”，每次规模开方，深度是 log log n 而非 log_b n，代入主定理会得到错误指数；正确解法是变量替换 m = log n，转化为线性递推。
存在额外控制流开销：T(n) = 2T(n/2) + n + g(n)，其中 g(n) 是条件判断、内存分配等不可忽略的附加操作，若 g(n) 与 n 同阶但相位不确定（如g(n)=n·[n为质数]），则 f(n) 失去渐近光滑性，主定理的极限比较失效。
提示：判断能否用主定理，第一反应不该是“套哪个Case”，而是画一棵递归调用树——看每一层的子问题规模是否严格按 b 倍等比缩小，子问题个数是否恒为 a，合并代价是否能统一写成 f(n)。树画出来歪歪扭扭，就别碰主定理。
1.2 a、b、f(n) 的物理意义与建模陷阱
很多初学者把 a、b 当作纯数学参数，却忽略了它们对应着代码里的具体结构。我们以归并排序为例，逐项还原：
a = 2：不是“因为要分两半”，而是每次递归调用恰好产生两个子调用。检查你的 mergeSort(arr, l, r) 函数：是否只调用 mergeSort(arr, l, m) 和 mergeSort(arr, m+1, r)？如果有第三个分支（比如异常处理时的 fallback 排序），a 就不再是2。
b = 2：不是“除以2”，而是子问题规模严格等于原规模除以常数 b。注意：当数组长度为奇数时，m = floor((l+r)/2)，右半段长度可能是 ⌈n/2⌉，此时两个子问题规模分别为 ⌊n/2⌋ 和 ⌈n/2⌉，严格来说不满足 n/b。但因 ⌈n/2⌉ ≤ n/2 + 1，且主定理对低阶项不敏感，工程上仍可接受。真正的雷区是像“按首字母A-M/N-Z分组”的字符串分治，分组比例随数据分布剧烈波动，b 就不是常数。
f(n) = Θ(n)：这是合并步骤的代价，即 merge() 函数的执行时间。关键在于：f(n) 必须是“仅依赖于当前层输入规模n”的函数。如果 merge 过程中还要做一次二分查找（如归并时去重），f(n) 就变成 Θ(n log n)，整个递推式变为 T(n) = 2T(n/2) + Θ(n log n)，此时属于 Case 2 的扩展情形，需重新比对 log_b a 与 k 的关系（后文详述）。
我曾遇到一个真实案例：某推荐系统用分治计算用户相似度，递归函数写成 T(n) = 4T(n/2) + n²，表面看是 Case 1（log₂4 = 2，f(n)=n²，ε=0.1），应得 O(n²)。但实际代码中，合并阶段要遍历所有子结果对做向量点积，其复杂度是 (n/2)² × (n/2)² = n⁴/16 —— 也就是说，f(n) 被严重低估了。正确建模应为 T(n) = 4T(n/2) + Θ(n⁴)，此时 log₂4 = 2 < 4，属 Case 3，结果是 O(n⁴)。上线后QPS暴跌，根源就在 f(n) 的建模失真。
1.3 主定理的数学根基：递归树展开与几何级数收敛性
主定理的三个Case，本质是递归树各层代价总和的主导项判别。我们以 T(n) = aT(n/b) + f(n) 展开：
- 根节点代价：f(n)
- 第1层：a 个节点，每个代价 f(n/b)，总代价 a·f(n/b)
- 第2层：a² 个节点，每个代价 f(n/b²)，总代价 a²·f(n/b²)
- …
- 第i层：aⁱ 个节点，每个代价 f(n/bⁱ)，总代价 aⁱ·f(n/bⁱ)
- 树高：log_b n（因 n/bⁱ = 1 ⇒ i = log_b n）
总代价 T(n) = Σ_{i=0}^{log_b n} aⁱ·f(n/bⁱ)
主定理的精妙之处，在于将这个求和式按 f(n) 的增长阶与 aⁱ 的衰减/增长关系分类：
Case 1（f(n) 多项式小于主导项）：当 f(n) = O(n^{log_b a − ε})，ε > 0，则 aⁱ·f(n/bⁱ) 随 i 增大而快速衰减，总和由叶节点主导，即 a^{log_b n} = n^{log_b a} 项胜出。
Case 2（f(n) 与主导项同阶）：当 f(n) = Θ(n^{log_b a} log^k n)，k ≥ 0，则每层代价近似相等（aⁱ·(n/bⁱ)^{log_b a} = n^{log_b a}），共 log_b n 层，总和为 Θ(n^{log_b a} log^{k+1} n)。
Case 3（f(n) 多项式大于主导项）：当 f(n) = Ω(n^{log_b a + ε}) 且满足正则条件 af(n/b) ≤ cf(n)，c < 1，则根节点 f(n) 项压倒一切，T(n) = Θ(f(n))。
注意：Case 2 中的 log^k n 是关键扩展。标准教材只讲 k = 0（即 f(n) = Θ(n^{log_b a})），但现实中大量算法含对数因子，如 Strassen 矩阵乘法 T(n) = 7T(n/2) + Θ(n² log n)，这里 log_b a = log₂7 ≈ 2.807，f(n) = n² log n = O(n^{2.807−ε})？不成立，因为 n² log n 增长慢于 n^{2.807}，但快于任何 n^{2.807−ε}（ε>0）。此时需用推广形式：若 f(n) = Θ(n^{log_b a} log^k n)，则 T(n) = Θ(n^{log_b a} log^{k+1} n)。Strassen 中 k = 1，故 T(n) = Θ(n^{log₂7} log² n)。
实操心得：手算时别死记Case编号，直接展开前3层，观察 aⁱ·f(n/bⁱ) 的变化趋势。如果每层代价大致持平（如归并排序：n → 2×(n/2)=n → 4×(n/4)=n），就是Case 2；如果快速下降（如二分搜索：n → 1×(1)=1），是Case 1；如果根节点远大于下一层（如T(n)=T(n/2)+n²：n² vs (n/2)²=n²/4），是Case 3。这种直觉比背公式可靠十倍。
2. 三大Case的深度解析与参数临界点计算
2.1 Case 1：子问题主导型——何时“分”比“合”更重要？
Case 1 的判定条件是 f(n) = O(n^{log_b a − ε})，ε > 0。核心是找到这个 ε，它代表 f(n) 比理论主导项低多少阶。很多人卡在“如何选ε”，其实ε不需要精确值，只需存在性证明。
以 T(n) = 9T(n/3) + n 距离为例：
- log_b a = log₃9 = 2
- f(n) = n = n¹
- 需验证 n¹ = O(n^{2−ε})，即找 ε 使 1 ≤ 2−ε ⇒ ε ≤ 1
- 取 ε = 0.5，则 n¹ = O(n^{1.5}) 显然成立
结论：T(n) = Θ(n²)
但若 f(n) = n^{1.999}，log_b a = 2，此时 n^{1.999} = O(n^{2−ε}) 要求 ε ≤ 0.001，依然成立，T(n) = Θ(n²)。只有当 f(n) = n² 或更高，才退出Case 1。
真正的难点在边界模糊区：f(n) = n² / log n。它比 n² 小，但小得不够“多项式”——因为 n² / log n / n^{2−ε} = n^ε / log n → ∞（当 n→∞），不满足 O(n^{2−ε})。此时主定理失效，需用Akra-Bazzi或递归树精确求和。
我处理过一个图像分割算法，递推式 T(n) = 4T(n/2) + n² / log n。客户坚持要用主定理，我现场展开：
- 第i层代价：4ⁱ × (n/2ⁱ)² / log(n/2ⁱ) = n² / log(n/2ⁱ)
- 总代价：Σ_{i=0}^{log₂n} n² / log(n/2ⁱ) = n² × Σ_{j=0}^{log₂n} 1 / log(2ʲ) （令 j=log₂n−i）
- log(2ʲ) = j log 2，求和式 ≈ Σ 1/j，即调和级数 H_{log n} = Θ(log log n)
- 故 T(n) = Θ(n² log log n)
这超出了标准主定理，但通过递归树可解。记住：当 f(n) 含 log、log log 等慢变因子时，先怀疑Case 1/2/3是否适用，再决定是否升级工具。
2.2 Case 2：平衡型——log因子的精确计数与k值判定
Case 2 是最容易被简化的部分。标准表述“f(n) = Θ(n^{log_b a}) ⇒ T(n) = Θ(n^{log_b a} log n)”遗漏了关键细节：log的幂次k必须与f(n)中log的幂次严格匹配。
考虑 T(n) = 2T(n/2) + n log² n：
- log_b a = log₂2 = 1
- f(n) = n log² n = Θ(n¹ log² n)，故 k = 2
- 主定理推广形式给出 T(n) = Θ(n¹ log^{2+1} n) = Θ(n log³ n)
验证：递归树第i层代价 = 2ⁱ × (n/2ⁱ) × log²(n/2ⁱ) = n × [log n − i log 2]²
总代价 = n × Σ_{i=0}^{log₂n} (log n − i)²
令 m = log₂n，则 Σ_{i=0}^m (m−i)² = Σ_{j=0}^m j² = m(m+1)(2m+1)/6 = Θ(m³) = Θ(log³ n)
故 T(n) = Θ(n log³ n)，与主定理一致。
但若 f(n) = n log n log log n，此时 log 的复合结构超出主定理能力，必须回归递归树或Akra-Bazzi。
另一个陷阱是log底数无关性。有人纠结“log₂n 还是 ln n”，其实所有对数底数只差常数倍，Θ记号下等价。但计算具体常数时（如性能调优），log₂n 更贴近计算机操作（位运算、内存地址），而自然对数 ln n 在数学推导中更简洁。
注意事项：Case 2 中的 log^{k+1} n 是“层高 × 每层代价”的体现。每层代价≈n^{log_b a}，层数=log_b n，但若f(n)本身含log^k n，则每层代价含log^k (n/bⁱ) ≈ (log n − i log b)^k，求和后升幂。所以k不是随便猜的，必须从f(n)中准确提取。
2.3 Case 3：合并主导型——正则条件的实操验证与反例
Case 3 要求两点：f(n) = Ω(n^{log_b a + ε}) 且 af(n/b) ≤ cf(n)（c < 1）。前者易验，后者常被忽略，却决定结论是否成立。
以 T(n) = 3T(n/4) + n 为例：
- log_b a = log₄3 ≈ 0.792
- f(n) = n = Ω(n^{0.792+ε})，取 ε = 0.1，成立
- 验证正则条件：a f(n/b) = 3 × (n/4) = 0.75n，取 c = 0.8，则 0.75n ≤ 0.8n，成立
- 故 T(n) = Θ(n)
但若 T(n) = 3T(n/4) + n log n：
- f(n) = n log n，log_b a + ε ≈ 0.792 + 0.1 = 0.892，n log n = Ω(n^{0.892})？是，因为 log n 增长慢于任何 n^δ（δ>0）
- 正则条件：a f(n/b) = 3 × (n/4) log(n/4) = 0.75n (log n − log 4) = 0.75n log n − 0.75n log 4
要求 ≤ c n log n，即 0.75n log n − 0.75n log 4 ≤ c n log n
整理得 (0.75 − c) log n ≤ 0.75 log 4
当 n 足够大，log n → ∞，左边无界，除非 c ≥ 0.75，但 c 必须 < 1 且对所有 n 成立。取 c = 0.76，则当 n > 4^{0.75/(0.76−0.75)} ≈ 4^{75} 时，不等式失效。故正则条件不满足。
此时主定理Case 3不适用，需用递归树：
第i层代价 = 3ⁱ × (n/4ⁱ) log(n/4ⁱ) = n (3/4)ⁱ (log n − i log 4)
总代价 = n log n Σ (3/4)ⁱ − n log 4 Σ i (3/4)ⁱ
两个级数均收敛（公比3/4<1），故 T(n) = Θ(n log n)，而非 Θ(n log n) 的简单结论——这里f(n)本身已是主导，但主定理无法直接给出。
实操技巧：验证正则条件时，不要代入具体n，而是化简 af(n/b)/f(n) 的表达式。若该比值极限 < 1（如上例中 lim_{n→∞} [3×(n/4)log(n/4)] / [n log n] = 3/4 < 1），则存在c满足条件；若极限=1（如f(n)=n），需检查是否严格≤c<1；若极限>1，则Case 3彻底失效。
3. 主定理的实战应用：从教科书到工业级代码
3.1 经典算法复盘：归并排序、Strassen、线段树
我们用主定理重算三个标杆算法，重点揭示参数建模中的易错点。
归并排序 T(n) = 2T(n/2) + Θ(n)
- a=2, b=2, log_b a = 1
- f(n) = Θ(n¹)，故 k=0，属Case 2
- T(n) = Θ(n¹ log^{0+1} n) = Θ(n log n)
- 关键确认：合并步骤的for循环确实是Θ(n)，不随数据有序性变化（最坏/平均都是n次比较+拷贝）
Strassen矩阵乘法 T(n) = 7T(n/2) + Θ(n²)
- a=7, b=2, log_b a = log₂7 ≈ 2.807
- f(n) = Θ(n²) = O(n^{2.807−ε})，取ε=0.1，成立 ⇒ Case 1
- T(n) = Θ(n^{log₂7}) ≈ Θ(n^{2.807})
- 注意：这里的Θ(n²)是7次矩阵加减的代价，不是传统乘法的n³。若实现时用朴素加法（而非位运算优化），常数因子可能让n^{2.807}在n<1000时不如朴素O(n³)快——主定理只管渐近，不管常数。
线段树区间查询 T(n) = 2T(n/2) + Θ(1)
- a=2, b=2, log_b a = 1
- f(n) = Θ(1)，即O(n^{1−ε})，取ε=0.5 ⇒ Case 1
- T(n) = Θ(n¹) = Θ(n)？错！这是典型建模错误。
正确建模：线段树高度h = ⌈log₂n⌉，每次查询最多访问2h个节点，故T(n) = O(log n)。问题出在递推式——它不是T(n) = 2T(n/2) + Θ(1)，而是T(n) ≤ 2T(n/2) + Θ(1)，且实际递归只走一条路径（或两条），a不是常数2。正确递推应为T(n) = T(n/2) + Θ(1)（单路径）或T(n) = T(n/2) + T(n/2) + Θ(1)（双路径），但后者仅在区间跨越中点时发生，概率模型下期望为O(log n)。主定理在此不适用，必须用递归树或摊还分析。
3.2 工业级场景：分布式任务调度与MapReduce作业
在大数据场景，主定理用于估算作业延迟。例如一个MapReduce任务：
- Map阶段：将n条记录分发到a个mapper，每个处理n/b条，耗时f_map(n)
- Reduce阶段：a个reducer聚合结果，每个输入规模约n/a，合并耗时f_reduce(n)
整体递推式常为 T(n) = aT(n/b) + f_map(n) + f_reduce(n)。我们分析一个真实日志分析流水线：
T(n) = 10T(n/10) + n^{0.8}
- a=10, b=10, log_b a = 1
- f(n) = n^{0.8} = O(n^{1−ε})，ε=0.2 ⇒ Case 1
- T(n) = Θ(n¹) = Θ(n)
但实测发现，当n从10⁶增至10⁷，运行时间从12s增至125s（≈10.4倍），接近线性。这验证了主定理结论。然而，当加入实时校验（f(n) = n^{0.8} + n^{0.9}），log_b a = 1，n^{0.9} = O(n^{1−ε})仍成立，T(n) = Θ(n)不变。但若校验升级为全量扫描（f(n) = n），则f(n) = Θ(n¹)，进入Case 2，T(n) = Θ(n log n)，n增10倍，时间增≈10×log₁₀10=10×1=10倍，与之前一致；但若n增100倍，Case 1预测增100倍，Case 2预测增100×log₁₀100=100×2=200倍——差异在大尺度才显现。
经验：在分布式系统中，b往往不是理想2或10，而是集群节点数（如16、32、64）。此时log_b a可能非整数，但主定理依然有效。计算log₃₂16 = log₂16 / log₂32 = 4/5 = 0.8，若f(n)=n^{0.7}，则属Case 1；若f(n)=n^{0.85}，则属Case 3。用计算器算log值比心算可靠。
3.3 代码级建模：如何从函数签名反推递推式？
给定一段递归代码，如何写出正确的T(n)？我总结四步法：
识别输入规模n：通常是数组长度、数字位数、图节点数。注意：若函数有多个参数（如merge(arr, l, r)），n = r−l+1。
统计子调用个数a：遍历所有递归调用语句，数常数个数。如quicksort中partition后调用两次，a=2；若加了尾递归优化（只调一次），a=1。
确定规模缩减因子b：看子调用的参数。若为arr[l..m]且m = l + (r−l)/2，则左半段长≈n/2，b=2；若m = l + sqrt(r−l)，则b非恒定，主定理失效。
量化合并开销f(n)：分析非递归部分。重点包括：
- 循环次数（如merge中的while循环，最坏n次）
- 内存分配（new int[n] 是Θ(n)）
- 条件判断（if (n < 10) return; 是Θ(1)，但若含复杂校验，需计入）
案例：一个树形DP函数
int dfs(Node root) { if (root == null) return 0; int left = dfs(root.left); // 子问题1 int right = dfs(root.right); // 子问题2 return left + right + root.val; // 合并：Θ(1)操作 }- n = 树节点数（假设满二叉树，但主定理要求b恒定，此处子树规模不均，严格说不适用；若限定为完美二叉树，则左右子树各n/2，a=2, b=2）
- f(n) = Θ(1)（加法和赋值）
- T(n) = 2T(n/2) + Θ(1) ⇒ Case 1 ⇒ T(n) = Θ(n)
这与树遍历O(n)一致。但若合并步骤改为“计算左右子树节点数乘积”，则f(n) = Θ(1)，不变；若改为“对左右子树结果做排序合并”，f(n) = Θ(n)，则T(n) = 2T(n/2) + Θ(n) ⇒ Case 2 ⇒ Θ(n log n)。
4. 常见问题与排查技巧实录
4.1 “套公式结果与实测不符”的7种根源
| 问题现象 | 根本原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 理论O(n log n)，实测接近O(n²) | f(n)被严重低估（如合并含嵌套循环） | 用profiler抓热点函数，看合并步骤实际耗时占比 | 重构合并逻辑，或改用迭代/非分治方案 |
| Case 1得出Θ(n²)，但n翻倍时间只增1.8倍 | 输入未达渐近区（n太小，常数项主导） | 测试n=10³,10⁴,10⁵,10⁶，画log-log图看斜率 | 增大n，或用实测拟合代替理论 |
| Case 2预测Θ(n log n)，实测Θ(n) | f(n)实际为Θ(1)，非Θ(n)（如误将初始化计入f(n)） | 拆分递归体，单独计时合并段 | 修正f(n)建模，重算Case |
| 所有Case都不满足 | f(n)含振荡项（如sin(n)）或慢变因子（log log n） | 计算af(n/b)/f(n)极限，观察是否收敛 | 改用递归树展开或Akra-Bazzi方法 |
| 并行环境下理论不准 | 主定理假设串行，未计通信/同步开销 | 添加计时点，分离计算与通信时间 | 引入并行主定理（如Brent定理）或实测建模 |
| 递归深度超栈限制 | log_b n过大（如b=2,n=2³²） | 监控栈帧数，或设递归深度断点 | 改为迭代，或增大栈空间 |
| 多线程下加速比低于预期 | a被硬件线程数限制，非理论a值 | 用top/htop看CPU利用率 | 调整并发数，或用工作窃取优化负载均衡 |
4.2 手算速查表：5分钟定位Case类型
给定T(n) = aT(n/b) + f(n)，按此流程：
- 计算 log_b a（用换底公式：log_b a = ln a / ln b）
- 将f(n)写成 n^k · (log n)^m 形式（k,m为实数）
- 比较 k 与 log_b a：
- 若 k < log_b a − 0.01 ⇒ Case 1
- 若 |k − log_b a| < 0.01 ⇒ 进入Case 2分支
- 若 m ≥ 0 ⇒ T(n) = Θ(n^{log_b a} log^{m+1} n)
- 若 f(n) 含 log log n 等 ⇒ 递归树
- 若 k > log_b a + 0.01 ⇒ 进入Case 3分支
- 计算 lim_{n→∞} af(n/b)/f(n)
- 若极限 < 1 ⇒ Case 3，T(n) = Θ(f(n))
- 若极限 = 1 ⇒ 主定理失效，用递归树
- 若极限 > 1 ⇒ 不可能（f(n)增长太快，递推式不合理）
- 计算 lim_{n→∞} af(n/b)/f(n)
实测心得：我用Python写了个主定理速判脚本，输入a,b,f_expr（如"n**2 * log(n)"），自动输出Case和复杂度。核心是sympy库解析表达式，计算极限。但提醒：脚本只是辅助，真正理解必须亲手展开递归树——就像学游泳，看教程永远不如跳下水。
4.3 面试高频题拆解：T(n) = 2T(n/2) + n/log n
这是检验主定理深度的经典题。表面看f(n) = n/log n，log_b a = 1，n/log n 比 n 小，似乎Case 1。但n/log n / n^{1−ε} = n^ε / log n → ∞，不满足O(n^{1−ε})。同样，n/log n / n = 1/log n → 0，不满足Ω(n^{1+ε})，Case 3也不成立。故属“主定理灰色地带”。
解法：递归树
- 第i层代价 = 2ⁱ × (n/2ⁱ) / log(n/2ⁱ) = n / log(n/2ⁱ)
- 总代价 = n × Σ_{i=0}^{log₂n} 1 / log(n/2ⁱ) = n × Σ_{j=0}^{log₂n} 1 / log(2ʲ) = n × Σ_{j=0}^{log₂n} 1 / (j log 2)
- Σ_{j=1}^{m} 1/j = H_m = Θ(log m) = Θ(log log n)
- 故 T(n) = Θ(n log log n)
这个结果说明：当f(n)比多项式慢但比常数快时，log log n会冒出来。在数据库索引合并、某些分形算法中常见此类行为。
最后分享个小技巧：下次看到含log的f(n)，先问自己——这个log是来自循环次数（如for i=1 to log n），还是来自数据结构深度（如BST高度）？前者通常可纳入主定理，后者往往暗示需要更精细的模型。主定理是利器，但不是全部；它教会你提问，而答案常在递归树的枝叶间。
