[1]方贤进,潘地林,管建军.用母函数理论分析递归算法的时间复杂度[J].南京师范大学学报(工程技术版),2005,05(01):092-94.
　FANG X ianjin,PAN Dilin,GUAN Jianjun.Analyzing the T ime Complexity of Recursion A lgorithm by Applying Generation Function Theory[J].Journal of Nanjing Normal University(Engineering and Technology),2005,05(01):092-94.
点击复制

用母函数理论分析递归算法的时间复杂度
分享到：

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
05卷
期数:
2005年01期
页码:
092-94
栏目:
出版日期:
2005-03-30

文章信息/Info

Title:
Analyzing the T ime Complexity of Recursion A lgorithm by Applying Generation Function Theory
作者:
方贤进; 潘地林; 管建军
安徽理工大学计算机系, 安徽淮南232001
Author(s):
FANG X ianjin;  PAN Dilin;  GUAN Jianjun
tim e com plex ity, recursion, genera tion function
关键词:
时间复杂度;  递归;  母函数
摘要:
对算法进行时间复杂度分析是算法分析与研究的重要内容, 而对递归算法分析其时间复杂度时往往比较困难. 提出了用组合数学中的母函数与递推关系理论来分析一些特殊的递归算法的时间复杂度, 并同时得出三个推论, 在算法的分析与研究方面具有一定的参考价值.
Abstract:
Ana lyz ing the time comp lex ity of one a lgo rithm is very important to the ana ly sis of and research on the a l-go rithm. It is usua lly difficu lt to ana lyze the tim e com plex ity o f a recursiv e a lgor ithm. In th is paper, the theo ries o f g eneration function and recursive relation in com bina to rics is used to ana ly ze the tim e com plex ity of som e specia l re-cursive algorithm, w ith three conc lusions reached s imu ltaneously, w hich is of v aluable re ference to the ana lys is and research on a lgo rithm.

参考文献/References:

[ 1] 严蔚敏, 吴伟民. 数据结构[M ]. 北京: 清华大学出版社, 1991. 303 -305.
[ 2] 谭浩强. C 程序设计[M ] . 第2版. 北京: 清华大学出版社, 2003. 160- 163.
[ 3] 黄国瑜, 叶乃箐. 数据结构( C 语言版) [M ] . 北京: 清华大学出版社, 2001. 13 -18.
[ 4] 卢开澄. 组合数学[M ]. 北京: 清华大学出版社, 2000. 48- 79.
[ 5] 杨骅飞, 王朝瑞. 组合数学及其应用[M ] . 北京: 北京理工大学出版社, 1992. 40- 48.

备注/Memo

备注/Memo:
作者简介: 方贤进( 1970 - ) , 讲师, 主要从事算法分析与计算、计算机网络等方面的教学与研究. E-m a il: xjfang@ aust. edu. cn
更新日期/Last Update: 2013-04-29