递推式与主定理：为什么分治算法的时间复杂度一算就准

图：归并排序的递归树——每层代价恒为 n，叠 log₂n 层得 Θ(n log n)

图：主定理按 f(n) 与临界值 n^{log_b a} 的大小分三种情况

本节你将能

读完这篇，你应该能：把归并排序、快速排序、二分查找的递归式写成 $T(n)=aT(n/b)+f(n)$ 的形式；套用主定理的三情况立刻写出 Θ 结果；用递归树直观验证；并识别出"主定理管不到"的递推式。

直觉模型：递归树

分治算法把规模为 $n$ 的问题拆成 $a$ 个规模为 $n/b$ 的子问题，每层合并代价为 $f(n)$。把所有层的代价画成一棵树：根节点代价 $f(n)$，第 $i$ 层有 $a^i$ 个节点、每个代价 $f(n/b^i)$，叶子层在第 $\log_b n$ 层、共 $a^{\log_b n}=n^{\log_b a}$ 个叶子。把每层的代价加起来，就是总复杂度。

以归并排序为例：$a=2,b=2,f(n)=\Theta(n)$。每一层总代价都是 $2^i \cdot \Theta(n/2^i)=\Theta(n)$，共 $\log_2 n$ 层，叶子 $n$ 个（每个 $\Theta(1)$），于是总数为 $\Theta(n\log n)+\Theta(n)=\Theta(n\log n)$。这就是上图递归树的含义。

核心要点：主定理三情况

令临界值 $g(n)=n^{\log_b a}$，比较 $f(n)$ 与 $g(n)$：

情况 1：若 $f(n)=O(n^{\log_b a-\varepsilon})$（多项式小于临界值），则 $T(n)=\Theta(n^{\log_b a})$。叶子层主导。

情况 2：若 $f(n)=\Theta(n^{\log_b a}\log^k n)$，则 $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$。（$k\ge 0$）各层均衡，多乘一个对数。

情况 3：若 $f(n)=\Omega(n^{\log_b a+\varepsilon})$（多项式大于临界值）且满足正则性 $a f(n/b)\le c f(n)$（$c<1$），则 $T(n)=\Theta(f(n))$。根层主导。

参考代码：递归树代价求和（验证主定理）

下面用代码把"每层代价相加"算一遍，验证归并排序的 $\Theta(n\log n)$：

def recursion_tree_cost(n, a, b, f):
    """对 T(n)=a*T(n/b)+f(n) 做递归树求和（假设 n 是 b 的幂）。
    f 是每层单个节点的代价函数；返回总代价（以 f 的调用次数计）。"""
    total = 0
    level = 0
    size = n
    while size >= 1:
        nodes = a ** level          # 第 level 层节点数 = a^level
        total += nodes * f(size)    # 该层总代价
        size //= b                  # 子问题规模缩小
        level += 1
    return total

# 归并排序：a=2, b=2, f(n)=n（合并代价线性）
cost = recursion_tree_cost(8, 2, 2, lambda x: x)
print(cost)   # 8+8+8+8(叶子) = 8*log2(8) + 8 = 32+8 = 40 ≈ Θ(n log n)

参考代码：主定理判定器

把三种情况写成可运行的判定逻辑，输入 $a,b$ 与 $f(n)$ 的阶，输出属于哪种情况：

def master_case(a, b, f_order):
    """f_order: f(n) 相对 n^{log_b a} 的关系，取值 'lt'/'eq'/'gt'。
    返回主定理情况与结论阶。"""
    crit = a ** (1 / b)              # n^{log_b a} 的指数（仅示意阶）
    if f_order == 'lt':
        return "情况1", f"Θ(n^{round(__import__('math').log(a, b), 2)})"
    if f_order == 'eq':
        return "情况2", "Θ(n^{log_b a} log n)"
    return "情况3", "Θ(f(n))"

print(master_case(2, 2, 'eq'))   # ('情况2', 'Θ(n^{log_b a} log n)') 归并
print(master_case(2, 2, 'gt'))   # ('情况3', 'Θ(f(n))') 如 T(n)=2T(n/2)+n^2

常见误区

主定理只适用于"除法型"递推 $aT(n/b)+f(n)$。像 $T(n)=T(n-1)+n$（减法型）、$T(n)=2T(n/2)+n/\log n$（临界处负指数）、$T(n)=T(\sqrt{n})+1$（根号递归）都不在主定理的适用范围内，硬套会出错。下一节热点会专门拆解。