大 O 符號（Big O Notation）掏颊，又稱為漸進符號，用于描述算法的時間復雜度。最好的算法將執(zhí)行得最快并且具有最簡單的復雜性肩杈。
算法并不總是執(zhí)行相同的操作，并且可能會根據(jù)提供的數(shù)據(jù)而有所不同。雖然在某些情況下它們會執(zhí)行非常快扛禽，但在其他情況下它們會執(zhí)行緩慢，即使要處理相同數(shù)量的元素皱坛。
在以下示例中编曼，基準時間為 1 個元素 = 1ms。
O(1) — 恒定時間復雜性
arr[arr.length - 1]
1000 個元素 = 1ms
無論數(shù)組有多少個元素剩辟，理論上執(zhí)行所需的時間（不包括實際的變化）都是相同的灵巧。
O(N) — 線性時間復雜度
arr.filter(fn)
1000 個元素 = 1000ms
執(zhí)行時間將隨著數(shù)組元素的數(shù)量線性增加。如果數(shù)組有 1000 個元素抹沪，并且函數(shù)需要 1ms 才能執(zhí)行，那么 7000 個元素將需要 7ms 執(zhí)行瓤球。這是因為函數(shù)必須在返回結(jié)果之前遍歷數(shù)組的所有元素融欧。
O([1, N]) — 恒定/線性時間復雜度
arr.some(fn)
1000 個元素 =1ms <= x <= 1000ms
執(zhí)行時間取決于提供給函數(shù)的數(shù)據(jù)，它可能會很早或很晚返回卦羡。這里最好的情況是 O(1)噪馏，最壞的情況是 O(N)麦到。
O(NlogN) — 線性時間復雜度
arr.sort(fn)
1000 個元素 ~= 10000ms
瀏覽器通常為 sort() 方法實現(xiàn)快速排序算法，快速排序的平均時間復雜度為 O(NlogN)欠肾。這對于大型集合非常有效瓶颠。
O(N^2) — 二次方時間復雜度
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
// ...
}
}
1000 個元素 = 1000000ms
執(zhí)行時間隨著元素的數(shù)量呈二次曲線增長。通常是嵌套循環(huán)的結(jié)果刺桃。
O(N!) — 階乘時間復雜度
const permutations = arr => {
if (arr.length <= 2) return arr.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（實際上）
即使只在數(shù)組中添加一個粹淋，執(zhí)行時間也會增長得非常快瑟慈。
Tips：隨著執(zhí)行時間呈指數(shù)增長桃移，需要注意嵌套循環(huán)。
更多資料
- Big O Notation: A primer for beginning devs
- A beginner's guide to Big O Notation
- A Simplified Explanation of the Big O Notation
- All you need to know about “Big O Notation” to crack your next coding interview
- A story of Big O
- Big-O Cheat Sheet
- The Big 'O' Notation - An Introduction Sarah Chima - Front-End Developer
