image.png
非常糟糕的复杂度 : O(n!) 、O(2^n) 、O(n^2)
比较糟糕的 ：O(nlog n)
可以接受的 ：O(n)
还不错的：O(n)
非常好的：O(logn) 、O(1)
如何计算时间复杂度
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O(1)
时间复杂度只关注最高数量级，且与之系数也没有关系。
语句频度T(n) = 2 + 2*n + 1，那么时间复杂度为O(2*n + 3) = O(n)
def fun(n):
count1 = 0
count2 = 0
for i in range(n):
count1 += 1
count2 += 2
return count
- 对于「多个循环」，假设循环体的时间复杂度为O(n) 以下例子是 O(nn1) = O(n^2)
def fun(n):
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
- 顺序执行的语句第1部分复杂度为O(n2)，第2部分复杂度为O(n)，总复杂度为max(O(n2), O(n)) = O(n^2)
def fun(n):
# 第1部分复杂度为O(n^2)
count = 0
for i in range(n):
for j in range(n):
count += 1
# 第2部分复杂度为O(n)
for i in range(n):
count += 2
return count
- 对于「条件判断语句」，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。当n >= 0分支的复杂度最大，即总复杂度为O(n^2)
def fun(n):
if n >= 0:
# 第1部分复杂度为O(n^2)
count = 0
for i in range(n):
for j in range(n):
count += 1
else:
# 第2部分复杂度为O(n)
for i in range(n):
count += 2
return count
「总结：时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，就要深入函数进行分析。」
image.png
image.png
image.png
image.png
image.png
