在CSP初赛题中，经常会遇到计算一个递推算法的时间复杂度的题目。 对于这类题，如果凭直觉去做，虽说许多情况都能算(蒙)对，但对于稍稍复杂一点的多项式来说，靠直觉去求解就非常困难了，这时可以用主定理来秒杀。

主定理是分治算法分析中非常重要的定理。


例如，我们要处理一个规模为n的问题，通过分治得到a个规模为$\frac{n}{b}$的问题(假设每个子问题的规模基本一样)，$f(n)$为递推以外的计算工作，则其时间复杂度的递推式为：

$T(n)=aT(\frac{n}{b})+f(n)$

如果$a≥1$，$b>1$为常数，$f(n)$为函数，$T(n)$为非负整数，$\Theta(n^{log_ba})$为基准函数，那么：

1. 若$f(n)<\Theta(n^{log_ba})$，则$T(n)=\Theta(n^{log_ba})$

2. 若$f(n)>\Theta(n^{log_ba})$，则$T(n)=f(n)$

3. 若$f(n)=\Theta(n^{log_ba})$，则$T(n)=\Theta(n^{log_ba}logn)$

以上仅仅是本人为简化记忆而整理而成的，若想知道严谨的表述，详见百度百科。若想要更深入地理解主定理并了解其证明，详见这篇博客。

例题：
(今天上午打的CSP模拟赛)

假设某算法的计算时间表示为递推关系式

$