用递推关系理论分析递归算法的时间复杂度

用递推关系理论分析递归算法的时间复杂度

[ 摘要 ] 对算法进行时间复杂度分析是算法分析与研究的重要内容，而对递归算法分析其时间复杂度时往往比较困难。 本文提出了用组合数学中的递推关系理论来分析一些特殊的递归算法的时间复杂度， 并同时得出三个推论， 在算法的分析与研究方面具有一定的参考价值。

[ 关键词 ] 时间复杂度，递归，母函数

1. 引言

一个程序在计算机上运行时所耗费的时间取决于对源程序进行编译所需时间、 计算机执行每条指令所需时间、 程序中指令重复执行的次数。
前两条依赖于实现算法的计算机软件、硬件系统，亦即依赖于实现算法所用语言的编译程序的性能和计算机本身的速度。因此习惯上常常用重复执行次数最多的语句频度来分析算法的时间复杂度， 记为t（n），其中n为问题的规模或大小。例如对n个存放于数组a[n] 中的数进行选择法排序的算法：

for( i=0; i //共进行n-1趟排序

k=i; //n-1次

for(j=i+1; j //n-i-1次

if(a[j] < a[k]){ //第i趟需进行n-i-1趟次比较，该语句频度最大

k=j;

}

}

if(k!=i){ t=a[k]; a[k]=a[i]; a[i]=t;} //n-1比较和交换

}

该算法的时间复杂度为：

t(n) = (n-i-1) = = (n2 - n) = O(n2).

对一个算法进行时间复杂度的分析方式有多种， 但有时候一个算法的时间复杂度并不象上面的例子那样可以轻易地分析出来。也许对一个for循环、 对一个单一语句的时间复杂度可以马上分析出来， 但遇到递归算法时， 则无法轻易地分析出其时间复杂度， 而递归算法又是程序设计时经常采用的有效手段，如求解n阶hanoi塔问题的递归算法：

//将n个盘从one 座借助two座，移动到three座

void hanoi ( int n, char one, char two, char three ){

if( n==1 ){

printf("%c —> %c", one, three);

}else{

hanoi(n-1, one, three, two);

printf("%c —> %c", one, three);

printf("%c —> %c", one, three);

hanoi( n-1, two, one, three);

}

}

类似的递归算法还有很多， 例如求Fibonacci数列前n项的递归算法等。对于这些递归算法，可以利用组合数学中的母函数与递推关系理论来分析其时间复杂度。

2. 利用递推关系理论分析递归算法的时间复杂度

2.1相关概念

1）k阶常系数线性递推关系式与特征多项式

若母函数G(x) = a0 +a1x +a2x2 + ... ，所对应的序列{an} 满足an + C1an-1 + C2an-2 + ... + Ckan-k = 0，并且有初始条件a0 = d0，a1=d1，...，ak-1=dk-1，C1，C2，...，Ck及d0，d1，...，dk-1是常数，Ck0，则称an + C1an-1 + C2an-2 + ... + Ckan-k = 0为序列{an}的k阶常系数线性递推关系。

对应于k阶常系数线性递推关系的多项式C(x) = xk + C1xk-1 + ..+ Ck-1x + Ck称为序列{an}的特征多项式。

2.2推论1及其应用

设某一递归算法时间复杂度函数为t(n)，如果其k阶常系数递推关系式所对应的特征多项式C(x)有k个不同的根β1, β2 , ... , βk, 则t(n)的解为：t(n) = A1β1n + A2β2n ... + Akβkn ,其中A1，A2 ... Ak 为k个待定常数。

例如，对上面n阶hanoi塔问题的递归算法进行分析。不妨设h(n) 表示将n个盘子从one座移动到three座所需的转移次数亦即hanoi问题算法的时间复杂度。根据算法先把前面n-1个盘子转移到two座上（移动次数为h(n-1)次），然后把第n个盘子转移到three座上（移动次数为 1 次）；最后再一次将two座上的n-1个盘子转移到three座上 （移动次数为h(n-1)次）。则显然有：

h(n) = 2h(n-1) + 1 , h(1) = 1 (1)

同样有

h(n-1) = 2h(n-2) + 1 (2)

(1) - (2) 式即可得到2阶（即k = 2）常系数线性递推关系式:

h(n) - 3h(n-1) + 2h(n-2) = 0

根据递推关系理论, 序列h(n)所对应的的特征多项式为

C(x) = x2 - 3x + 2 其有两个不同的根，x1= 1，x2=2。则

h(n) = A1x1n + A2x2n = A1 + A22n ，其中A1，A2为待定系数。

根据hanoi问题，显然有初值h(1) = 1，h(2) = 3, 于是求得A1= -1，A2=1，故h(n) = 2n -1。说明n阶hanoi塔问题递归算法的时间复杂度为O(2n )。

2.3推论2及其应用

设某一递归算法时间复杂度为t(n)，其常系数线性递推关系式所对应的特征多项式C(x)，有k重根β1，则递推关系的解即t(n)对应于β2 的项为(A0 + A1n + ... + Ak-1nk-1)β1n，其中A0，A1，....，Ak-1为k个待定常数。特征多项式C(x)的非重根所对应的项按推论1中的方法求解。

例如， 分析用递归算法求下列函数值时的时间复杂度(tn) （算法简略）。

func(n) = 5func(n-1) - 8 func(n-2) + 4func(n-3)，并给定初值func(1)，func(2)，func(3)。

由函数的递推关系我们得到算法的时间复杂度t(n) 的线性常系数递推关系：

C(x) = x3 - 5x2 + 8x -4，该特征多项式有3个根x1,2 = 2（二重根），x3=1，则递推关系式的解即t(n) 为：

t(n) = (A0 +A1n) * 2n + A2 * 1n，其中A0 ，A1，A2为待定常数，根据初值求得A0 = 3，A1= -1，A2 = -3，所以该递归算法的时间复杂度为t(n) = 3*2n - n*2n - 3。

2.4推论3

设某一递归算法时间复杂度为t(n)，其递推关系式所对应的特征多项式C(x)有不同的复根，此时可按照“推论”的办法处理。不过复数有它的特点，假如特征多项式C(x)的两个共轭复根x1，x2可化成下列形式：x1 = ρ(cosθ + isinθ)，x2 = ρ(cosθ - isinθ)。例如将特征多项式C(x) = x2 + x+1的两个复根x1 = (-1 + i)/2，x2 = ( -1 -i)/2可写成：

X1 = cosπ + isinaπ，

X2 = cosπ - isinaπ ( ρ=1 )

此种情况下，递推关系式的解即递归算法的时间复杂度可根据推论1有：

t(n) = k1x1n + k2x2n = k1ρn（cosθ + isinnθ）+ k2ρn（cosθ - isinnθ）

= ρn(k1 + k2)cosnθ + iρn(k1 - k2)sinnθ 。

k1 + k 和 i(k1 - k2)仍然是待定常数，ρ、θ可由复根求得。令A = k1 + k2，

B = i(k1 - k2)得到：

t(n) = Aρncosnθ + Bρnsinnθ

3. 结论

在分析递归算法的时间复杂度t(n)时，如果t(n)的递推关系式是一个常系数线性递推关系式，则可以利用母函数与递推关系理论求出其时间复杂度。

[ 参考文献 ]：

1.姜建国，岳建国。 组合数学[M] 西安电子科技大学出版社2003

2.方贤进，潘地林，管建军。 用母函数理论分析递归算法的时间复杂度[J] 2005

本文来源：https://www.2haoxitong.net/k/doc/bff73cb1c8d376eeafaa310a.html