1. 概论
- 时间复杂度
- 空间复杂度
2. 时间复杂度
渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系
- 规模：水 ↔ 水杯：水
- 测试环境：手机 ↔ 电脑：手机
2.1 大O表示法
def tmp(n):
add = 0
for i in range(n):
add += i
return add
上述代码的时间复杂度T(n) = （2n + 1）* unit
- 运行每一行都是1unit
- T(n) = O(f(n))
- O表示T(n) 与 f(n) 成正比
- O表示渐近时间复杂度，表示代码执行时间随数据规模增长的变化趋势
- 在采用大O标记复杂度的时候，可以忽略系数、常量
只关注循环次数多的代码
def tmp(n):
add = 0
for i in range(n):
add += i
return add
O(n)
选大量级
def tmp(n):
for i in range(999):
print(123)
for i in range(n):
print(1)
for i in range(n):
for j in range(n):
print(2)
$O(n^2)$
嵌套循环要乘积
def tmp(n):
for i in range(n):
a(n)
def a(n):
for i in range(n):
pring(1)
$O(n^2)$
3. 空间复杂度
渐进空间复杂度是，存储空间与数据规模之间的增长关系
def tmp(n):
a = [1]*n
for i in a:
print(i)
第二行是O(n)