引入
先看一道题
如果 a+b+c=1000，且 a2+b2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
解法一：
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if (a + b + c == 1000) and (a ** 2 + b ** 2 == c ** 2):
print(a, b, c)
end_time = time.time()
print("total time : {}".format(end_time - start_time))
运行结果：
0 500 500
200 375 425
375 200 425
500 0 500
total time : 120.97856378555298
注意运行时间为：120.97856378555298秒
解法二：
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
c = 1000 - a - b
if a ** 2 + b ** 2 == c ** 2:
print(a, b, c)
end_time = time.time()
print("total time : {}".format(end_time - start_time))
运行结果：
0 500 500
200 375 425
375 200 425
500 0 500
total time : 1.074127435684204
注意运行时间为：1.074127435684204秒
执行时间反应算法效率
对于用一个问题，给出了两种解法，但是两种解法在时间上大不相同，解法一比解法二慢上了很多，由此可知，实现算法程序的执行时间可以反映出算法的效率，即算法的优劣。
但是只靠时间来衡量算法的效率是可靠的吗？假如我们把解法二在一台配置、性能很低的电脑上运行，执行时间不一定比解法一快上多少。所以说单靠执行时间来说，不能衡量一个算法的执行效率优劣，程序的运行离不开计算机环境（包括硬件和操作系统），这些客观因素也会反映在程序的运行时间上，那么如何客观的来衡量算法的效率呢？
大O表示法
对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
大O表示法"表示程序的执行时间或占用空间随数据规模的增长趋势。
时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)。
时间复杂度表示代码执行时间与数据规模之间的增长规律。
对于解决方法一用大O表示法来计算时间复杂度为：T(n) = O(nnn) = O(n^3)
对于解决方法二用大O表示法来计算时间复杂度为：T(n) = O(nn(1+1)) = O(nn)=O(n^2)
时间复杂度的计算
1、基本操作：即只有常数项，其时间复杂度为O(1)。
2、顺序结构：时间复杂度按加法计算。
3、循环结构：时间复杂度按乘法计算。
4、分支结构：时间复杂度取最大值。
基本流程：
①找出基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
②计算基本语句执行次数的数据级：要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。
③大O表示法记录
下面看几个例子：
①线性阶：一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数呈直线增长。
for i in range(n):
print(i)
循环体代码需要执行n次，所以时间复杂度为O(n)
②平方阶
for i in range(n):
for j in range(n):
print("hello")
外层循环每执行一次，内层循环就需要执行n次，所以总程序需要执行n*n次，所以时间复杂度为O(n^2)。
③对数阶
i = 1
while (i < n):
i = i * 2
对于循环体 i = i * 2，由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。
于是由2^x = n得到x = log(2)n，所以这个循环的时间复杂度为O(logn)。
最坏时间复杂度
比如我们要在一个list中查找一个数字，最好的情况就是第一个数字就是，这时候的算法时间复杂度就是O(1),最坏的情况就是这个数字在最后，这时候的算法时间复杂度为O(n)。
通常有三种可能：最坏、最优和平均时间复杂度。
对于最坏时间复杂度提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作，因此通常我们只关心最坏时间复杂度。
对于最优时间复杂度，表示一种理想情况，没有什么实际的参考价值。
对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
常见算法时间复杂度
常见时间复杂度之间的关系
大小关系：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
