首页 > 代码库 > 计算机科学及编程导论(8)算法的复杂度
计算机科学及编程导论(8)算法的复杂度
1.基于问题规模的复杂度计算方法
在考虑时间效率的时候,面临以下两个问题:输入规模以及步骤。
输入规模受很多因素影响:参数大小、参数类型(数组、元组的存取小绿是不同的),而且不同操作步骤(加减、判断)时间也不是相同的,为了方便计算,我们需要建立以下的假设:
假设从计算机取得任何变量的时间是相同的
假设基本操作时间恒定
接下来就可以考虑以下几种情况:
最好情况:何种输入会使得程序的运行时间最短?
最坏情况:何种输入会使得程序的运行时间最长?
平均情况
如果考虑平均情况的话,就要去设想问题输入规模的分布情况,这样大大增加了计算的难度。因此,我们通常考虑的是最坏的情况,因为最坏情况能够让我们知道程序运行时间的上限,能够避免意外的发生。
2. 实例分析
实例一:计算a的b次方
方法一:常规方法
# 方法一:用常规方法计算a的b次方def exp1(a,b): ans = 1 #一次 while (b>0): #3b次 ans *= a b -= 1 return ans #一次
程序执行的步骤为:1 + 3b + 1 = 2 + 3b次
b = 300 , 执行次数:902;
b = 3000, 执行次数:90002;
b = 30000,执行次数,9000002;
可以发现,随着b的增长,2和3的作用越来越小,因为单单b就可以体现出函数的增长的上限。因此我们引入了Big O的概念:
Big O:upper limit to growth of function as the input gets large.
大 O:当问题规模变大时候对应的解决方法的增长上限
因此,方法一的时间复杂度为O(b).
方法二:递归方法
#方法二:递归方法求a的b次方def exp2(a,b): if b == 1: #一次 return a else: return a*exp2(a,b-1) #2次,一次乘法,一次减法
首先我们假设时间为t(b),可以进行如下推导:
t(b)=3+t(b-1)
=3+3+t(b-2)
=...
=3k + t(b-k)
其中,b-k=1,代入,因为t(1)=2,所以,可得
t(b)=3b-1
因此,方法二的时间复杂度仍然为O(b)
方法三:根据b奇偶性的不同分别进行判断
a**b:
b为偶数:(a*a)**(b/2),规模减半
b为奇数:a*(a**(b-1))
#8.3 分类法求平方根def exp3(a,b): if b == 1: return a if b%2 ==0: return exp3(a*a,b/2) else: return a*exp3(a,b-1)
可以简单计算出时间复杂度:
b为偶数: t(b) = 5 + t(b/2)
b为奇数:t(b) = 5 + t(b-1) = 10 + t(b-1/2)
也就是说,没经过两轮,规模减半,所以时间复杂度为O(logb)
实例2:时间复杂度为O(n²)的例子
这个例子很简单,不多说明
#8.4def g(n): x=0 for i in range(n): for j in range(m):x += 1 return x
实例3:汉罗塔问题
主要介绍如何从递归角度来考虑汉罗塔问题
解题思路:
设三个圆盘的名称分别为为:fromstack(起始圆盘)、sparestack(空余圆盘)、tostack(目的圆盘)
如果个数为1,直接从fromstack移动到tostack
如果个数为n:
- 将n-1个圆盘移动到sparestack
- 将第n个圆盘移动到tostack
- 然后将n-1个圆盘移动到tostack
代码:
#8.4 用递归方法求解汉罗塔问题def Towers(size,fromStack,toStack,spareStack): if size == 1: print(‘Move disk from ‘,fromStack,‘to‘,toStack) else: Towers(size-1,fromStack,spareStack,toStack) Towers(1,fromStack,toStack,spareStack) Towers(size-1,spareStack,toStack,fromStack)
该算法的时间复杂度为O(n²)