主定理

发布于 2021-08-23  3.87k 次阅读


对于 $T(n) = a \times T(\lceil \dfrac n b \rceil) + O(n^d)$:

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

简单来说分为三种情况:

  1. $a \times (\lceil \dfrac n b \rceil)^d < n^d \to T(n) = O(n^d)$
  2. $a \times (\lceil \dfrac n b \rceil)^d = n^d \to T(n) = O(n^d \log_b n)$
  3. $a \times (\lceil \dfrac n b \rceil)^d > n^d \to T(n) = O(n^{\log_b a})$

我缓慢吐出一串啊吧啊吧并不再想说话