下面四组代码,哪一组运行时间最短?

print('konbanwa')
for i in range(n):
    print('konbanwa')
for i in range(n):
    for j in range(n):
        print('konbanwa')
for i in range(n):
    for j in range(n):
        for k in range(n):
            print('konbanwa')

那么用什么方式表现算法运行的快慢?

时间复杂度:用来评估算法运行效率的式子

用大写的O来表示算法的运行时间,记作:O(n)

频度表示算法中所有原操作的执行次数;一个算法的执行时间可以用频度计量。

频度是问题规模n的函数,用T(n)表示。

算法的执行时间大致等于原操作所需时间*T(n),即T(n)与执行时间成正比;为此用T(n)表示算法的执行时间,比较不同的T(n)的大小得出算法的好坏。

def matrixadd(A,B,C,n):
    for i in range(n):    #语句1
        for j in range(n):    #语句2
            C[i].append(A[i][j]+B[i][j])    #语句3

语句1的循环控制变量i从0增加到n,当i=n时终止,因此语句1的频度为n+1;其循环体执行了n次。

语句2是语句1的循环体,执行n次;但语句2本身要执行n+1次(同上),所以语句2的频度为n(n+1)。

同理,语句3的频度为n2

该算法中所有语句的频度之和T(n)=n+1+n(n+1)+n2

算法的执行时间不是绝对的时间统计,算法的时间复杂度用T(n)的数量级表示,即为T(n)找到一个上界f(n),T(n)的上界f(n)可能会有多个,只取最紧凑的上界,即只求T(n)的最高阶,忽略低阶项和常系数。

例如以上算法的时间复杂度为O(n2)。

print('konbanwa')    # O(1)
for i in range(n):    # O(n)
    print('konbanwa')
for i in range(n):    # O(n2)
    for j in range(n):
        print('konbanwa')
for i in range(n):    # O(n3)
    for j in range(n):
        for k in range(n):
            print('konbanwa')

以下算法的时间复杂度是否正确?

print('konbanwa')        # O(3)×    O(1)√
print('konbanwa')
print('konbanwa')
for i in range(n):         # O(n2+n)×    O(n2)√
    print('konbanwa')
    for j in range(n):
        print('konbanwa')

在一个没有循环或循环次数与问题规模n无关的算法中,算法的频度与规模n无关,记作O(1),也称常数阶。

评估以下代码的时间复杂度

while n>1:
    print(n)
    n=n//2

当n=64时的输出:

64
32
16
8
4
2

:O(log2n)或O(logn)

当算法中出现循环减半时,式子会出现logn

小结

  • 时间复杂度是用来评估算法运行效率的式子
  • 一般来说,时间复杂度高的算法比时间复杂度低的算法慢
  • 常见的时间复杂度(按效率排序)O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)<O(2n)<O(n!)
  • 复杂问题的时间复杂度 O(n!) O(2n) O(nn) O(n!)

我们所度过的每个平凡的日常,也许就是连续发生的奇迹