Python数据结构与算法--算法分析   发布时间:2017-09-06 19:45:14

Python数据结构与算法--算法分析 一个有趣的问题经常出现,那就是两个看似不同的程序,到底哪个更好呢?

要回答这个问题, 我们必须知道程序和代表程序的算法有很大的区别. 算法是一个通用的, 解决问题的一条条的指令. 提供一个解决任何具有指定输入的实例问题方法, 算法产生期望的结果. 一个程序, 另一方面, 是将算法用某一门编程语言代码实现. 有很多的程序实现的同一算法, 取决于程序员和编程语言的使用.

进一步的探究这种差异, 考察下面的函数代码. 这个函数解决一个简单的问题, 计算前n个自然数的和. 解决方案遍历这 n 个整数, 相加后赋值到累加器.

def sumOfN(n):

theSum = 0

for i in range(1,n+1):

theSum = theSum + i

return theSum

print(sumOfN(10))

接下来看下面的代码. 第一眼看上去感觉很奇怪, 但是深入理解之后你将发现这个函数和上面的函数完成同样的工作. T原因是这个函数不是那么明显,代码难看. 我们没有使用好的变量名导致可读性很差, 并且还声明了没有必要声明的变量.

def foo(tom):

fred = 0

for bill in range(1,tom+1):

barney = bill

fred = fred + barney

return fred

print(foo(10))

到底哪段代码更好呢.问题的答案取决于你的标准.如果你只关注可读性,函数sumOfN 肯定比 foo 好. 事实上, 你可能在你的编程启蒙课上见到过很多教你编写可读性好和易于理解的程序的例子. 然而在这里, 我们还对算法感兴趣.

作为替代空间的需求, 我们基于它们执行时间来分析和比较算法. 这种度量有时候被称为算法的“执行时间”或"运行时间". 我们测量 sumOfN 函数执行时间的一种方法是做个基准分析. 在Python, 我们可以通过一个函数针对我们所使用的系统上标记程序的起始和结束时刻. 在 time 模块有一个被称为 time 的函数,将返回系统的当前时间. 通过两次调用这个函数, 起始和结束, 然后计算差值, 我们可以得到准确的执行时间.

Listing 1

import time

def sumOfN2(n):

start = time.time()

theSum = 0

for i in range(1,n+1):

theSum = theSum + i

end = time.time()

return theSum,end-start

Listing 1 展示了sumOfN 函数在求和前后的时间开销. 测试结果如下:

>>>for i in range(5):

print("Sum is %d required %10.7f seconds"%sumOfN(10000))

Sum is 50005000 required 0.0018950 seconds

Sum is 50005000 required 0.0018620 seconds

Sum is 50005000 required 0.0019171 seconds

Sum is 50005000 required 0.0019162 seconds

Sum is 50005000 required 0.0019360 seconds

我们发现时间相当的一致并且都平均花费 0.0019 秒执行程序. 那么假如我们将n增大到 100,000 会怎样呢?

>>>for i in range(5):

print("Sum is %d required %10.7f seconds"%sumOfN(100000))

Sum is 5000050000 required 0.0199420 seconds

Sum is 5000050000 required 0.0180972 seconds

Sum is 5000050000 required 0.0194821 seconds

Sum is 5000050000 required 0.0178988 seconds

Sum is 5000050000 required 0.0188949 seconds

>>>

再次, 时间更长, 非常的一致, 平均10倍的时间. 将 n 增大到 1,000,000 我们达到:

>>>for i in range(5):

print("Sum is %d required %10.7f seconds"%sumOfN(1000000))

Sum is 500000500000 required 0.1948988 seconds

Sum is 500000500000 required 0.1850290 seconds

Sum is 500000500000 required 0.1809771 seconds

Sum is 500000500000 required 0.1729250 seconds

Sum is 500000500000 required 0.1646299 seconds

>>>

在这种情况下, 平均执行时间又一次被证实是之前的10倍.

现在来看一下 Listing 2, 提出了一个不同的解决求和问题的方法. 这个函数, sumOfN3, 运用了一个等式:∑ni = (n+1)n/2来计算前 n 个自然数取代循环计算.

Listing 2

def sumOfN3(n):

return (n*(n+1))/2

print(sumOfN3(10))

如果我们针对 sumOfN3 做一些测试, 使用5种不同的n值(10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000), 我们得到下面的结果:

Sum is 50005000 required 0.00000095 seconds

Sum is 5000050000 required 0.00000191 seconds

Sum is 500000500000 required 0.00000095 seconds

Sum is 50000005000000 required 0.00000095 seconds

Sum is 5000000050000000 required 0.00000119 seconds

对于这个输出,有两个方面需要注意. 第一, 上面程序的运行时间比前面的任意一个的运行时间都短. 第二, 无论n为多大执行时间都是一致的.

但是这个标准真正地告诉我们什么?直观地说, 我们可以看到,迭代的解决方案似乎是因为一些程序步骤被重复而做更多的工作. 这是它占用更多运行时间可能的原因. 当我们增加 n的时候循环方案执行时间也在增加. 然而,有一个问题. 如果我们跑相同的功能在不同的计算机或使用不同的编程语言,我们可能会得到不同的结果. 如果是老式计算机将可能在 sumOfN3上执行更多的时间.

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:十堰网站制作 http://shiyan.666rj.com