递归算法的时间复杂度分析

一、步骤

建立递归方程
求解该递归方程
用渐进符号表示函数的阶

二、递归方程

递归方程是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。
当一个算法包含对其自身的递归调用时，可以用递归方程来表示其运行时间。

【例1】建立汉诺塔问题的算法递归方程

void Hanoi(int n,char A,char B,char C)//------T(n)
{
    if(n == 1){
        printf("将盘片%d从%c搬到%c\n",n,A,C);//------O(1)
    }else{
        Hanoi(n-1,A,C,B);//------T(n-1)
        printf("将盘片%d从%c搬到%c\n",n,A,C);//------O(1)
        Hanoi(n-1,B,A,C);//------T(n-1)
    }
}

最终得到递归方程为

$\begin{cases} T(n) = O(1)~~~~~~~~~~~~~~~~~~~~~~~~~~~当n=1时\\ T(n) = 2T(n-1) + O(1)~~~~~当n>1时 \end{cases}$

三、递归方程的求解

1.迭代法

从初始递归方程开始，反复用递归方程右边的等式代入左边的函数，直到得到初值。
【例2】用迭代法求解递归方程

1 2	T(n)=O(1) 当n=1时 T(n)=2T(n-1)+O(1) 当n>1时

$T(n) = 2T(n-1)+c = 2[2T(n-2)+c]+c = 2^2T(n-2)+c2^1+c = 2^3T(n-3)+c2^2+c2^1+c = … = 2^{n-1}T(1)+c2^{n-2}+…+c2^2+c2^1+c = c(2^{n-1}) = O(2^n)$

2.代入法

2.1 猜测解的形式
2.2 用数学归纳法证明

3.递归树法

用树的形式给出一个递归算法执行的成本模型。

3.1 递归树法求解递归方程的步骤

(1) 展开递归方程，构造对应的递归树
(2) 将树中每层中的代价求和，得到每层代价，再将所有层的代价求和，得到总的递归调用代价

3.2 递归树的构造方法

(1) 递归树是一棵结点带权值的树，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。
(2) 初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点。

【例3】求解递归方程 $T(n)=T(n/4)+ T(n/2)+ n^2$
解法如下：

4.主定理法

主定理法适用于求解下面的递归形式:
$T(n) =aT(n/b) + f(n)$ ，其中其中a≥1,b>1为常数，f(n)为渐近正函数，a为分解后的子问题个数，n/b为分解后子问题的规模，f(n)为分解与合并子问题的解的工作量。算法的时间复杂度 $T(n)$ 满足下列条件:

$f(n)=O(n^{(log_ba)-ε} ),ε>0,n^{log_ba}比f(n)大(大n^ε倍),则T(n)=Θ(n^{log_ba});$
$f(n)=Θ(n^{log_ba}),那么T(n)=Θ(n^{log_ba}log_2n);$
$f(n)=Ω(n^{(log_ba)+ε}),ε>0,f(n)比n^{log_ba}大(大n^ε倍)且对于某个常数c<1和所有的充分大的n有af(n/b)≤cf(n),那么T(n)=Θ(f(n)).$

【例4】求解 $T(n)=9T(n/3)+n$ 的时间复杂度

【例5】求解 $T(n)=T(2n/3)+1$ 的时间复杂度

【例6】求解 $T(n)=3T(n/4)+nlogn$ 的时间复杂度

不能使用主定理法解决的情况：
【例7】求解 $T(n)=2T(n/2)+n^2log_2n$ 的时间复杂度
解： $a=2,b=2，则n^{log_ba}=n^{log_22}=O(n),f(n)=nlogn$ ，
则 $af(n/b)=2*n/2*log(n/2)<nlogn$ ，则 $c=1$ ,不满足 $c<1$ ,所以无法使用主定理法