算法分析，主定理
主定理，master theorem，算法中基于分治思想写出的递归解法，其时间复杂度可用于一个递推关系式表示，而主定理用于计算满足某些条件下的递推关系式中的时间复杂度。
问题的规模为n，T(n)为问题规模为n时需要的耗时，规模为n的问题可以分解为a个规模为n/b的子问题，是将原问题分解成子问题和将子问题的解合并成原问题的解的时间f(n)，则
T ( n ) = a T ( n b ) + f ( n ) 其中， a 、 b 为常数， a > = 1 ， b > 1 ， f ( n ) 为函数 T(n) = aT(\frac{n}{b}) + f(n)\\ 其中，a、b为常数，a >=1，b > 1，f(n)为函数 T(n)=aT(bn)+f(n)其中，a、b为常数，a>=1，b>1，f(n)为函数
- 若 f ( n ) = O ( n l o g b a − ϵ ) f(n) = O(n^{log_{b}a-\epsilon}) f(n)=O(nlogba−ϵ)， ϵ > 0 \epsilon>0 ϵ>0，则 T ( n ) = Θ ( n l o g b a ) T(n) = \Theta(n^{log_ba}) T(n)=Θ(nlogba)
- 若 f ( n ) = Θ ( n l o g b a ) f(n) = \Theta(n^{log_{b}a}) f(n)=Θ(nlogba)，则 T ( n ) = Θ ( n l o g b a l o g n ) T(n) = \Theta(n^{log_ba}logn) T(n)=Θ(nlogbalogn)
- 若 f ( n ) = Ω ( n l o g b a + ϵ ) f(n) = \Omega(n^{log_{b}a+\epsilon}) f(n)=Ω(nlogba+ϵ)， ϵ > 0 \epsilon>0 ϵ>0，且对于某个常数 c < 1 c<1 c<1和所有充分大的n有 a f ( n b ) < = c f ( n ) af(\frac{n}{b})<=cf(n) af(bn)<=cf(n)，则 T ( n ) = Θ ( f ( n ) ) T(n) = \Theta(f(n)) T(n)=Θ(f(n))
速记
对于基准函数
y
=
n
l
o
g
b
a
y = n^{log_ba}
y=nlogba
若 f(n) < y，
Θ
(
n
l
o
g
b
a
)
\Theta(n^{log_ba})
Θ(nlogba)
若f(n) = y，
Θ
(
n
log
b
a
l
o
g
n
)
\Theta(n^{ \log_ba}logn)
Θ(nlogbalogn)
若f(n) > y，
Θ
(
f
(
n
)
)
，
a
f
(
n
b
)
<
=
c
f
(
n
)
，
c
<
1
\Theta(f(n))，af(\frac{n}{b})<=cf(n)，c<1
Θ(f(n))，af(bn)<=cf(n)，c<1