首页 > 代码库 > 计算机科学及编程导论(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:

  1. 将n-1个圆盘移动到sparestack
  2. 将第n个圆盘移动到tostack
  3. 然后将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²)