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

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

引言：时间复杂度的求解，在此都是以实例进行讲解，各位读者可以从中慢慢理解；以下所有的案例都是以Python语言编写！

二叉树先序中序非递归算法

递归算法转换为非递归算法

案例一：求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中文版]

《Python开发技术详解》.( 周伟,宗杰).[高清PDF扫描版+随书视频+代码]

Python脚本获取Linux系统信息

在Ubuntu下用Python搭建桌面算法交易研究环境

Python 的详细介绍：请点这里
Python 的下载地址：请点这里

本文永久更新链接地址：