关于递归算法时间复杂度分析的探讨

《关于递归算法时间复杂度分析的探讨》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第18卷第4期浙江万里学院学报Vol.18No.42005年8月JournalofZhejiangWanliUniversityAug.2005关于递归算法时间复杂度分析的探讨邓芳（浙江万里学院，宁波315100）摘要：通过递归实例，介绍了递归算法时间复杂度的一类分析方法.说明了在分析问题时递归思想的作用，但在问题实现时最好采用非递归算法.关键词：递归；语句频度；时间复杂度中图分类号：TP311.12文献标识码：A文章编号：1671－2250（2005）04－0024－04收稿日期：2005－03－22作者简介：邓芳，浙江万里学

2、院计算机与信息学院讲师.1引言[1]递归是指对一个问题的求解，可以通过同一问题的更简单的形式的求解来表示.并通过问题的简单形式的解求出复杂形式的解.递归是解决一类问题的重要方法.递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的.但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省.以下讨论递归的时间效率分析方法，以及与非递归设计的时间效率的比较.2时间复杂度的概念及其计算方法算法是对特定问题求解步骤的一种描述.对于算法的优劣有

3、其评价准则，主要在于评价算法的时间效率，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然的联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量.算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n).算法时间度量记作：T（n）=O（f（n））它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂[2]度，简称时间复杂度.例如下列程序段：（1）x=x+1;（2）for(i=

4、1;i<=n;i++)x=x+1;（3）for(j=1;j<=n;j++)for(k=1;k<=n;k++)x=x+1.2以上三个程序段中，语句x=x+1的频度分别为1，n，n，则这三段程序的时间复杂度分别为O2（1），O（n），O（n）.求解过程为：先给出问题规模n的函数的表达式，然后给出其时间复杂度T（n）.但是在现实程序设计过程中，往往遇到的问题都是比较复杂的算法，就不能很容易地写出规模n的表达式，也比较难总结其时间复杂度.递归函数就是属于这种情况.下面举例说明递归函数的时间复杂度的分析方法.3递归函数递归函数是一个使用自

5、身定义的函数，即此函数可以直接或间接地调用自己.递归是程序设计中一个强有力的工具，是一种分而治之的把复杂问题分解为简单问题的求解方法.很多数学函数或二叉树等第4期邓芳：关于递归算法时间复杂度分析的探讨25数据结构都是递归定义的.例1求阶乘n!，递归公式为1若n=0Fact(n)=n*Fact(n-1)若n>0递归算法如下：intfac(intn){if(n==0)return1;elsereturnn*fac(n-1);}例2Fibonacci数列，其递归公式为：0若n=0Fib(n)=1若n=1Fib(n-1)+Fib(n-2

6、)其它情形递归算法如下：intfib(intn){ints;if(n==0)return0;if(n==1)return1;s=fib(n-1)+fib(n-2);returns;}从上述采用递归方法来设计算法，可以达到算法思路清晰、简单易懂的效果.4递归算法时间复杂度分析4．1阶乘n!的递归算法的时间复杂度时间复杂度是由语句频度分析得来.递归算法中重复执行的语句主要是调用.所以递归算法的时间复杂度分析主要是分析递归算法中递归函数调用的次数，并给出其调用次数的函数f(n).如例1中，当n=5时fan(5)的调用情况如图1所示：从

7、图1中可以总结出fan(n)函数被重复调用了n+1次.由此可以写出f(n)=n+1.其时间复fan(4)杂度T(n)=O(n).4．2Fibonacci数列的时间复杂度4fan(3)用4．1所使用的方法求解简单递归算法的3fan(2)时间复杂度的方法，对于Fibonacci数列来说就不适用.在Fibonacci数列的公式中我们发现：2fan(1)计算第n项的数列值，就要先计算第n-1与第n-2项的值.这就很难计算出要递归调用的次1fan(0)数，所以就不能单纯地用上述方法来求解时间复杂度.图1n=5时fan(5)的调用情况[3]

8、对于Fibonacci数列可以采用母函数的方法来计算Fibonacci数列的时间复杂度：26浙江万里学院学报2005年8月设Fn为计算第n项数列值的运算量，则有Fn=Fn-1—Fn-2；且F0=F1=1.2设G(x)=F1x+F2x+⋯3x:FFF=+3214x