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

《用递推关系理论分析递归算法的时间复杂度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用递推关系理论分析递归算法的时间复杂度[摘要]对算法进行时间复杂度分析是算法分析与研究的重要内容，而对递归算法分析其时间复杂度时往往比较困难。本文提出了用组合数学中的递推关系理论来分析一些特殊的递归算法的时间复杂度，并同时得出三个推论，在算法的分析与研究方面具有一定的参考价值。[关键词]时间复杂度，递归，母函数1.引言一个程序在计算机上运行时所耗费的时间取决于对源程序进行编译所需时间、计算机执行每条指令所需时间、程序中指令重复执行的次数。前两条依赖于实现算法的计算机软件、硬件系统，亦即依赖于实现算法所用语言的编译程序的性能和计算机本身

2、的速度。因此习惯上常常用重复执行次数最多的语句频度来分析算法的时间复杂度，记为t（n），其中n为问题的规模或大小。例如对n个存放于数组a[n]中的数进行选择法排序的算法：for(i=0;i

3、-n)=O(n2).对一个算法进行时间复杂度的分析方式有多种，但有时候一个算法的时间复杂度并不象上面的例子那样可以轻易地分析出来。也许对一个for循环、对一个单一语句的时间复杂度可以马上分析出来，但遇到递归算法时，则无法轻易地分析出其时间复杂度，而递归算法又是程序设计时经常采用的有效手段，如求解n阶hanoi塔问题的递归算法：//将n个盘从one座借助two座，移动到three座voidhanoi(intn,charone,chartwo,charthree){if(n==1){printf("%c—>%c",one,three);}

4、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项的递归算法等。对于这些递归算法，可以利用组合数学中的母函数与递推关系理论来分析其时间复杂度。1.利用递推关系理论分析递归算法的时间复杂度2.1相关概念1）k阶常系数线性递推关系式与特征多项式若母函数G(x)=a0+a1x+a2x2+...，所对应的序列{an}

5、满足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个不

6、同的根β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

7、(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

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