来看一段程序,完成从 1 到 n 的累加,输出总和

设置累计变量 = 0,从 1 到 n 循环,逐次累加到累计变量,返回累计变量

def sum0fN(n):
    theSum = 0
    for i in range(1, n+1):
        theSum += i
    return theSum
print(sum0fN(10))

运行时间检测

用 python库 time 检测总运行时间,返回累计和,以及运行时间(秒)

import time
def sum0fN2(n):
    start = time.time()
    theSum = 0
    for i in range(1, n+1):
        theSum += i
    end = time.time()
    return theSum, end - start

for i in range(5):
    print("Sum is %d required %10.7f seconds" % sum0fN2(10000))

电脑有点渣,运行的时间还是比较多的,约为0.001

Sum is 50005000 required  0.0013449 seconds
Sum is 50005000 required  0.0012052 seconds
Sum is 50005000 required  0.0012829 seconds
Sum is 50005000 required  0.0013096 seconds
Sum is 50005000 required  0.0013196 seconds

如果累加到 100,000?

看起来运行时间增加到 10,000 的 10

Sum is 5000050000 required  0.0123219 seconds
Sum is 5000050000 required  0.0096383 seconds
Sum is 5000050000 required  0.0096786 seconds
Sum is 5000050000 required  0.0095470 seconds
Sum is 5000050000 required  0.0096965 seconds

进一步累加到 1,000,000?

运行时间又是 100,000 的 10

Sum is 500000500000 required  0.1023099 seconds
Sum is 500000500000 required  0.1013489 seconds
Sum is 500000500000 required  0.1017647 seconds
Sum is 500000500000 required  0.0983462 seconds
Sum is 500000500000 required  0.0983982 seconds

另一种无迭代的累计

利用求和公式

def sum0fN3(n):
    theSum = (n * (n+1)) / 2
    return theSum

采用同样的方法检测运行时间

Sum is 50005000 required  0.0000026 seconds		# 10,000
Sum is 5000050000 required  0.0000033 seconds		# 100,000
Sum is 500000500000 required  0.0000031 seconds		# 1,000,000
Sum is 50000005000000 required  0.0000031 seconds	# 10,000,000
Sum is 5000000050000000 required  0.0000031 seconds	# 100,000,000

需要关注的两点:

  • 这种算法的运行时间比前种短很多
  • 运行时间与累计对象 n 的大小没有关系(前种算法是倍数增长关系)

运行时间检测的分析

关于运行时间的实际检测,有点问题:

  • 编程语言
  • 运行环境

同一种算法,采用不同的编程语言编写,放在不同的机器上运行,得到的运行时间会不一样,有时候会大不一样

比如把非迭代算法放在老旧机器上跑,甚至可能慢过新机器上的迭代算法

需要更好的方法来衡量算法运行时间:

这个指标与具体的机器、程序、运行时段都无关