文档介绍：第18卷第4期浙江万里学院学报
2005 年 8 月 Journal of Zhejiang Wanli University Aug. 2005

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

邓芳
(浙江万里学院,宁波 315100)

摘要:通过递归实例,介绍了递归算法时间复杂度的一类分析方法. 说明了在分析问题时递归思想的作
用,但在问题实现时最好采用非递归算法.
关键词:递归;语句频度;时间复杂度
中图分类号: 文献标识码:A 文章编号:1671-2250(2005)04-0024-04
收稿日期:2005-03-22
作者简介:邓芳,浙江万里学院计算机与信息学院讲师.

1 引言
递归[1]是指对一个问题的求解,可以通过同一问题的更简单的形式的求解来表示. 并通过问题的简单
形式的解求出复杂形式的解. 递归是解决一类问题的重要方法. 递归程序设计是程序设计中常用的一种
方法,它可以解决所有有递归属性的问题,并且是行之有效的. 但对于递归程序运行的效率比较低,无
论是时间还是空间都比非递归程序更费,若在程序中消除递归调用,则其运行时间可大为节省. 以下讨
论递归的时间效率分析方法,以及与非递归设计的时间效率的比较.
2 时间复杂度的概念及其计算方法
算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则,主要在于评价算法的时间效
率,算法的时间通过该算法编写的程序在计算机中运行的时间来衡量,所花费的时间与算法的规模 n 有
必然的联系,当问题的规模越来越大时,算法所需时间量的上升趋势就是要考虑的时间度量.
算法的时间度量是依据算法中最大语句频度(指算法中某条语句重复执行的次数)来估算的,它是
问题规模 n 的某一个函数 f(n). 算法时间度量记作:T(n)=O(f(n))
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的时间复杂
度,简称时间复杂度[2].
例如下列程序段:
(1)x=x+1;(2)for(i=1;i<=n;i++) x=x+1;(3)for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1.
以上三个程序段中,语句x=x+1 的频度分别为 1,n,n2,则这三段程序的时间复杂度分别为O
(1),O(n),O(n2).
求解过程为:先给出问题规模 n 的函数的表达式,然后给出其时间复杂度 T(n).
但是在现实程序设计过程中,往往遇到的问题都是比较复杂的算法,就不能很容易地写出规模 n 的
表达式,也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度
的分析方法.
3 递归函数
递归函数是一个使用自身定义的函数,即此函数可以直接或间接地调用自己. 递归是程序设计中一
个强有力的工具,是一种分而治之的把复杂问题分解为简单问题的求解方法. 很多数学函数或二叉树等
第 4 期邓芳:关于递归算法时间复杂度分析的探讨 25
数据结构都是递归定义的.
例 1 求阶乘 n!,递归公式为

1 若 n=0