算法时空复杂度分析：大O表示法
算法时空复杂度分析：大O表示法
算法时空复杂度分析是理解算法效率的基础，其中大O表示法是描述算法复杂度的常用方法。本文将从基本概念出发，通过具体示例，详细介绍大O表示法、时间复杂度分析原则以及常见的时间复杂度量级，帮助读者掌握算法复杂度分析的基本方法。
前言
在算法开发和面试中，算法的时空复杂度是一个重要的考量指标。虽然在日常编码过程中，我们可能更多关注代码的正确性和功能实现，但在设计高效算法时，了解和分析算法的复杂度是非常必要的。这是因为：
- 测试结果依赖测试环境：机器的配置会严重影响测试结果；
- 测试结果依赖数据规模的大小。
因此，我们需要一个不依赖数据规模和测试环境，帮助粗略估计算法执行效率的方法，这就是大O表示法。
大O表示法
让我们通过几个例子来理解大O表示法：
def f(n: int):
a = 0 # 1个unit time
for i in range(n): # n个unit time
a += i # n个unit time
return a
这个函数的总的执行时间 T(n) = 1 + 2n 个unit time。
再看一个更复杂的例子：
def g(n: int, m: int):
a = 0 # 1个unit time
for i in range(n): # n个unit time
for j in range(n): # n^2个unit time
a += i*j # n^2个unit time
return a
这个函数的总的执行时间 T(n) = 1 + n + 2n^2 个unit time。
用一个公式表示就是：
T(n) = O(f(n))
其中：
- T(n) 表示代码执行的时间；
- n 表示数据规模的大小；
- f(n) 表示每行代码执行的次数总和；
- O 表示执行时间T(n)与f(n)成正比。
当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，只需要记录一个最大量级即可！因此，上例的时间复杂度可以记为：T(n) = O(n)、T(n) = O(n^2)。
3个时间复杂度分析原则
- 只关注循环执行次数最多的一段代码：
还是上面第一个例子，关注for循环这段代码就行了，a = 0这类代码都是常量级的执行时间，与n无关。
def f(n: int):
a = 0 # 1个unit time
for i in range(n): # n个unit time
a += i # n个unit time
return a
- 总复杂度 = 量级最大的那段代码的复杂度：
这个有点像运筹学里关键路径法的思想，只有找到了最关键/量级最大的，你去优化的时候才能发力在刀刃上～
比如下面这段代码，有一层for循环的，有两层for循环，我们去关注两层for循环的这段代码即可。
def g(n: int, m: int):
for i in range(n):
pass
a = 0 # 1个unit time
for i in range(n): # n个unit time
for j in range(n): # n^2个unit time
a += i*j # n^2个unit time
return a
- 嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积：
上面的第二个例子，两层for循环嵌套，最后的时间复杂度 = 外层for循环的复杂度乘以里面for循环的复杂度。
def g(n: int, m: int):
a = 0 # 1个unit time
for i in range(n): # n个unit time
for j in range(n): # n^2个unit time
a += i*j # n^2个unit time
return a
常见的时间复杂度量级
时间复杂度可以分为多项式量级和非多项式量级两大类：
- 多项式量级：下图左侧；
- 非多项式量级：下图右侧波浪线。执行时间会随着数据规模的增大而急剧增大，是非常低效的算法！
空间复杂度
空间复杂度又称为渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系！
举个栗子🌰，空间复杂度为O(n)
def f(n: int):
a = 2 # 1个空间存储变量，常量
b = [] # 从下面代码可以看出时一个大小为n的数组
for i in range(n):
b.append(i)
return b