演算法筆記:Big O Notation

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

為什麼你要知道現在算法的 Time Complexity?唯有知道現況才能優化!普遍而言,優秀的算法都是 O(log n),如果不知道 O(log n) 的含義要怎麼達到呢?如果不知道現在的狀況是 O(n) 或是 O(n^2) 要怎麼優化呢?另外自己在寫 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^2))

隨著資料量的增加,執行時間會以指數(平方)成長。最常見就是兩個 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 = 2²),n = 16 時,程式會在 4 個步驟完成(16 = 2⁴),以此類推。

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

O(n log n)

時間複雜度為 O(n log n) 的演算法,代表著執行時間會隨著以二為底的 log n 再乘上 n 成長。最常見的例子是合併排序法 (Merge Sort) 與快速排序法 (Quick Sort)。

Merge Sort 合併排序法

合併屬於比較複雜一點的步驟,因為在合併的過程中我們同時也要完成排序。詳細說明可以參考:
1. 觀念講解十分清楚的 appwork 文章
2. 使用 JS 說明的 jpchender 文章

拆分

拆分屬於簡單的步驟,從上面的圖就可以觀察,把一個 n 的陣列切切切,切到每個小陣列都只有 1 個數字時,需要 n-1 個步驟(切 n-1 刀)。

合併

合併排序法中,我們總共需要進行幾回合這樣的合併呢?在上面的例子中,從一開始 7 個小陣列合併成 4 個,再從 4 個合併成 2 個,最後合併成 1 個,因為每一回合的合併,都可以讓下一回合需要合併的陣列減少一半,這樣的特性表示總共需要合併的回合數會是以 2 為底的 log n 次。

排序

把兩個排序好的小陣列合併成一個排序好的大陣列需要多少步驟呢?在上圖的每次排序中,如果兩個小陣列加起來有 n 個數字,總共就需要 n 個步驟。

  • 每回合的合併需要花:O(n)
  • 總共需要回合數:O(log n)
  • 拆分的步驟數為 n-1

拆分的步驟數為 n-1,合併的步驟數為 n 乘上 log n,相加後我們可以得知合併排序法總共的步驟數為 n-1 + n log n。化成大 O 符號時,我們只計最高項係數並省略常數,因此我們終於得到合併排序法的時間複雜度,即為 O( n log n)。

圖示

把上面這幾種類型用圖線表示,縱軸是時間、橫軸是輸入資料量的多少,可以用來判斷這幾種類型的演算法(函式)的好壞:

比 O(n log n) 效率更差都無法實際上運作了

可以參考以下影片,針對如何計算 Big O 有非常詳細的介紹,基本概念是顯示影響圖形最大的因素,例如:合併排序法總共的步驟數為 n-1 + n log n,n-1 比起 n log n 的影響較小。常數也可以捨去,例如 3n 可以視為 n、n^2+100 可以視為 n^2。

參考資料:

1. https://pjchender.blogspot.com/2017/09/big-o-notation-time-complexity.html
2. https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5

Share on facebook
Facebook
Share on linkedin
LinkedIn
Share on twitter
Twitter

More to explorer

Close Menu