如何用主定理（Master Theorem）求解递推式 T(n) = 2T(n/4) + T(n/4) + T(n/4) + 311

首先明确主定理的适用边界：它仅适用于符合以下标准分治形式的递推式：
T(n) = aT(n/b) + f(n)
其中参数要求：

• a 是拆分后的子问题总数，常数且 ≥ 1
• b 是子问题规模的缩放系数，常数且 > 1
• f(n) 是拆分问题、合并子问题结果的非递归阶段耗时

求解核心步骤 #

1. 先从你的递推式里提取出a、b、f(n)三个参数，计算临界值的指数c = log_b a，对应临界复杂度为n^c
2. 比较f(n)和n^c的渐进量级，对应三种匹配规则直接套结果：
   • 情况1：f(n) 比 n^c 多项式级更小，即存在常数ε>0，满足f(n) = O(n^{c-ε})，最终复杂度为 T(n) = Θ(n^c)
   • 情况2：f(n) 和 n^c 同阶（允许差log的若干次方），即存在常数k≥0，满足f(n) = Θ(n^c log^k n)，最终复杂度为 T(n) = Θ(n^c log^{k+1} n)
   • 情况3：f(n) 比 n^c 多项式级更大，即存在常数ε>0，满足f(n) = Ω(n^{c+ε})，且满足正则条件a*f(n/b) ≤ k*f(n)（k<1为常数，n足够大时成立），最终复杂度为 T(n) = Θ(f(n))

常见示例验证（归并排序递推） #

递推式为 T(n) = 2T(n/2) + O(n)

• 提取参数：a=2，b=2，f(n)=O(n)
• 计算c=log₂2=1，临界值为n^1 =n
• f(n)=O(n) 符合情况2的Θ(n^1 log^0 n)，k=0
• 最终结果：Θ(n log n)，和归并排序的实际复杂度完全匹配

避坑提示 #

• 不符合标准分治递推形式的式子不能直接套主定理，比如子问题规模不统一、递推项系数不是常数的场景
• 量级比较必须是多项式级的差异，比如f(n)=n log n、临界值为n的场景，二者差异仅为log项，不属于多项式级差异，不能套用情况1，需匹配情况2

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