分析复杂度时可能有用。(主定理狗都不学)
若有递归式 \(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))\)