略标题党。

解决递归式时间复杂度题目的新方法

在初赛中，递归式时间复杂度计算通常以选择题的形式出现，所以可以不求解而是验证。

这里给出一种快速验证时间复杂度的不严谨简便方法，在主定理不适用的情况下也能使用，我和机房同学称之为 o 定理。

例 1（主定理不适用）：

$T(n) = 4\sqrt{n}T(\sqrt{n}) + n$

若要检验时间复杂度是不是 $O(n\log^2n)$，只需带入 $T(n) = kn\log^2n$，得等式右边为 $4\sqrt{n}\times k \sqrt{n} \log^2 (n^{\frac{1}{2}}) + n = 4kn\times \frac{1}{4}\log^2n+n=k\log^2n+n$，最高次项为 $k\log^2n$，等式左边也是 $k\log^2n$，所以成立。

例 2（主定理适用）：

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

带入 $T(n) = kn\log n$，得等式右边为 $\frac{k}{2}\log{\frac{n}{2}} + n\log{n} = \frac{k}{2}(\log n + C)+n\log n = \frac{k+2n}{2}\log n + \frac{kC}{2}$，等式左边为 $kn\log n$，令 $k = 2$，等式左右最高次项相同。

例 3（主定理不适用）：

$T(n) = 3T(\frac{n}{2}) + 4T(\frac{n}{4})+n$

带入 $kn^2$，得等式右边为 $3k\times\frac{n^2}{4}+4k\times\frac{n^2}{16} + n = \frac{3kn^2}{4} + \frac{kn^2}{4} + n = kn^2 + n$，左右最高次项相同。

初赛模拟的时候随便想的，如果错了轻喷