2.16d 主定理

Tip

本主定理为简化版

形式

如果已知:

$$T(n) = aT\left( \left\lceil \frac{n}{b} \right\rceil \right) + O(n^d) ( a > 0, b > 1, d \geq 0 )$$

那么我们就可以将其转换为大O表示法:

$$T(n) = \begin{cases} O(n^d) & \text{if } d > \log_b a \\ O(n^d \log n) & \text{if } d = \log_b a \\ O(n^{\log_b a}) & \text{if } d < \log_b a \end{cases}$$

简单的解释

我们可以对 a、b、d进行如下解释:

• a: 每个问题会分裂的子问题个数
• b: 问题规模缩小的因子
• $n^d$: 每个子问题处理的代价
  所以，对于原式中的两个式:
• $aT\left( \left\lceil \frac{n}{b} \right\rceil \right)$: 当前的分裂子问题所消耗的成本
• $O(n^d)$: 每个子问题所消耗的成本

考虑一颗递归树，这就是两股势力的竞争，哪股势力增长越快，谁就能主导大O表示法
因此，我们将$d$和$\log_b a$进行比较即可，哪个大选哪个

$$T(n) = \begin{cases} O(n^d) & \text{if } d > \log_b a \\ O(n^{\log_b a}) & \text{if } d < \log_b a \end{cases}$$

如果他们相等的话，任何一边的影响就都无法忽略不计了，因为一共有$log n$层，所以我们再乘上$log n$
最终合并起来:

$$T(n) = \begin{cases} O(n^d) & \text{if } d > \log_b a \\ O(n^d \log n) & \text{if } d = \log_b a \\ O(n^{\log_b a}) & \text{if } d < \log_b a \end{cases}$$

没有这种形式怎么办

尝试变形成这种形式

• 换元法
• 使用更通用的主定理

不能用主定理的情况

• 非分治递归 （如$T(n)=T(n-1)+...$)
• $a$或$b$并非常数