算法复杂度分析¶
既然算法就是解决问题的方法，那么解决同一个问题也就可能会有多种不同的方法，如何评判哪个方法更好，这就需要一个衡量标准。即算法复杂度分析，来找到最优的解决方案。
数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，算法复杂度分析就是分析算法的执行效率以及资源消耗。
- 快：执行效率，即时间复杂度
- 省：资源消耗，即空间复杂度
动态分析法¶
测试结果非常依赖测试环境，比如不同的处理器。另外测试结果受数据规模影响也很大。比如排序算法，如果给一个本身就有序的数据排序，算法可能不需要做任何操作，执行时间会非常短，基本无法判断哪个好哪个坏。
time
import time
start_time = time.time() # 开始时间
pass # 待测算法
end_time = time.time() # 结束时间
print(end_time - start_time) # 耗时
timeit
timeit.timeit(stmt, setup,timer, number)
"""
stmt: statement的缩写，要测试的代码或者语句，默认值是"pass"
setup: 在运行stmt前的配置语句，默认值"pass"
timer: 计时器，一般忽略这个参数
number: stmt执行的次数，默认是100万次
"""
# 由于stmt只能是语句，需要借助匿名函数来测试函数
t = timeit.timeit(lambda :range(10), number=500)
print(t)
静态分析法(大O)¶
大O复杂度表示法：
O(f(n))
- 每行代码执行时间：
t - 数据规模：
n - 代码总执行次数：
f(n) - 代码总执行时间：
T(n)=f(n)*t
释义：在不运行代码的情况下，假设t相同，n不断增长，忽略常量系数、低阶、底阶等对增长趋势关系不大的部分，复杂度约等于T(n)，与f(n)成正比
分析法则¶
假设每行代码执行的时间都一样，为 unit_time，简写为：t
- 找循环次数最多的代码段
def test():
sum = 0 # t
i = 1 # t
while i <= n: # nt
sum = sum + i # nt
i = i + 1 # nt
return sum
# T(n) = (2+3n)t
# 复杂度：O(n)
- 找嵌套最多，量级最大的那一段代码
def test():
sum = 0 # t
i = 1 # t
while i <= n: # nt
j = 1 # nt
while j <= n: # n^2t
sum = sum + i * j # n^2t
j = j + 1 # n^2t
return sum
# T(n) = (2+2n+3n^2)t
# 复杂度：O(n^2)
- 若最大有多段则相加，有嵌套则相乘
def f1(n):
ret = 0
i = 1
while i < n:
ret = ret + f2(i) # 这里调用了另一个函数f2
n = n + 1
def f2(n):
sum = 0
i = 1
while i < n:
sum = sum + i
return sum
# T(n) = T1(n) * T2(n)
# 复杂度为：O(n^2)
常见大O复杂度¶
空间复杂度分析¶
空间复杂度：表示的是代码存储空间随数据规模增长的变化趋势
相对时间复杂度，空间复杂度比较简单，只需掌握最常见的三种即可
时间复杂度分析¶
时间复杂度，表示的是代码执行效率随数据规模增长的变化趋势
- 常量级
一般情况下，只要算法中不存在循环或递归语句，无论有多少行代码，都属于常量级，都用O(1)表示
i = 8
j = 6
sum = i + j
- 对数级
很常见，但通常较难分析
i=1
while i <= n:
i = i * 2
# 退出循环的条件为2^x=n，即要循环x=log2_n次
# 忽略底数之后，复杂度为：O(logn)
上面这段代码循环多少次（x），取决于i，每循环一次i的值要乘2，当循环2^x次后大于n则停止，即x为logn，最终复杂度表示为：O(logn)
如果每循环一次i的值要乘3、乘10等等，忽略底阶后复杂度仍然表示为：O(logn)
如果循环了n次，那就是：O(nlogn)
特殊情况¶
# 示例1
# 在一个长度不固定的无序列表中，查找元素x所在的位置
# 找到则停止查找，遍历完后没找到则返回-1
def find(_list, x):
pos = -1
for i in len(_list):
if _list[i] == x:
pos = i
break
return pos
在示例1中，要查找的元素x，可能会出现在列表的任意位置，亦或者不在列表中，共有n+1种情况，于是复杂度需要根据不同情况进行分析：
- 如果x位于首位则时间复杂度为O(1)，称之为
最好情况时间复杂度 - 如果x位于末位，则时间复杂度为O(n)，称之为
最坏情况时间复杂度 - 但大多数情况下元素都不位于首位或末位，于是我们需要引出
平均情况时间复杂度
假设元素x在列表中和不在列表中的概率各自为1/2，如果在列表中，则每个位置的概率相等，均为1/2 * 1/n，即1/2n
总遍历次数，即加权平均值为：(1+2+3+...+n)/2n + n*1/2，前n项和为：n(1+n)/2，最后：T(n)=(3n+1)/4，忽略系数等，最终的平均情况时间复杂度为：O(n)
# 示例2
# 向一个长度为n的列表中插入新数据value，如果列表有剩余空间，则直接插入
# 如果列表没有剩余空间，则先计算其元素总和sum，然后清空列表后将sum插入到列表的首位，再继续插入value
_list = [1,2,3...n]
count = 0
def insert(value):
if count == len(_list):
sum = 0
for i in len(_list):
sum = sum + _list[i]
_list.insert(0, sum)
count = 1
_list.insert(count, value)
count = count + 1
在示例2中，根据不同情况分析：
- 理想的情况下，列表有剩余空间，直接插入即可，即最好情况时间复杂度为O(1)
- 最坏的情况下，没有剩余空间，需要遍历一次列表求和，所以最坏情况时间复杂度为O(n)
- 平均情况呢？此处与示例1有所不同
对于示例2来说，列表要么有剩余，要么没有剩余，只有这两种情况，而且有剩余空间的概率远大于没有剩余空间的情况，我们没必要再计算其加权平均值，也就是说绝大多数情况都属于理想的情况，复杂度都是O(1)，我们称之为均摊时间复杂度，算是平均情况时间复杂度的一种特殊情况。