一.简介
1.1 何为“复杂度”
复杂度:指为了执行目标程序,所需要的计算资源与“问题规模”之间的函数关系。
- 时间复杂度:是指执行当前算法所消耗的时间
- 空间复杂度:是指执行当前算法需要占用多少内存空间
1.2 问题规模
"问题规模" 是需要根据具体问题来定义的, 通常会用若干个自然数来定义,当然也是根据具体场景和分析侧重来定义的。因此,定义 "问题规模" 本身就是分析过程中的一个很重要的步骤。
1.3 大O符号含义
用大O记法表示的复杂度,叫做渐近复杂度(asymptotic complexity),通常大家说的"分析算法复杂度"指的就是渐近复杂度分析。
引用知乎的一段话:
大O符号是一种算法「复杂度」的「相对」「表示」方式。
- 相对(relative):你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是,比较2个算法所做的算术操作(一个做乘法,一个做加法)将会告诉你一些有意义的东西;
- 表示(representation):大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。
二.类型
常见复杂度表示:
- O(1): Constant Complexity: Constant 常数复杂度
- O(log(n)): Logarithmic Complexity: 对数复杂度
- O(n): Linear Complexity: 线性时间复杂度
- O(n^2): N square Complexity 平⽅
- O(n^3): N square Complexity ⽴⽅
- O(2^n): Exponential Growth 指数
- O(n!): Factorial 阶乘
2.1 O(1)
# 程序只执行一次
print("hello world")
2.2 O(n)
# 程序线性增长执行
n = 10
for i in range(n):
print("hello world")
2.3 O(n^2)
# 程序嵌套循环,执行n^2次
n = 10
for i in range(n):
for j in range(n):
print("hello world")
2.4 O(log(n))
# 程序步长为2(或者更大),反推其执行次数为log(n)
n = 10
for i in range(0, n, 2):
print("hello world",i)
2.5 O(k^n)
# pow(n,k)为最终执行的次数,以下为举例
n = 10
k = 3
for i in range(pow(n, k)):
print("hello world", i)
2.6 O(n!)
# factorial(n)为最终执行的次数,以下为举例
import math
n = 5
for i in range(math.factorial(n)):
print("hello world", i)
三.小结
以上例子证明了:“print”函数执行多少次,该算法的时间复杂度即为O(x)多少。
借用极客时间的一张图,如下:
评论区