Big O notation with JavaScript examples

•5 min read
algorithmbig-o-notationjavascript
Back

Big O notation

下方為常見的時間複雜度，從快到慢依序為：

  1. O(1) (constant)
  2. O(log n) (logarithmic)
  3. O(n) (linear)
  4. O(n log n) (n log n)
  5. O(n²) (quadratic)
  6. O(2ⁿ) (exponential)
  7. O(n!) (factorial)

O(n) - Linear

透過 for loop 計算費氏數列，時間複雜度為 O(n)

//  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]
function fib(n) {
  const arr = [0, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

下方為遞迴檢查是否為回文的範例程式碼（順讀和倒讀都一樣的詞)

當字串長度為奇數時，palindrome 會被遞迴執行 n/2 + 1 次，長度為偶數時，遞迴執行 n/2 次

因為 Big O 忽略係數、常數的關係，時間複雜度仍用 O(n) 作為表示

// if there are less than two characters in the string, return true.
// compare first and last characters and recur for remaining substring.
 
function palindrome(str) {
  if (str.length < 2) {
    return true;
  } 
 
  const firstChar = str.charAt(0);
  const lastChar = str.charAt(str.length - 1);
  
  if (firstChar === lastChar) {
    return palindrome(str.substring(1, str.length - 1));
  }
  
  return false;
}

O(n²) - Quadratic

簡單來說就是迴圈中再重複一次相同次數的迴圈，下方程式碼以輸出階梯圖形為例

// steps(3)
// '#  '
// '## '
// '###'
function steps(n) {
  for (let row = 0; row < n; row++) {
    let stair = '';
    for (let column = 0; column < n; column++) {
      stair += column <= row ? '#' : ' ';
    }
    console.log(stair);
  }
}

O(2ⁿ) - Exponential

下方程式碼使用遞迴函式來計算費氏數列

當 fib(n) 且 n > 1 時，除了預先定義好的 fib(0)、fib(1) 以外，皆需要逐層調用 fib(n - 1) + fib(n - 2) 來計算 (如下方圖示)，其時間複雜度約為 O(2ⁿ)

function fib(n) {
  if (n < 2) {
    return n;
  }
  
  return fib(n - 1) + fib (n - 2);
}

補充 - 利用 memoization 優化 recursion fibonacci 執行效率

function memoize(fn) {
  const cache = {};
  return function(...args) {
    if (cache[args]) {
      return cache[args];
    }
    
    const result = fn.apply(this, args);
    cache[args] = result;
    return result;
  }
}
 
function fib(n) {
  if (n < 2) {
    return n;
  }
 
  return fib(n - 1) + fib (n - 2);
}
 
fib = memoize(fib);

O(log n) - Logarithm

參考 維基百科 - 對數

3⁴ = 3 * 3 * 3 * 3 = 81

我們可以得出 4 = log₃ 81 用日常語言說，即「81 以 3 為底的對數是 4」。這個意思就是說，3 的 4 次方是 81。

O(log n) 不論對數的底數為何，時間複雜度與資料量增長的關係是一樣的

以 binary search 為例，我們不需要在已經排序好的集合中，將元素一個一個取出做判斷。利用中間元素可以將搜索範圍二分為前半、後半，將目標元素與中間元素比較後，決定下次的搜尋範圍，直到找到相同元素或只剩至一個元素為止，若只剩一個元素代表該目標不存在。

在一個長度為 8 的陣列使用 binary search，即為 3 = log₂ 8，表示在最差的情況下，需要經過 3 次步驟得到結果

const people = [
  { id: 1, name: 'Sam' },
  { id: 3, name: 'Sarah' },
  { id: 5, name: 'John' },
  { id: 6, name: 'Burke' },
  { id: 10, name: 'Simona' },
  { id: 12, name: 'Asim' },
  { id: 13, name: 'Niki' },
  { id: 15, name: 'Aysegul' },
];
 
function binarySearch(array, id) {
  let min = 0;
  let max = array.length - 1;
  let element;
  
  while(min <= max) {
    const index = Math.floor((min + max) / 2);
    element = array[index];
    
    if (element.id < id) {
      min = index + 1;
    } else if (element.id > id) {
      max = index - 1;
    } else {
      return element;
    }
  }
  
  return undefined;
}
 
binarySearch(people, 15);
 
/**
 * min: 0, max: 7, index: 3
 * min: 4, max: 7, index: 5
 * min: 6, max: 7, index: 6
 * min: 7, max: 7, index: 7
 **/

Reference