是什么？

• 一个函数，用大O表示，比如 O(1)、O(n)、O(n^2)...
• 算法在运行过程中临时占用存储空间大小的量度

案例

1. 常量空间
   O(1)

let i = 0;
i += 1;

原因：只声明了单个变量，单个变量所占用的内存永远是1

2. 线性空间
   当算法分配的空间是一个线性的集合（如数组），并且集合大小 和输入规模n成正比时，空间复杂度记作O(n)。
   O(n)

const list = []
for (let i = 0; i < n; i++) {
  list.push(i)
}

原因：我们声明了一个数组，给这个数组里 push 了 n 个 i，所以就占了 n 个

3. 二维空间
   当算法分配的空间是一个二维数组集合，并且集合的长度和宽度 都与输入规模n成正比时，空间复杂度记作O(n^2)。
   O(n^2)

const matrix = [];
for (let i = 0; i < n; i++) {
  matrix.push([]);
  for (let j = 0; j < n; j++) {
    matrix[i].push(j)
  }
}

matrix 里 push 了 n 个，每一个里又 push 了 n 个，所以就是 n^2

4. 递归空间
   O(n)

function fun4(n) {
  if (n <= 1) {
    return;
  }
  fun4(n-1);
  ...
}
fun4(5)

执行递归操作所需 要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也 是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。