什么是大O符号？

Big O表示法在计算机科学中用于描述算法的时间复杂度。最好的算法将以最快的速度执行，并且具有最简单的复杂度。

算法并不总是执行相同的操作，并且可能会根据所提供的数据而有所不同。尽管在某些情况下它们将快速执行，但在另一些情况下，即使要处理的元素数量相同，它们也将执行缓慢。

在这些示例中，基准时间为1元素=  1ms。

O(1)

arr[arr.length - 1]

• 1000个元素= 1ms

恒定的时间复杂度。无论数组有多少个元素，理论上执行（不包括实际变化）所花费的时间都是相同的。

O(N)

arr.filter(fn)

• 1000个元素= 1000ms

线性时间复杂度。执行时间将随着数组中元素的数量线性增加。如果数组有1000个元素，并且该函数需要1ms的执行时间，则7000个元素将需要7ms的执行时间。这是因为函数必须在返回结果之前遍历数组的所有元素。

O(1,N)

arr.some(fn)

• 1000个元素= 1ms <= x <= 1000ms

执行时间取决于提供给函数的数据，它可能返回得很早或很晚。最好的情况是O(1)，最坏的情况是O(N)。

O(NlogN)

arr.sort(fn)

• 1000个元素〜= 10000ms

浏览器通常为该sort() 方法实现快速排序算法，快速排序 的平均时间复杂度为O(NlgN)。这对于大型馆藏非常有效。

O（N ^ 2）

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    // ...
  }
}

• 1000个元素= 1000000ms

执行时间随着元素数量的增加而平方增加。通常是嵌套循环的结果。

在！）

const permutations = arr => {
  if (arr.length <= 2) returnarr.length=== 2 ? [arr, [arr[1], arr[0]]] : arr
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [
          item,
          ...val
        ])
      ),
    []
  )
}

• 1000个元素=  Infinity （实际上）ms

即使仅向阵列添加1，执行时间也会非常快地增加。

额外信息

• 警惕嵌套循环，因为执行时间呈指数增长。

其他连结

• JavaScript中的大O表示法