聊聊前端算法复杂度

算法复杂度

前端开发一般：重时间 轻空间

什么是复杂度

1. 程序执行时需要的计算量和内存空间（和代码简洁度无关）
2. 复杂度是 数量级，不是具体的 数字
3. 一般针对一个具体的算法，而非一个完整的系统

时间复杂度

程序执行时需要的计算量(cpu)

1. O(1) 一次就够
   1. "可数的", 和输入量无关，无论输入量是1还是1000，都只计算一次
2. O(n) 和传输的数据量一样
3. O(n^2) 数据量的平方
4. O(logn) 数据量的对数
5. O(n*logn) 数据量 * 数据量的对数

// O(1)
function fn(obj = {}, key) {
  return obj[key]

  return obj.a + obj.b + obj.c // 这个计算量虽然大概为4-5，但是也是数量级1，不需要去循环数据量
}

// O(n)
function fn(arr = []) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i])
  }
}

// O(n^2)
function fn(arr = []) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[j])
    }
  }
}

// O(logn)
// 二分的思想
function fn(arr = []) {
  // 每次都排除一半的数据量
}

// O(n * logn)
// 先循环，再嵌套二分
function fn(arr = []) {

}

空间复杂度

程序执行时需要的内存空间

1. O(1) 有限的、可数的空间
2. O(n) 和输入的数据量相同的空间
3. O(n^2)

// O(1)
function fn(arr = []) {
  // 没有循环，都是可数的
  const a = arr[1]
  const b = arr[2]
}

// O(n)
function fn(arr = []) {
  const arr2 = []
  for (let i = 0; i < arr.length; i++) {
    arr2[i] = arr[i]
  }
  // ...
}