时间复杂度

是什么

衡量算法执行效率的指标

就是看看你写的代码运行速度有多快

大 O 表示法

全称是 “Big O Notation”

其中 “O” 源于德语单词”Ordnung”(意为”顺序”或”级别”)的首字母

用于表示时间复杂度

比如 O(n)、O(n^2)、O(logn) 等

怎么算

O(1) - 常数时间复杂度

function getFirst(arr) {
  return arr[0]
}

无论输入数据多大，执行时间都是固定的

O(n) - 线性时间复杂度

function findMax(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    // 循环n次
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

执行时间与输入数据大小成正比

O(n^2) - 平方时间复杂度

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 外层循环n次
    for (let j = 0; j < arr.length - 1; j++) {
      // 内层循环n次
      if (arr[j] > arr[j + 1]) {
        // 交换元素
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

执行时间与输入数据大小的平方成正比

注意

描述的是最坏情况下算法的执行时间