主定理

主定理是用于计算如下递推形式的时间复杂度

根据$f(n)$与 $\log_ba$ 的大小关系分为四种情况

1. $f(n)=O\left(n^{\log_ba-\epsilon}\right)$ 可以理解为 $f(n)<n^{\log_ba}$, 则有

2. $f(n)=\Theta\left(n^{\log_ba}\right)$ 可以理解为 $f(n)=n^{\log_ba}$, 则有

3. $f(n)=\Omega\left(n^{\log_ba+\epsilon}\right)$ 可以理解为 $f(n)>n^{\log_ba}$, 则有

4. 第四种情形是特殊的, 当$f(n)=\Omega\left(n^{\log_ba}\log^kn\right)$ 即 $f(n)=n^{\log_ba}\log^kn$时

简化的主定理

如果取$f(n)$是多项式复杂度的, 即 $f(n)=O(n^d)$, 递推式即

那么就能讲主定理简化为

1. $d<\log_ba$

2. $d=\log_ba$

3. $d>\log_b a$