略标题党。借用了两位先驱的标题: https://www.luogu.com.cn/discuss/490240 https://www.luogu.com.cn/discuss/490184

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

暴力递归是靠谱的，因为其本质就是递归树，所以据大多数题目都可以用，但是暴力递归有时很慢很麻烦，便有：

主定理和Akra–Bazzi 定理搭配！

关于 Akra–Bazzi 定理，推荐看我的博客，已经投了日报，但是考虑到审核没那么快，而且明天就是初赛，所以发此帖宣传。

例一：

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

本题其实可以用主定理做，详见：https://math.stackexchange.com/questions/239402/solve-the-recurrence-relation-tn-sqrtn-t-left-sqrt-n-right-n

例二：

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

$a=\{3,4\},b=\left\{\frac12,\frac14\right\}$，使 $\frac{3}{2^p}+\frac{4}{4^p}=1$，即 $p=2$。

&=\Theta\left(n^2\left(1+\frac{n-1}{n}\right)\right) \\ &=\Theta\left(n^2\cdot\frac{2n-1}{n}\right) \\ &=\Theta\left(2n^2-n\right) \\ &=\Theta\left(n^2\right)\end{aligned}$$