[演算法] Big O Notation, Time Complexity & Space Complexity
TL;DR;
好的程式碼通常是指好的「閱讀性/維護性(readable/maintainable)」和「可擴展性(scalable)」,而可擴展性又可以分成時間複雜度(速度)和空間複雜度(space complexity)。其中時間複雜度就可以使用 Big O Notation 來衡量,也就是用來衡量當資料量持續增加時,程式執行的時間增加的比率為何。
O(1)
:沒有迴圈O(log N)
:通常會是搜尋使用的演算法,會排序後先對半分O(n)
:一層迴圈O(n*log(n))
:通常是排序的操作O(n^2)
:兩層迴圈(迴圈內有迴圈)O(2^N)
:recursiveO(n!)
:每個元素都在跑一次回圈
Big O Notation & Time Complexity
同樣的問題可以用許多種不同的方式加以解決,因此,我們需要一些指標來評量各種方式的好壞。在演算法中,常會使用 Big O Notation
和 Time Complexity
來衡量一個演算法(函式)的好壞。通常,會根據這個函式隨著輸入的資料量增加時,執行時間會拉長多少來作為衡量的標準之一。
Big O Notation 代表演算法時間函式的上限(Upper bound),表示在「最壞的狀況」下,演算法的執行時間不會超過 Big-Ο。--- 演算法評估與資料型別
常見的時間複雜度(Time Complexity)
常見的時間複雜度由快到慢排列包含:
- 優良
O(1)
O(log n)
O(n)
- 可接受
O(n log n)
- 差
O(n ^ 2)
O(2 ^ n)
O*(n!)
💡 在演算法中,
log n
的慣例指的是以 2 為底的意思,也就是 2 的幾次方。
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];
/**
* 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 (O(n)
)
keywords: 一層迴圈
下面的函式,當我們輸入的資料越多的時候,它就會需要等比例輸出越多的內容給我們,因此會需要消耗等比例越多的時間:
/**
* 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 (O(n^2)
)
keywords: 迴圈內有迴圈
隨著資料量的增加,執行時間會以指數成長。以下面的函式為例,當我們輸入的陣列包含 5 個元素的時候,它會輸出 25 (5^2) 筆資料;但是當我們數入的陣列包含 10 個元素的時候,它則會輸出 100 (10^2) 筆資料:
/**
* Exponential Run Time: 隨著資料量的增加,執行時間會誇張的增長
* Big O Notation: "O(n^2)"
**/
function addAndLog(arr) {
for (let item of arr) {
for (let item2 of arr) {
console.log('First', item + item2);
}
}
}
addAndLog(arr1); // 25 pairs logged out
addAndLog(arr2); // 100 pairs logged out
Logarithmic Run Time (O(log n)
)
keywords: n / 2
隨著資料量增加,執行時間雖然會增加,但增加率會趨緩。能夠對半(n/2
)處理的通常都屬於 O(log n)
的演算法,因為假設 n 是 8,表示一共會跑 3 次,也就是 log 8 = 3
的意思。
例如,每次都找到陣列中最中間的元素並保存起來:
/**
* Logarithmic Run Time: 隨著資料量增加,執行時間雖然會增加,但增加率會趨緩
* Big O Notation: "O (log n)"
**/
function half(arr: number[]): number[] {
const elements: number[] = [];
let n = arr.length - 1;
while (n > 0) {
n = Math.floor(n / 2);
elements.push(arr[n]);
}
return elements;
}
下面的程式碼類似 findIndex
的函式,當輸入的資料有 5 個元素時,它會先切對半後,再尋找,再切半再尋找,因此雖然隨著資料量增加,執行的時間會增加,但是當資料量越大時,執行速度增加的情況越不明顯:
/**
* 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];
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));
sqrt n O(√n)
keywords: x*x < n
- n 是 100 的話,只會跑 10 次,也就是
√100
,所以可以知道是√n
/**
* Logarithmic Run Time: 隨著資料量增加,執行時間雖然會增加,但增加率會趨緩
* Big O Notation: "O (√n)"
**/
function isPrime(n: number): boolean {
// 關鍵在這裡的 X * x
for (let x = 2; x * x < n; x += 1) {
if (n % x === 0) {
return false;
}
}
return true;
}
圖示
把上面這四種類型用圖線表示,縱軸是時間、橫軸是輸入資料量的多少,可以用來判斷這四種類型的演算法(函式)的好壞:
圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy
Space Complexity
空間複雜度指的是程式佔用記憶體的空間,一樣可以透過 Big O 來表示。
時間複雜度和空間複雜度之間有時有 trade-off 存在,也就是為了提升時間複雜度(提升處理效率)必須犧牲空間複雜度;有時則需要為了空間複雜度(減少記體體的消耗)而犧牲時間複雜度。
- 增加變數
- 資料結構
- 呼叫函式
- Allocation
範例程式碼
O(1)
// space complexity of foo: O(1)
function foo(n) {
for (let i = 0; i < n.length; i++) {
console.log('foo');
}
}
O(n)
// space complexity of bar: O(n)
function bar(n) {
const arr = [];
for (let i = 0; i < n; i++) {
arr[i] = n;
}
return arr;
}
完整程式碼
- Big O Notation @ Repl.it
資料來源
- Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy
- Master the Coding Interview: Data Structures + Algorithms @ Udemy
- 不只是刷題的 Leetcode 訓練營 @ ALPHA Camp