Big O Notation & Time Complexity
同樣的問題可以用許多種不同的方式加以解決，因此，我們需要一些指標來評量各種方式的好壞。在演算法中，常會使用 Big O Notation 和 Time Complextiy 來衡量一個演算法（函式）的好壞。通常，會根據這個函式隨著輸入的資料量增加時，執行時間會拉長多少來作為衡量的標準之一，下面會說明其中四種類型：
補充：
Big O Notation 代表演算法時間函式的上限（Upper bound），表示在最壞的狀況下，演算法的執行時間不會超過Big-Ο。
—
[資料結構]演算法評估與資料型別
Constant Run Time (O(1))
第一個類型是屬於 constant run time（O(1)），這個演算法（函式）的執行時間不會隨著輸入資料量的增加而增加。
以下面的函式為例，不論我們代入的資料量有多大，它都只是輸出陣列中第一和第二個元素的值，因此執行時間不會隨著輸入資料量的增加而增加。
let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7,8,9,10]
function log (arr) {
console.log(arr[0])
console.log(arr[1])
}
log(arr1)
log(arr2)
Linear Run Time (O(n))
下面的函式，當我們輸入的資料越多的時候，它就會需要等比例輸出越多的內容給我們，因此會需要消耗等比例越多的時間：
function logAll(arr) {
for (let item of arr) {
console.log(item)
}
}
logAll(arr1)
logAll(arr2)
Exponential Run Time (O(n^2))
隨著資料量的增加，執行時間會以指數成長。以下面的函式為例，當我們輸入的陣列包含 5 個元素的時候，它會輸出 25 (5^2) 筆資料；但是當我們數入的陣列包含 10 個元素的時候，它則會輸出 100 (10^2) 筆資料：
function addAndLog (arr) {
for (let item of arr) {
for (let item2 of arr) {
console.log ('First', item + item2)
}
}
}
addAndLog(arr1)
addAndLog(arr2)
Logarithmic Run Time (O(log n))
隨著資料量增加，執行時間雖然會增加，但增加率會趨緩。下面的程式碼類似 findIndex 的函式，當輸入的資料有 5 個元素時，它會先切對半後，再尋找，再切半再尋找，因此雖然隨著資料量增加，執行的時間會增加，但是當資料量越大時，執行速度增加的情況越不明顯：
function binarySearch (arr, key) {
let low = 0
let high = arr.length - 1
let mid
let element
while (low <= high) {
mid = Math.floor((low + high) / 2, 10)
element = arr[mid]
if (element < key) {
low = mid + 1
} else if (element > key) {
high = mid - 1
} else {
return mid
}
}
return -1
}
console.log(binarySearch(arr1, 3))
console.log(binarySearch(arr2, 3))
圖示
把上面這四種類型用圖線表示，縱軸是時間、橫軸是輸入資料量的多少，可以用來判斷這四種類型的演算法（函式）的好壞：
完整程式碼
/**
* Demo Big O Notation
**/
let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7,8,9,10]
/**
* Constant Run Time：不會隨著輸入的資料量越大而使得執行時間變長
* Big O Notation: "O(1)"
**/
function log (arr) {
console.log(arr[0])
console.log(arr[1])
}
log(arr1) // 1, 2
log(arr2) // 1, 2
/**
* Linear Run Time: 隨著資料量的增加，執行時間會等比增加
* Big O Notation: "O(n)"
**/
function logAll (arr) {
for (let item of arr) {
console.log(item)
}
}
logAll(arr1) // 1, 2, 3, 4, 5
logAll(arr2) // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/**
* Exponential Run Time: 隨著資料量的增加，執行時間會誇張的增加
* Big O Notation: "O(n^2)"
**/
function addAndLog (arr) {
for (let item of arr) {
for (let item2 of arr) {
console.log (item + item2)
}
}
}
addAndLog(arr1) // 25 pairs logged out
addAndLog(arr2) // 100 pairs logged out
/**
* Logarithmic Run Time: 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
* Big O Notation: "O (log n)"
**/
function binarySearch (arr, key) {
let low = 0
let high = arr.length - 1
let mid
let element
while (low <= high) {
mid = Math.floor((low + high) / 2, 10)
element = arr[mid]
console.log('ele', mid, element)
if (element < key) {
low = mid + 1
} else if (element > key) {
high = mid - 1
} else {
return mid
}
}
return -1
}
console.log(binarySearch(arr1, 1))
console.log(binarySearch(arr2, 1))
資料來源
