为什么需要复杂度分析
如何进行复杂度分析
对于时间复杂度的分析，通常使用大O复杂度表示法，表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
用公式表示，就是 T(n) = O(f(n))表示，其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 表示数据的规模。
由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时可以忽略这些项。
具体分析的时候，有下列三个方法：
常见的时间复杂度
按照数量级递增，常见的时间复杂度量级有：
其中，最后两种情况是非常糟糕的情况，当然 O(n^2) 也是一个可以继续进行优化的情况。
接下来简单介绍上述复杂度中的几种比较常见的：
O(1)
O(1) 表示的是常量级时间复杂度，也就是只要代码的执行时间不随 n 的增大而增长，都记作 O(1) 。一般只要算法不包含循环语句和递归语句，时间复杂度都是 O(1)
像下列代码，有 3 行，但时间复杂度依然是O(1)，而非 O(3)。
a = 3
b = 4
print(a + b)
O(logn)、O(nlogn)
O(logn) 也是一个常见的时间复杂度，下面是一个 O(logn) 的代码例子：
i = 1
count = 0
n = 20
while i <= n:
count += 1
i *= 2
print('while 循环运行了 {} 次'.format(count))
这段代码其实就是每次循环都让变量 i 乘以 2，直到其大于等于 n，这里我设置 n=20，然后运行了后，输出结果是循环运行了 5 次。
实际上这段代码的结束条件，就是求 2^x=n 中的 x 是等于多少，那么循环次数也就知道了，而求 x 的数值，方法就是 ，那么时间复杂度就是
假如上述代码进行简单的修改，将 i *= 2 修改为 i *= 3 ，那么同理可以得到时间复杂度就是 。
但在这里，无论是以哪个为对数的底，我们都把对数阶的时间复杂度记为 O(logn) 。
这里主要原因有两个：
基于这两个原因，对数阶的时间复杂度都忽略了底，统一为 O(logn) 。
至于 O(nlogn) ，根据乘法法则，只需要将对数阶复杂度的代码，运行 n 次，就可以得到这个线性对数阶复杂度了。
注意， O(nlogn) 是非常常见的时间复杂度，常用的排序算法如归并排序、快速排序的时间复杂度都是 O(nlogn)
O(m+n)、O(m*n)
前面介绍的情况都是只有一个数据规模 n ，但这里介绍有两个数据规模的情况--m 和 n。
# O(m+n)
def cal(n, m):
result = 0
for i in range(n):
result += i
for j in range(m):
result += j * 2
return result
简单的代码示例如上述所示，如果事先无法评估 m 和 n 的量级大小，那么这里的时间复杂度就没法选择量级最大的，所以其时间复杂度就是 O(m+n) 。
同理，对于嵌套循环，就是 O(m*n) 的时间复杂度了。
最好、最坏、平均、均摊时间复杂度
这四种复杂度的定义如下：
为什么会有这四种复杂度呢？原因是：
同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面、更准确描述代码的时间复杂度，引入这四种复杂度的概念；
但通常除非代码是出现量级差别的时间复杂度，才需要区分这四种复杂度，大多数情况都不需要区分它们。
下面是给出第一个代码例子：
# 在数组 arr 中查找目标数值 x
def find(arr, x):
for val in arr:
if val == x:
return True
return False
这个例子假设数组 arr 的长度是 n ，那么它最好的情况，就是第一个数值就是需要查找的 x ，此时复杂度是 O(1) ，但最坏情况就是最后一个数值或者不存在需要查找的 x ，那么此时就遍历一遍数组，复杂度就是 O(n) ，因此这段代码最好和最坏情况是会出现量级差别的，O(1) 和 O(n) 分别是最好情况复杂度和最坏情况复杂度。
而这段代码的平均情况时间复杂度是 O(n) ，具体分析就是首先考虑所有可能的情况以及对应出现的概率，可能发生的情况先分为两种，存在和不存在需要查找的数值 x ，也就是分别是 1/2 的概率，然后对于存在的情况下，又有 n 种情况，即出现在数组任意位置的概率都是均等的，那么它们的概率乘以存在的概率就是 1/2n ，接着再考虑每种情况需要搜索的元素个数，其实就是代码执行的次数，这个分别就是从 1 到 n，并且对于不存在的情况，也是 n ，需要遍历一遍数组才发现不存在，所以平均时间复杂度的计算过程如下：
计算得到的就是概率论中的加权平均值，也叫期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。
这里用大 O 表示法表示，并且去掉常量和系数后，就是 O(n)。
最后介绍下均摊时间复杂度，需要满足以下两个条件才使用：
1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；
2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
空间复杂度分析
和时间复杂度的定义类似，空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。
简单介绍下一个程序所需要的空间主要由以下几个部分构成：
参考：