被主定理震撼到了

分析复杂度时可能有用。（主定理狗都不学）

若有递归式 \(T(n)=aT(\dfrac{n}{b})+f(n)\)

则分以下三种情况：

• \(f(n)=O(n^{\log _ b a-\epsilon}),\epsilon>0\)，此时 \(T(n)=\Theta(n^{\log_ b a})\)
• \(f(n)=\Theta(n^{\log_ b a}\log^k n),k\geq 0\)，此时 \(T(n)=\Theta(n^{\log_ b a}\log^{k+1} n)\)
• \(f(n)=\Omega(n^{\log_b a+\epsilon}),\epsilon>0\)，此时若 \(\exists c<1\) 使得 \(\forall n>n_0,af(\dfrac{n}{b})\leq cf(n)\)，则 \(T(n)=\Theta(f(n))\)

upd：这把被震撼到了。
当 \(a=b=2\) 时，取 \(f(n)=\log n, T(1)=1\)，实测递归结果 \(T(n)=3n\)；取 \(f(n)=\sqrt n, T(n)=3n\)；取 \(f(n)=\log ^2 n\)，\(T(n)=8n\)。