是什么

衡量算法优劣维度

1. 时间维度： 执行当前算法消耗的时间
2. 空间维度： 执行当前算法占用的内存空间

通常时间和空间不能兼顾， 需取得平衡点

时间复杂度

1. 理解： 执行次数越多， 花费的时间就越多
2. 定义： T(n)= O(fn(n))

• O(1)
• O(log n)
• O(n)
• O(nlog n)
• O(n^2)
• O(n^3)
• O(n^k)
• O(2^n)

3. 效率 Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)

• O(n)

function process(n) {
  let a = 1
  let b = 2
  let sum = a + b
  for(let i = 0; i < n; i++) {
    sum += i
  }
  return sum
}

• O(n ^ 2)

function process(n) {
 let count = 0
  for(let i = 0; i < n; i++){
    for(let i = 0; i < n; i++){
      count += 1
    }
  }
}

• O(log n)

function process(n) {
  let i = 1; // ①
  while (i <= n) {
     i = i * 2; // ②
  }
}

循环语句中以2的倍数来逼近n，每次都乘以2。如果用公式表示就是1 * 2 * 2 * 2 … * 2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn

嵌套循环取最大

function process(n) {
  let sum = 0
  for(let i = 0; i < n; i++) {
    sum += i
  }
  for(let i = 0; i < n; i++){
    for(let i = 0; i < n; i++){
      sum += 1
    }
  }
  return sum

O(n) < O(n^2)， 那么复杂度为O(n^2)

空间复杂度

1. 理解：执行算法占用的内存大小

• O(1)

let a = 1
let b = 2
let c = 3

• O(n)

let arr []
for(i=1; i<=n; ++i){
  arr.push(i)
}

举例

• 栈、递归空间复杂度为O(1)
• 一维数组 O(n)
• 二维数组 O(n^2)