引言:时间复杂度的求解,在此都是以实例进行讲解,各位读者可以从中慢慢理解;以下所有的案例都是以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搭建桌面算法交易研究环境