知乎：主定理(Master Theorem)
tip：对于$T(n)=2T(3n/2)$来说，其中$b=2/3$
利用主定理求下列递归方程的时间复杂度：
$T(n)=5T(n/2)+\theta(n^2)$
$a=5,b=2,f(n)=n^2$
$n^{log_b^a}=n^{log_2^5}>f(n)$
$\therefore T(n)=\theta(n^{log_2^5})$
$T(n)=2T(n/2)+n$
$a=2,b=2,f(n)=n$
$n^{log_b^a}=n=f(n)$
$\therefore T(n)=\theta(nlogn)$
$T(n)=5T(n/2)+\theta(n^3)$
$a=5,b=2,f(n)=n^3$
$n^{log_b^a}=n^{log_2^5}<f(n)$
$\therefore T(n)=\theta(n^3)$