概论
- 时间复杂度
- 空间复杂度
时间复杂度
- 规模：数据的大小对算法至关重要，不同量级有不同的速度，比如水 vs 水杯: 水
- 测试环境：环境的快慢对算法至关重要，在不同测试环境，速度也不同，比如手机 vs 电脑: 电脑
大O表示法
def tmp(n):
add = 0 # 运行 1unit 次
for i in range(n): # 运行 nunit 次
add += i # 运行 nunit 次
return add
- 假设每行代码的运行时间为
1unit - 总共运行：
-
，
表示
与
成正比
-
- 表示代码执行时间数据规模增长的变化趋势
当 n 很大时，低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，就可以记为：
；
只关注循环次数多的代码
def tmp(n):
add = 0
for i in range(n):
add += i
return add
-
，将规模变为无穷大，就不必关注循环次数少或没有循环的代码
选大量级
def tmp(n):
for i in range(999):
print(123)
for i in range(n):
print(123)
for i in range(n):
for j in range(n):
print(2)
-
，最后一个循环为
n的2次方
嵌套循环要乘积
def tmp(n):
for i in range(n):
a(i)
def a(n):
for i in range(n):
print('C')
-
n的2次方
常见复杂度分析
- 非多项式量级（过于低效）：
和
- 多项式量级：
,
,
,
- 不是说只有一行代码
- 是指代码的执行时间不随着规模增加
a=2
b=3
c=4
def tmp(n):
i = 1
while i < n:
i = i * 2
- 退出循环的条件是：
，即
，时间复杂度为
def tmp(n):
i = 1
while i < n:
i = i * 3
-
就等于
，所以
，其中
是一个常量。 基于我们前面的一个理论：在采用大
O标记复杂度的时候，可以忽略系数，即。所以，
就等于
。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为
)
、)
def tmp(m, n):
for i in range(m):
print(1)
for i in range(n):
print(2)
空间复杂度
- 空间复杂度是 存储空间与数据规模之间的增长关系
- 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下， 空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。
渐进时间复杂度：表示算法的 执行时间 与数据规模之间的增长关系。
渐进空间复杂度：表示算法的 存储空间 与数据规模之间的增长关系。
def tmp(n):
a = [1]*n
for i in a:
print(i)
- 空间复杂度是：
