如何使用主定理或递归法求解T(n) = 2T(n/2) + n!类递归问题

方法1：主定理（Master Method）求解 #

主定理适用于形如T(n) = aT(n/b) + f(n)（a≥1，b>1）的递推关系，对应本题参数：

• a=2，b=2，因此计算子问题量级基准值：n^(log_b a) = n^(log2 2) = n
• 非递归项f(n) = n!，阶乘的增长速度远快于任何多项式、指数函数，显然满足主定理第三种情况的判定条件：f(n) = Ω(n^(log_b a + ε))，其中ε可以取任意大于0的常数（比如取ε=1，显然n!是Ω(n²)）
• 再验证主定理第三种情况要求的正则条件：当n足够大时，a*f(n/b) ≤ c*f(n)（0<c<1）。代入参数得2*(n/2)! ≤ c*n!，由于n! = n*(n-1)*...*(n/2+1)*(n/2)!，n≥4时取c=0.5即可满足不等式，正则条件成立。

因此主定理第三种情况的结论为：T(n) = Θ(f(n)) = Θ(n!)

方法2：递归展开法验证 #

我们可以直接展开递推式验证结论：

T(n) = n! + 2T(n/2)
= n! + 2*( (n/2)! + 2T(n/4) )
= n! + 2*(n/2)! + 4*(n/4)! + 8*(n/8)! + ... + 2^k * T(n/2^k)

当展开到n/2^k = 1时终止，此时k=log2 n，最后一项为n * T(1)，T(1)为常数阶。
观察所有展开项的量级，首项n!的增长速度远大于后面所有项的总和，后面所有项的和甚至不到n!的1%（n≥10时差距已经达到数个数量级），因此整个递推式的主导项就是n!，时间复杂度为Θ(n!)

补充说明 #

• 只要递推式的非递归项是阶乘级，几乎都会主导所有子问题的开销，最终时间复杂度由阶乘项决定
• 部分特殊递推（比如子问题拆分后规模不是线性缩小、非递归项和子问题项量级接近）可能不适用主定理，此时用递归展开法推导更稳妥

内容的提问来源于stack exchange，提问作者NMK