三种解递推式的武器：递归树、代入法、主定理

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

面对一个递推式，工程上通常三步走：

① 递归树：先画树、加各层代价，快速"猜"出 $\Theta$ 阶。它最直观，也能处理主定理卡不到的边界情形。

② 代入法：用猜出的阶做归纳假设（如 $T(n)\le c n\log n$），严格证明上下界。它是"证明工具"，不是"猜工具"。

③ 主定理：当递推正好是 $aT(n/b)+f(n)$ 时，直接查三情况，省去画树与归纳。它是前两者的"提速包"。

参考代码：把三种思路写进一个判定器

def solve(a, b, f_order):
    """f_order: 'lt'/'eq'/'gt' 表示 f(n) 相对 n^{log_b a} 的关系。"""
    if f_order == 'lt':
        return "情况1: Θ(n^{log_b a})    # 递归树叶子主导"
    if f_order == 'eq':
        return "情况2: Θ(n^{log_b a} log n)  # 各层均衡，代入法证"
    return "情况3: Θ(f(n))             # 根主导，需正则性"

print(solve(2, 2, 'eq'))     # 归并
print(solve(1, 2, 'eq'))     # 二分

记住：主定理能套就套（最快），套不上就回到递归树 + 代入法。三者互补，没有谁取代谁。

关联推荐

• 算法与问题求解入门（KU） — 递归与复杂度的基本功
• 插入、选择、冒泡排序（KU） — 排序递推都是练手好题
• 动态规划：从斐波那契到背包 — 另一种"递推"，但不属分治型