算法复杂度

时间复杂度

用来定义描述算法的运行时间

// O(1)
let i = 0
i += 1

// O(n)：一层循环，如果是 O(1) + O(n) 则还是 O(n)
for(let i=0; i<n; i++) {
    console.log(i)
}

// O(n^2)： 等于O(n*n)，也就是双层循环，自此类推：O(n^3)...
// 如果第二层循环换成j<m,那就是O(n*m)
for(let i=0; i<n; i++) {
    for(let j=0; j<n; j++) {
        console.log(i, j)
    }
}

// 线性对数阶O(nlogN)：将时间复杂度为O(logn)的代码循环N遍的话，
// 那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
// O(logn)
let i = 1;
while(i<n) {
    i = i * 2;
}
//  n * O(logN)，也就是了O(nlogN)
for(let i=0; i<n; i++) {
    i = 1;
    while(i<n) {
        i = i * 2;
    }
}

空间复杂度

用来定义描述算法运行过程中临时占用的存储空间大小，占用越少，代码写得越好。

// O(1)：单个变量，所以占用永远是 O(1)
let i = 0
i += 1

// O(n)：声明一个数组， 添加 n 个值， 相当于占用了 n 个空间单元
const arr = []
for (let i = 0; i < n; i += 1) {
    arr.push(i)
}

// O(n^2)：类似一个矩阵的概念，就是二维数组的意思
const arr = []
for (let i = 0; i < n; i += 1) {
  arr.push([])
  for (let j = 0; j < n; j += 1) {
    arr[i].push(j)
  }
}