递归算法中的时间复杂度分析
对于一种算法的时间复杂度分析还是特别重要的，在一些非递归算法中，我们仅仅看运算次数最多的那一行代码可能执行多少次就可以，实际就是看在循环中变量的变化，但是对于递归算法中该怎么分析呢？下面介绍几种递归函数中的算法时间复杂度分析的方法
0.递推法
这种方法是最简单的，也是最容易理解的一种方法，对于一个递归函数，我们可以利用他的递归方程，将其递推到常量的情况下，这样子就很容易求解他的时间复杂度了，可以看一下下面的递归方程
T
(
n
)
=
{
1
n
=
1
2
T
(
n
−
1
)
+
1
n
>
0
T(n) = \left\{\begin{matrix} 1 \qquad n=1\\ 2T(n-1)+1 \qquad n>0 \end{matrix}\right.
T(n)={1n=12T(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)
这种方法思路比较简单，但是使用的时候会特别复杂，上面举的例子是一种比较简单的情况，要是比较复杂的情况这种就会很麻烦。
1.Master定理
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
ε的，所以该题目不适应主定理。
2.递归树
递归树的这种解法，其实跟递推的方法其实很相似，就是根据树的形式来确定时间的复杂度。我们之间来看个例子：
下面这个是一个时间复杂度的递归定义：
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)