演算法筆記：Big O Notation

Published in

Traveling Light Taipei

7 min readSep 2, 2020

技術面試很怕白筆題，很多時候不只是能不能解出問題，更是面試官不問提問能不能優化？現在的 Time Complexity 是什麼？經由 Alpha camp 的課程，獲益不少想法，因此記錄下來分享。

為什麼你要知道現在算法的 Time Complexity？唯有知道現況才能優化！普遍而言，優秀的算法都是 O(log n)，如果不知道 O(log n) 的含義要怎麼達到呢？如果不知道現在的狀況是 O(n) 或是 O(n²) 要怎麼優化呢？另外自己在寫 leetcode 時候也可以嘗試說明寫法，先說再寫，也可以設定時間限制來模擬面試。

Big O Notation 代表演算法時間函式的上限（Upper bound），表示在最壞的狀況下，演算法的執行時間不會超過Big-Ο。

以上說明可以得知其實演算法的 Time Complexity 可以分為最佳狀態(best case)與最壞狀態(worst case)，一般來說 Big O Notation 表示最壞狀況，實務上可能會使用平均狀況(average case)最佳的解。

以下依序介紹常見的 Big O Time Complexity

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 return1st(arr) {
  return arr1[0]
}
return1st(arr1)    // 1
return1st(arr2)    // 1

Linear Run Time (O(n))

基本上回圈 for loop 都是這種狀況，當輸入的資料越多的時候，它會等比例輸出越多的內容，因此會需要消耗等比例越多的時間：

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²))

隨著資料量的增加，執行時間會以指數（平方）成長。最常見就是兩個 for loop，許多演算法的暴力解都會是這個答案。

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))

O(log n) 這邊的 log 都是以二為底，代表當輸入的數量是 n 時，執行的步驟數會是 log n。當 log n = x 的意思是 n = 2^x。舉例來說，當 n = 4，程式會在 2 個步驟完成（4 = ²²），n = 16 時，程式會在 4 個步驟完成（16 = ²⁴），以此類推。

隨著資料量增加，執行時間雖然會增加，但增加率會趨緩，基本上白板題會希望找出這個答案，或是 O(nlog 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))