略标题党。借用了前一个的标题。

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

验证仍然是带有一点不靠谱的，实际上可以采用更加靠谱和直接的办法：

暴力递归。

以下是使用暴力递归法来解前一个的三个例子：

例 1

$\begin{aligned}T(n)&=4\sqrt nT(\sqrt n)+n\\&=16n^{3/4}T(n^{1/4})+4n+n\\&=\cdots\\&=n(1+4+\cdots+4^{\log_2\log_2 n})\\&=O(n\log^2 n)\end{aligned}$

众所周知，把 $n$ 开根到 $1$ 为止的次数是 $\log_2\log_2 n$。

例 2

$\begin{aligned}T(n)&=T(n/2)+n\log n\\&=T(n/4)+n\log n+(n/2)\log(n/2)\\&=\cdots\\&=n\log n+(n/2)\log(n/2)+\cdots\\&\le 2n\log n\end{aligned}$

$\log(n/2^k)$ 全部放成 $\log n$，然后等比数列求和。

例 3

$\begin{aligned}T(n)&=3T(n/2)+4T(n/4)+n\end{aligned}$

不妨设 $n=2^{k}$，记 $T(2^k)=f_k$，那么 $f_k=3f_{k-1}+4f_{k-2}+2^k$。

记 $g_k=f_k+2^{k+1}/3$，那么 $g_k=3g_{k-1}+4g_{k-2}$。

容易看出 $g_k=a4^k+b(-1)^k$（高中数学竞赛基础内容，瞪眼也能看出来）

所以 $T(2^k)=a4^k+b(-1)^k-2^{k+1}/3=O(4^k)$，所以 $T(n)=O(n^2)$。

---

虽然其实是非常正常和直接的思路，但是好像很多人不会这种东西。

计算量不会很大的。