在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。
原文：https://www.cnblogs.com/void-null/p/15227387.html