主定理的一些特化

· · 算法·理论

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

不难发现 $$ \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) $$