如何使用主定理求解T(n)=8T(n/2)+1000n²类递推关系

主定理适用前提 #

• 仅适用于形式为 T(n) = aT(n/b) + f(n) 的递推式，参数要求如下：
  • (a \geq 1)，代表拆分出的子问题数量
  • (b > 1)，代表每个子问题的规模缩小比例
  • (f(n)) 为渐近正函数，代表拆分子问题、合并子问题解的总代价

主定理三种判定规则 #

• 规则1：若存在常数 (\varepsilon > 0)，使得 (f(n) = O(n^{\log_b a - \varepsilon}))，则 (T(n) = \Theta(n^{\log_b a}))
• 规则2：若 (f(n) = \Theta(n^{\log_b a}))，则 (T(n) = \Theta(n^{\log_b a} \log n))
• 规则3：若存在常数 (\varepsilon > 0)，使得 (f(n) = \Omega(n^{\log_b a + \varepsilon}))，且存在常数 (c < 1)，对所有足够大的 (n) 满足 (a f(n/b) \leq c f(n))，则 (T(n) = \Theta(f(n)))

递推式1推导：(T(n) = 8T(n/2) + 1000n^2) #

1. 提取参数：(a=8)，(b=2)，(f(n)=1000n^2)
2. 计算临界阶：(\log_b a = \log_2 8 = 3)，对应临界阶项为 (n^{\log_b a} = n^3)
3. 渐近阶比较：
   • 常数系数不影响渐近阶，因此 (f(n) = 1000n^2 = \Theta(n^2))
   • 取 (\varepsilon=1>0)，可满足 (n^2 = O(n^{3-1}))，完全符合主定理规则1的判定条件
4. 结论：(T(n) = \Theta(n^3))

递推式2推导：(T(N) = 8T(N/2) + 100N^2) #

1. 提取参数：(a=8)，(b=2)，(f(N)=100N^2)
2. 计算临界阶：(\log_b a = \log_2 8 = 3)，对应临界阶项为 (N^{\log_b a} = N^3)
3. 渐近阶比较：
   • 该递推式仅(f(N))的常数系数与递推式1不同，常数系数不改变渐近阶，因此 (f(N) = 100N^2 = \Theta(N^2))
   • 取 (\varepsilon=1>0)，可满足 (N^2 = O(N^{3-1}))，符合主定理规则1的判定条件
4. 结论：(T(N) = \Theta(N^3))

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