[Python]递归算法时间复杂度

引言：时间复杂度的求解，在此都是以实例进行讲解，各位读者可以从中慢慢理解；以下所有的案例都是以Python语言编写！二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm递归算法转换为非递归算法 http://www.linuxidc.com/Linux/2014-06/102934.htm案例一：求a的n次方代码如下： def exp1（a,n）: if n == 1: return a else: return a*exp2（a,n-1）分析：1、问题的规模是n；2、当规模为1是结束；3、假设T（n）表示规模为n的问题所需的步骤数；求解： T（n）=3+T（n-1）//注释：3表示一次循环中所做的操作数，一次是if的比较“==”，二次是递归中的n-1中的“-”，三次是a*exp1（a,n-1）中的“*”，规模每减少一次，就进行上述三次操作。分解：T（n）=3+3+T（n-2） =3+3+3+T（n-3） ...... =3*K+T（n-K）当规模为1时返回结果，即n-K=1-》K=n-1，将K带入T（n） T（n）=3（n-1）+T（1）=3n-3+2=3n-1//注释：T（1）时规模为1，进行了两次操作。综上：上述程序时间复杂度为：O（n）《Python核心编程第二版》.（Wesley J. Chun ）.[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm《Python开发技术详解》.（周伟,宗杰）.[高清PDF扫描版+随书视频+代码] http://www.linuxidc.com/Linux/2013-11/92693.htmPython脚本获取Linux系统信息 http://www.linuxidc.com/Linux/2013-08/88531.htm在Ubuntu下用Python搭建桌面算法交易研究环境 http://www.linuxidc.com/Linux/2013-11/92534.htmPython 的详细介绍：请点这里
Python 的下载地址：请点这里本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-07/104546.htm