我们先来看几个概念
1、算法
算法：一种解决问题的方法和思想
2、时间复杂度
计算 1 + 2 + 3 + … + 100
先看下面这段代码：
tot = 0 for x in range(1,101): tot += x print(tot)分析：
进入循环体后，tot += x 等价于 tot = tot + x
tot + x为一个基本运算
=赋值运算符为一个基本运算
循环体执行了 100次，则程序一共执行100 * 2个基本步骤
如果我们要计算1000以内的自然数之和，那么只需要修改成以下代码：
tot = 0 for x in range(1,1001): tot += x print(tot)程序需要执行1000 * 2个基本步骤
通过上面的例子，我们知道100次，1000次只是问题计算规模的大小，那么我们就定义一个变量n来代表计算问题的规模
什么是时间复杂度？
时间复杂度就是程序执行的基本步骤
时间复杂度分析
tot = 0 for x in range(1,101): tot += x print(tot)这段代码的时间复杂度为100 * 2
对于计算n以内的自然数之和，时间复杂度为 2 * n，记作：
T(n) = 2 * n
n : 代表计算问题的规模大小
3、大O记法
实际应用中，我们并不关心其具体的实际执行步骤，而是更加关心数量级和趋势，认为T(n) = 2 * n 和 T(n) = n 是同一个数量级的，都是n
什么是大O记法
大O记法就是忽略次要项和常数项
T(n) = 2 * n 的大O记法就是 O(n) = n
常见时间复杂度
时间复杂度举例大O表示法术语12O(1)常数阶2n+3O(n)线性阶3n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶