Big O Notation，统称为Bachmann-Landau notation 或 asymptotic notation，是一种描述算法性能的方法。它用于描述算法的最坏情况。它用于比较不同算法的性能。它根据输入大小描述算法的实现。

大O表示法根据函数的增长率来表征函数：具有相同增长率的任务被认为具有相同的顺序。它是一种数学符号，描述了当参数趋向于特定值或无穷大时函数的限制行为。它用于根据算法的运行时间或空间需求随着输入大小的增长而增长对算法进行分类。使用字母O是因为函数的增长率也称为阶数。

迭代

For循环

for (let i = 0; i < n; i++) {  console.log(i)}

上面的代码会运行n次。这段代码的时间复杂度是O(n)。

while 循环

let i = 0while (i < n) {  console.log(i)  i++}

上面的代码会运行n次。这段代码的时间复杂度是O(n)。

做 while 循环

let i = 0do {  console.log(i)  i++} while (i < n)

上面的代码会运行n次。这段代码的时间复杂度是 O(n)。

递归

阶乘

function factorial(n) {  if (n === 0) {    return 1  }  return n * factorial(n - 1)}

上面的代码会运行n次。这段代码的时间复杂度是O(n)。

斐波那契数列

function fibonacci(n) {  if (n <= 1) {    return n  }  return fibonacci(n - 1) + fibonacci(n - 2)}

上面的代码会运行n次。这段代码的时间复杂度是O(n)。

搜索中

线性搜索

function linearSearch(arr, value) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === value) {      return i    }  }  return -1}

上面的代码会运行n次。这段代码的时间复杂度是O(n)。

二分查找

function binarySearch(arr, value) {  let start = 0  let end = arr.length - 1  let middle = Math.floor((start + end) / 2)  while (arr[middle] !== value && start <= end) {    if (value < arr[middle]) {      end = middle - 1    } else {      start = middle + 1    }    middle = Math.floor((start + end) / 2)  }  if (arr[middle] === value) {    return middle  }  return -1}

上面的代码将运行log(n) 次。这段代码的时间复杂度是O(log(n))。

排序

冒泡排序

function bubbleSort(arr) {  for (let i = arr.length; i > 0; i--) {    for (let j = 0; j < i - 1; j++) {      if (arr[j] > arr[j + 1]) {        let temp = arr[j]        arr[j] = arr[j + 1]        arr[j + 1] = temp      }    }  }  return arr}

上面的代码将运行n^2 次。这段代码的时间复杂度是O(n^2)。

选择排序

function selectionSort(arr) {  for (let i = 0; i < arr.length; i++) {    let lowest = i    for (let j = i + 1; j < arr.length; j++) {      if (arr[j] < arr[lowest]) {        lowest = j      }    }    if (i !== lowest) {      let temp = arr[i]      arr[i] = arr[lowest]      arr[lowest] = temp    }  }  return arr}

上面的代码将运行n^2次。这段代码的时间复杂度是O(n^2)。

插入排序

function insertionSort(arr) {  for (let i = 1; i < arr.length; i++) {    let currentVal = arr[i]    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {      arr[j + 1] = arr[j]    }    arr[j + 1] = currentVal  }  return arr}

上面的代码将运行n^2 次。这段代码的时间复杂度是O(n^2)。

合并排序

function mergeSort(arr) {  if (arr.length <= 1) return arr  let mid = Math.floor(arr.length / 2)  let left = mergeSort(arr.slice(0, mid))  let right = mergeSort(arr.slice(mid))  return merge(left, right)}function merge(left, right) {  let results = []  let i = 0  let j = 0  while (i < left.length && j < right.length) {    if (left[i] < right[j]) {      results.push(left[i])      i++    } else {      results.push(right[j])      j++    }  }  while (i < left.length) {    results.push(left[i])    i++  }  while (j < right.length) {    results.push(right[j])    j++  }  return results}

上面的代码将运行n log(n) 次。这段代码的时间复杂度是O(n log(n))。

快速排序

function pivot(arr, start = 0, end = arr.length + 1) {  let pivot = arr[start]  let swapIdx = start  function swap(array, i, j) {    let temp = array[i]    array[i] = array[j]    array[j] = temp  }  for (let i = start + 1; i < arr.length; i++) {    if (pivot > arr[i]) {      swapIdx++      swap(arr, swapIdx, i)    }  }  swap(arr, start, swapIdx)  return swapIdx}function quickSort(arr, left = 0, right = arr.length - 1) {  if (left < right) {    let pivotIndex = pivot(arr, left, right)    quickSort(arr, left, pivotIndex - 1)    quickSort(arr, pivotIndex + 1, right)  }  return arr}

上面的代码将运行n log(n) 次。这段代码的时间复杂度是O(n log(n))。