什么是空间复杂度

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

O(1)

  1. // 单个变量
  2. let i = 0

O(n)

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

O(n^2)

  1. // 二维数组，存放了n^2的变量
  2. const matrix = []
  3. for(let i =0; i< n; i+=1) {
  4.     matrix.push([])
  5.     for(let j =0; j< n; j+=1) {
  6.         matrix[i].push(j)
  7.     }
  8. }