主定理简洁结论

前言

首先，众所周知，主定理是一个根据复杂度递推式子计算出实际复杂度的定理。

网上有不少讲解主定理的文章，但是我感觉可能对于一部分人来说还是太长了（毕竟就出一道题，看什么证明))

所以我就写一个直接说结果的博客吧。

直接上结论

假设复杂度递推式子是

$T(n)=aT(\frac{n}{b})+O(n^d)$

那么

如果$\dfrac{a}{b^d}<1$：

复杂度为

$O(n^d)$

如果$\dfrac{a}{b^d}>1$：

复杂度为

$O(n^{\log_ba})$

如果$\dfrac{a}{b^d}=1$：

复杂度为

$O(n^{d}\log_bn)$

嗯，到这里就结束了！