在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模拟赛)

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

$??(??)=3??(\frac{??}{2})+Θ(??),??(1)=Θ(1)$

则算法的时间复杂度为 （ ）

A. $Θ(??)$

B. $Θ(??log_23)$

C. $Θ(??log??)$

D. $Θ(??^{log_23}log??)$



显然，在这里$a=3,b=2,f(n)=Θ(n)$

则基准函数
$Θ(n^{log_ba})=Θ(n^{log_23})>Θ(n)=f(n)$

即$f(n)<\Theta(n^{log_ba})$，符合定理第1条，则：

$T(n)=\Theta(n^{log_ba})=\Theta(n^{log_23})$，选B。

主定理