空间复杂度

空间复杂度与时间复杂度非常相似.

空间复杂度是评估算法占用内存空间变化趋势的一种表达方式. 它表达的是一种增长曲线趋势, 而不具体的内存空间大小.

空间负责度用大 O 表示法来表示, 他具体的公式是

$S(n) = O(f(n))$

$f(n)$ 是数学公式中对于函数的一种表达, 我们也可以用代码来平替一下简化理解

1
// 针对线性时间复杂度
2
function f1(n) { 
3
  return n
4
}
5

6
// 针对平方时间复杂度
7
function f2(n) { 
8
  return n * n
9
}

函数 f1 等价于 $O(n)$

函数 f2 等价于 $O(n^2)$

线性空间复杂度

线性空间复杂度常见于数组, 链表, 栈, 队列等线性数据结构.

线性空间复杂度表示为 $O(n)$, 对应的数学公式就是

$y = x$

在坐标系中我们可以用一条直线来表示, 这条直线表示的是输入和输出的关系. x 轴表示输入, y 轴表示输出.

平方空间复杂度

平方空间复杂度常见于二维数组, 矩阵, 图等二维数据结构.

平方空间复杂度表示为 $O(n^2)$, 对应的数学公式就是

$y = x^2$

在坐标系中我们可以用一个抛物线来表示, 这条抛物线表示的是输入和输出之间的关系. x 轴表示输入, y 轴表示输出.

指数空间复杂度

指数空间复杂度常见于递归, 斐波那契数列等.

指数空间复杂度表示为 $O(2^n)$, 对应的数学公式就是

$y = 2^x$

用坐标系表示为

对数空间复杂度

对数空间复杂度常见于分治算法, 例如二分查找, 快速排序等.

对数空间复杂度表示为 $O(log_2 n)$, 或者简化为 $O(log n)$, 对应的数学公式就是

$y = log_2 x$

用坐标系表示为

总结

• 常量空间复杂度：$O(1)$ 常见于常量, 变量, 对象等, 比较简单不单独介绍
• 线性空间复杂度：$O(n)$ 常见于数组, 链表, 栈, 队列等线性数据结构
• 平方空间复杂度：$O(n^2)$ 常见于二维数组, 矩阵, 图等二维数据结构
• 指数空间复杂度：$O(2^n)$ 常见于二叉树, 多叉树等
• 对数空间复杂度：$O(log_2 n)$ 常见于分治算法, 例如二分查找, 快速排序等

通常情况下, 在真实的实践过程中, 在选择算法时, 我们可能会更专注于时间效率, 或者更多的去利用空间来换取时间. 因此只要空间的消耗不是特别大, 我们通常会优先选择时间复杂度更低的算法.