对于一种算法的时间复杂度分析还是特别重要的，在一些非递归算法中，我们仅仅看运算次数最多的那一行代码可能执行多少次就可以，实际就是看在循环中变量的变化，但是对于递归算法中该怎么分析呢？下面介绍几种递归函数中的算法时间复杂度分析的方法
这种方法是最简单的，也是最容易理解的一种方法，对于一个递归函数，我们可以利用他的递归方程，将其递推到常量的情况下，这样子就很容易求解他的时间复杂度了，可以看一下下面的递归方程
T
(
n
)
=
{
1
n
=
1
T
(
n
−
1
)
+
1
n
>
0
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ T(n-1)+1 \qquad n>0 \end{matrix}\right.
T(n)={1n=1T(n−1)+1n>0
我们可以递归成
T
(
n
)
=
T
(
n
−
1
)
+
1
=
T
(
n
−
2
)
+
2
=
T
(
n
−
3
)
+
3
=
.
.
.
=
T
(
1
)
+
n
−
1
T(n)= T(n-1)+1 = T(n-2) +2 = T(n-3)+3=...=T(1)+ n-1
T(n)=T(n−1)+1=T(n−2)+2=T(n−3)+3=...=T(1)+n−1
这样很容易就可以看出来这个上面这个递归算法的时间复杂度是O(n)
这种方法思路比较简单，但是使用的时候会特别复杂，上面举的例子是一种比较简单的情况，要是比较复杂的情况这种就会很麻烦。
master定理又称为主定理，这是一种快速的得出递归函数的时间复杂度
下面看一下，主定理的内容：
对于任意的递归函数，我们都一可以写出他的递归定义，下面我们给出递归定义的一般形式：
T
(
n
)
=
{
O
(
1
)
n
=
n
0
a
T
(
n
b
)
+
f
(
n
)
n
>
n
0
T(n) = \left\{\begin{matrix} O(1) \qquad n=n0\\ aT(\frac{n}{b})+f(n) \qquad n>n0 \end{matrix}\right.
T(n)={O(1)n=n0aT(bn)+f(n)n>n0
这里要是a>=1,b>1，并且f(n)是正函数
使用主定理方法，就是比较两个公式阶的比较 n log b a n^{\log_{b}{a} } nlogba 与 f ( n ) f(n) f(n)，已求出T(n)的时间复杂度。
规则1：如果 f ( n ) = O ( n log b a − ε ) f(n) = O(n^{\log_{b}{a-\varepsilon } } ) f(n)=O(nlogba−ε) 其中 ε \varepsilon ε >0 为常数，也就是说 f ( n ) < O ( n log b a ) f(n) < O(n^{\log_{b}{a} } ) f(n)<O(nlogba) ，则 T ( n ) = O ( n log b a ) T(n) = O(n^{\log_{b}{a} } ) T(n)=O(nlogba)
规则2：如果 f ( n ) = Θ ( n log b a ) f(n) = \Theta (n^{\log_{b}{a} } ) f(n)=Θ(nlogba) ,则 T ( n ) = O ( n log b a log n ) T(n) = O(n^{\log_{b}{a} } \log_{}{n} ) T(n)=O(nlogbalogn)
规则3：如果 f ( n ) = Ω ( n log b a + ε ) f(n) = \Omega (n^{\log_{b}{a+\varepsilon } } ) f(n)=Ω(nlogba+ε) 其中 ε \varepsilon ε >0 为常数，也就是说 f ( n ) > O ( n log b a ) f(n) > O(n^{\log_{b}{a } } ) f(n)>O(nlogba) 且存在n0,当n>n0时， a f ( n b ) ≤ c f ( n ) af(\frac{n}{b} )\le cf(n) af(bn)≤cf(n) 成立，c<1为常数，则 T ( n ) = O ( f ( n ) ) T(n) = O(f(n) ) T(n)=O(f(n))
以上就是主定理的内容，我们可以根据其规则直接快速的来判断递归函数的时间复杂度。
下面举个栗子看一看主定理的使用：
例一：
下面这个是一个时间复杂度的递归定义：
T
(
n
)
=
{
1
n
=
1
4
T
(
n
2
)
+
1
n
>
1
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 4T(\frac{n}{2})+1 \qquad n>1 \end{matrix}\right.
T(n)={1n=14T(2n)+1n>1
根据在主定理规则，我们先写出
n
log
b
a
n^{\log_{b}{a} }
nlogba和
f
(
n
)
f(n)
f(n) ，
n
log
b
a
n^{\log_{b}{a} }
nlogba =
n
log
2
4
n^{\log_{2}{4} }
nlog24 =
n
2
n^{2}
n2，
f
(
n
)
=
1
f(n) = 1
f(n)=1 。很明显这里对于阶数的比较
n log b a > f ( n ) n^{\log_{b}{a} } > f(n) nlogba>f(n)，所以根据主定理规则， T ( n ) = O ( n log b a ) T(n) = O(n^{\log_{b}{a} } ) T(n)=O(nlogba) ，即 T ( n ) = O ( n 2 ) T(n) = O(n^{2} ) T(n)=O(n2)
例二：
下面这个是一个时间复杂度的递归定义：
T
(
n
)
=
{
1
n
=
1
2
T
(
n
2
)
+
n
n
>
1
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 2T(\frac{n}{2})+n \qquad n>1 \end{matrix}\right.
T(n)={1n=12T(2n)+nn>1
根据在主定理规则，我们先写出
n
log
b
a
n^{\log_{b}{a} }
nlogba和
f
(
n
)
f(n)
f(n) ，
n
log
b
a
n^{\log_{b}{a} }
nlogba =
n
log
2
2
n^{\log_{2}{2} }
nlog22 =
n
n
n，
f
(
n
)
=
n
f(n) =n
f(n)=n 。很明显这里对于阶数的比较
n log b a = f ( n ) n^{\log_{b}{a} } = f(n) nlogba=f(n)，所以根据主定理规则， T ( n ) = O ( n log b a log n ) ) T(n) = O(n^{\log_{b}{a} } \log_{}{n} )) T(n)=O(nlogbalogn)) ，即 T ( n ) = O ( n log n ) T(n) = O(n\log_{}{n} ) T(n)=O(nlogn)
例三：
下面这个是一个时间复杂度的递归定义：
T
(
n
)
=
{
1
n
=
1
4
T
(
n
2
)
+
n
3
n
>
1
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 4T(\frac{n}{2})+n^{3} \qquad n>1 \end{matrix}\right.
T(n)={1n=14T(2n)+n3n>1
根据在主定理规则，我们先写出
n
log
b
a
n^{\log_{b}{a} }
nlogba和
f
(
n
)
f(n)
f(n) ，
n
log
b
a
n^{\log_{b}{a} }
nlogba =
n
log
2
4
n^{\log_{2}{4} }
nlog24 =
n
2
n^{2}
n2，
f
(
n
)
=
n
3
f(n) =n^{3}
f(n)=n3 。很明显这里对于阶数的比较
n
log
b
a
<
f
(
n
)
n^{\log_{b}{a} } < f(n)
nlogba<f(n)，有
4
f
(
n
2
)
≤
c
f
(
n
)
4f(\frac{n}{2} )\le cf(n)
4f(2n)≤cf(n) ，是否存在c使得这个式子成立，
4
f
(
n
2
)
=
4
(
n
2
)
3
<
c
n
3
4f(\frac{n}{2} )=4(\frac{n}{2})^{3} < cn^{3}
4f(2n)=4(2n)3<cn3，很显然
1
2
<
c
<
1
\frac{1}{2} < c <1
21<c<1，这里的所以根据主定理规则，
T
(
n
)
=
O
(
f
(
n
)
)
T(n) = O(f(n))
T(n)=O(f(n))，即
T
(
n
)
=
O
(
n
3
)
T(n) = O(n^{3} )
T(n)=O(n3)
这就是上面三种情况，我们也很容易的发现，在第三种规则的时候多了一个判定的条件，如果这个条件不满足那么就不能使用主定理这个方法了。看下面的一个例子：
下面这个是一个时间复杂度的递归定义：
T
(
n
)
=
{
1
n
=
1
2
T
(
n
2
)
+
n
log
n
n
>
1
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 2T(\frac{n}{2})+n\log_{}{n} \qquad n>1 \end{matrix}\right.
T(n)={1n=12T(2n)+nlognn>1
根据主定理的规则，我们同样先写出他的
n
log
b
a
n^{\log_{b}{a} }
nlogba和
f
(
n
)
f(n)
f(n) ，
n
log
b
a
n^{\log_{b}{a} }
nlogba =
n
log
2
2
n^{\log_{2}{2} }
nlog22 =
n
n
n，
f
(
n
)
=
n
log
n
f(n) =n\log_{}{n}
f(n)=nlogn ，显然
n
log
b
a
<
f
(
n
)
n^{\log_{b}{a} } < f(n)
nlogba<f(n) 这就符合规则三，但是我们还要判断一下是否存在一个
ε
\varepsilon
ε 使得
f
(
n
)
=
Ω
(
n
log
b
a
+
ε
)
f(n) = \Omega (n^{\log_{b}{a+\varepsilon } } )
f(n)=Ω(nlogba+ε) 成立，显然是不存在
ε
\varepsilon
ε的，所以该题目不适应主定理。
递归树的这种解法，其实跟递推的方法其实很相似，就是根据树的形式来确定时间的复杂度。我们之间来看个例子：
下面这个是一个时间复杂度的递归定义：
T
(
n
)
=
{
1
n
=
1
2
T
(
n
2
)
+
n
n
>
1
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 2T(\frac{n}{2})+n \qquad n>1 \end{matrix}\right.
T(n)={1n=12T(2n)+nn>1
我们可以很容易的画出他的递归树来，以他的f(n)为根，并以他的递归方程形式，分成孩子结点
我们通过观察这个递归树可以发现，每一层消耗的时间都是n，那么只要知道这课递归树的高度，我们就可以大致的判断出这个递归算法的时间复杂度，实际就是求出这颗树中结点的个数。很容易的可以看出来，这棵树是一颗满二叉树，那么他的高度应该为 log 2 n \log_{2}{n} log2n，这就很容易判断出这个递归算法的时间复杂度为 O ( n log n ) O(n \log_{}{n} ) O(nlogn)
