主定理管不到的情况：这些递推式别硬套

图：三类主定理失效/需小心的递推式，须换方法（求和/换元）

主定理有清晰的前提：递推必须是 $T(n)=aT(n/b)+f(n)$，且 $f(n)$ 与临界值 $n^{\log_b a}$ 是多项式差距。以下三类会"卡不到"：

1. 减法型：$T(n)=T(n-1)+\Theta(n)$

规模每次减 1 而非除以 $b$，主定理前提不满足。直接求和：$T(n)=\sum_{i=1}^n \Theta(i)=\Theta(n^2)$。背公式会误判成 $\Theta(n)$。

2. 临界处负指数：$T(n)=2T(n/2)+n/\log n$

$n/\log n$ 比临界值 $n$ 只少一个对数（亚多项式），三情况都精确卡不到。展开递归树得 $\Theta(n\log\log n)$。

3. 根号型：$T(n)=T(\sqrt n)+\Theta(1)$

换元 $m=\log_2 n$，则 $T(2^m)=T(m)+1$，变成关于 $m$ 的加法递推，解得 $\Theta(\log\log n)$。

参考代码：减法型用求和而非主定理

def subtractive(n):
    total, k = 0, n
    while k > 0:                 # T(n)=T(n-1)+k，逐层求和
        total += k
        k -= 1
    return total                 # = n(n+1)/2 = Θ(n^2)，不是 Θ(n)

print(subtractive(5))           # 15

结论：凡"非除法型"或"临界处负指数"，先回到递归树/求和/换元，别硬套主定理。

关联推荐

• 插入、选择、冒泡排序（KU） — 对照"能套主定理"的标准分治
• 算法与问题求解入门（KU） — 建立递推分析的全局观
• 动态规划：从斐波那契到背包 — 另一类递推（记忆化），思路不同