主定理到底在算什么：递归树一眼看懂

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

很多人学主定理（Master Theorem）靠背三句话，但一遇到变体就懵。其实主定理背后只有一个直觉：把递归展开成一棵树，把每一层的代价加起来，看哪一层最"重"。这一步叫递归树（recursion tree）。

递归树怎么画

形如 $T(n)=aT(n/b)+f(n)$ 的递推：根代表原问题，代价 $f(n)$；它分裂出 $a$ 个子问题，每个规模 $n/b$；如此反复，直到规模降到 1（叶子）。第 $i$ 层有 $a^i$ 个节点，每个代价 $f(n/b^i)$，叶子层在第 $\log_b n$ 层。

总代价 = 各层代价之和

把每层总代价相加：层 $i$ 的总代价是 $a^i\cdot f(n/b^i)$。哪个量"主导"了这个和，复杂度就是它。这就自然引出主定理三情况——比较 $f(n)$ 与临界值 $n^{\log_b a}$（叶子总规模）。

参考代码：把递归树"加"出来验证

def tree_sum(n, a, b, f):
    total, lvl, size = 0, 0, n
    while size >= 1:
        total += (a ** lvl) * f(size)   # 第 lvl 层总代价
        size //= b
        lvl += 1
    return total

# 归并排序 a=2,b=2,f(n)=n：每层都是 n，叠 log n 层
print(tree_sum(8, 2, 2, lambda x: x))   # 40 = 8*log2(8) + 8 叶 ≈ Θ(n log n)

所以主定理不是魔法，它只是把"递归树求和"做成了分情况速查。理解了树，你就再也不用死记公式。

关联推荐

• 插入、选择、冒泡排序（KU） — 排序是分治的主战场，主定理用得最多
• 算法与问题求解入门（KU） — 先建立算法与复杂度的整体观
• 二分查找：20 行代码里藏着的对数级智慧 — 下一个用主定理一眼看穿的算法