空间复杂度

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

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

空间负责度用大 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$

用坐标系表示为

由于三方工具的bug，导致曲线无法正常显示，不过移入鼠标之后可以显示坐标点，通过移动鼠标可以查看坐标点的变化趋势

对数空间复杂度

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

对数空间复杂度表示为 $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)$ 常见于分治算法，例如二分查找，快速排序等

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