1、执行时间反映算法效率

对上文1.1中最后部分的程序进行优化
优化前：

  1. #输出满足条件：a^2+b^2=c^2 且 a+b+c=1000 的3个数
  2. import time
  4. start=time.time()
  5. for a in range(0,1000):
  6.     for b in range(0,1000):
  7.         c=1000-a-b
  8.         if a**2+b**2==c**2:
  9.             print('a=%s,b=%s,c=%s' % (a, b, c))
  10. end=time.time()
  11. print(end-start) #4.189582109451294

优化后：

  1. #输出满足条件：a^2+b^2=c^2 且 a+b+c=1000 的3个数
  2. import time
  4. start=time.time()
  5. for a in range(0,501):
  6.     for b in range(a,501):
  7.         c=1000-a-b
  8.         if a**2+b**2==c**2:
  9.             print('a=%s,b=%s,c=%s'%(a,b,c)+'\n'+'a=%s,b=%s,c=%s'%(b,a,c))
  10. end=time.time()
  11. print(end-start) #0.47472620010375977

对于同一问题，我们用了两种不同算法来解决，从中可以看出在我们优化后，算法程序的运行时间缩短了10倍，从而我们得出结论：算法程序的执行时间可以反映算法的效率（优劣）。

1.1 单靠执行时间来判断是否可靠？

  1. 测试结果非常依赖测试环境

    • 同一段代码在不同的处理器中运行，时间是完全不一样的（i9比i3快得多）；
    • 不同代码的比较放在不同机器中测试，最终得出的结果也可能是完全相反的。

  2. 受数据规模的影响

    • 比如对同一个排序算法，要排序的数据是：乱序的、有序的（已经排好了）两种数据，显然二者之间的执行时间是完全不一样的（有序比乱序的快多了），不同数据规模对同一算法的影响是很大的。
  • 因此单靠执行时间来衡量算法的效率是不严谨的，所以我们引入了更为严谨的时间复杂度来衡量算法的效率。

2、时间复杂度T(n)

2.1 时间复杂度定义

  • 算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间，也叫作渐进时间复杂度；是一个增量
  • 时间复杂度常用大O符号表述；记为T(n)
  • T(n)=O(f(n))，其中：
    • O：表示执行时间和f(n)成正比；
    • f(n)：代码执行次数；
    • n：数据规模；

2.2 大O表示法

  • 用大O来反映T(n)和f(n)的关系，称之为大O表示法。
  • T(n)=O(3*n^2+6n+6)

2.3 时间复杂度分析

  • 可以忽略掉公式中的常数项，系数，低阶项，只保留最高阶项；

（1）一段代码的时间复杂度：可以只看循环执行次数最多的部分代码；
比如：

  1. def cal(n):
  2.     sum = 0
  3.     i = 1
  4.     for k in range(3):
  5.         for i in range(n+1):
  6.             for j in range(n):
  7.                 sum += i+j
  8.                 j+=1
  9.             i+=1
  10.     return sum

由程序可得：T(n)=O(3*n+3) 可以等价为 T(n)=O(n^2)，即相当于只看内层的两个for循环即可，因为他们的执行次数最多。

（2）总的时间复杂度：取最大量级来表示
比如：

  1. import time
  2. start=time.time()
  3. def cal(n):
  4.     sum = 0
  5.     i = 1
  6.     for k in range(3):
  7.         for i in range(n+1):
  8.             for j in range(n):
  9.                 sum += i+j
  10.                 j+=1
  11.             i+=1
  12.     return sum
  14. def fn(n):
  15.     start=time.time()
  16.     for a in range(0,n):
  17.         for b in range(0,n):
  18.             for c in range(0,n):
  19.                 if a**2+b**2==c**2 and a+b+c==1000:
  20.                     print(a,b,c)
  22. a=fn(100)
  23. b=cal(100)
  24. end=time.time()
  25. print(end-start,a,b)

这个程序的时间复杂度T(n)=O(n^3+n^2+1) ==>T(n)=O(n^3)

总结：算法的时间复杂度等于量级最大的时间复杂度

（3）**分析算法时，我们一般考虑最坏时间复杂度；**
对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。

  1. 对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
  3. 对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中**一定能完成工作**。<br />因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。