主定理的一些特化

下文中一切的等号并不意味着完全相等，而是二者量级相同，不会影响证明的结果。

T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n)

。

不难发现

\begin{aligned} T(n) &= n \times 1 + \frac{n}{2} \times 2 + \frac{n}{4} \times 4 + \ldots + \frac{n}{n} \times n\\ &= n \times (1 + 1 + \ldots + 1)\\ &= n\log n\\ \end{aligned}

T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n^2)

。

不难发现

\begin{aligned} T(n) &= n \times 1 + \frac{n}{2} \times 4 + \frac{n}{4} \times 16 + \ldots + \frac{n}{n} \times n^2\\ &= n \times (1 + 2 + 4 + \ldots n)\\ &= n \times (2n - 1)\\ &= n^2\\ \end{aligned}

T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n\log n)

。

不难发现

\begin{aligned} T(n) &= n \times 1\log 1 + \frac{n}{2} \times 2\log 2 + \frac{n}{4} \times 4\log 4 + \ldots + \frac{n}{n} \times n\log n\\ &= n \times (\log 1 + \log 2 + \log 4 + \ldots + \log n)\\ &= n \times (0 + 1 + 2 + \ldots + \log n)\\ &= n \times \frac{\log^2 n}{2}\\ &= n\log^2n \end{aligned}

我们知道

\sum_{i = 0}^{n} i^k = \mathcal{O}(n^{k + 1})

于是推广上面结论得到

T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n\log^k n) \Rightarrow T(n) = \mathcal{O}(n\log^{k + 1}n)

文章操作