时间空间复杂度详解

什么是复杂度

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

复杂度有如下几种

• O(1) 可数的数量级
• O(logn) 随着计算量越大 时间越平缓
• O(n) 输入两怎加 复杂度也增加
• O(nlogn) 随着输入量增大，复杂度明显增大 也就是 第二种乘以第三种
• O(n^2) 输入量增大， 复杂度指数级增长

时间复杂度

下面是几种复杂度的对应的代码帮助理解

O(1)

function fn (obj={}, key) {
  return onj[key]
}

O(n)

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

O(n^2)

function fn (list = []) {
  for (let i=0; i<list.length;i++) {
    for (let j=0; j<list.length;j++) {
      console.log(list[j])
    }
  }
}

O(logn)

二分

O(nlogn)

一次循环 嵌套一个二分

空间复杂度

常用的是三个 没有 log

O(1)

function fn (arr=[]) {
  let a = arr[1]
  let b = arr[2]
}

O(n)

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

2周刷完100道前端优质面试真题 更多视频及资料领取请关注公众号：奋斗的刚子
欢迎体验我的小程序