概论
- 时间复杂度
- 空间复杂度
时间复杂度
- 规模: 不同量级有不同的速度，比如水 vs 水杯: 水
- 测试环境: 在不同测试环境，速度也不同，比如手机 vs 电脑: 电脑
大 O 表示法
def tmp(n):
add = 0
for i in range(n):
add += i
return add
运行时间：T(n) = (2n + 1) * unit
T(n) = O(f(n)) , O表示 T(n) 与 f(n) 成正比
O 表示渐近时间复杂度
表示代码执行时间随数据规模增长的变化趋势
当 n 很大时,低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略．就可以记为：T(n) = O(n)； T(n) = O(n2)。
只关注循环次数多的代码
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(n2)
嵌套循环要乘积
def tmp(n):
for i in range(n):
a(i)
def a(n):
for i in range(n):
print('c')
O(n2)
常见复杂度分析
-
非多项式量级（过于低效） : O(2n) 和 O(n!)。
-
多项式量级:O(1), O(logn), O(n), O(nlogn), O(nk)
O(1)
a=2
b=3
d=4
O(logn)
def tmp(n):
i = 1
while i < n :
i = i * 2
i = 20,21, 22, 23…2x
退出循环的条件是 : 2x = n ,即 x = log2n，时间复杂度为 Ｏ(log2n)
def tmp(n):
i = 1
while i < n :
i = i * 3
log3n 就等于 log32 * log3n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)
O(m+n)、O(m*n)
def tmp(m, n):
for i in range(m):
print(1)
for i in range(n):
print(2)
空间复杂度
- 渐进时间复杂度：表示算法的执行时间与数据规模之间的增长关系。
- 渐进空间复杂度：表示算法的存储空间与数据规模之间的增长关系。
def tmp(n):
a = [1]*n
for i in a:
print(i)
空间复杂度是： O(n)