[Algorithm] Big O Notation 演算法的複雜度

• 電腦要解多久的問題稱為演算法的複雜度，用O()表示，唸為Big O。
• Big O Notation 代表演算法時間函數的上限，表示在最壞的情況下，演算法的執行時間不會超過Big O

類型：

圖片來源: Learning Algorithms in JavaScript from Scratch by Eric Traub

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)    // 1, 2
log(arr2)    // 1, 2

2. Linear Run Time — O(n)

當輸入越多時，需要等比例輸出越多內容，因此需要消耗等比例越多的時間。

function logAll(arr) {
  for (var i = 0; i < arr.length; i++) {
    console.log(arr[i])
  }
}
logAll(arr1)  // 1, 2, 3, 4, 5
logAll(arr2)  // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

3. Exponential Run Time — O(n²)

當輸入越多時，時間會以指數成長。

function addAndLog (arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length; j++) {
      console.log (arr[i] + arr[j])
    }
  }
}
addAndLog(arr1)  // 25 pairs logged out
addAndLog(arr2)  // 100 pairs logged out

4. Logarithmic Run Time — O(log n)

當輸入越多，執行時間雖會增加，但增加率會趨緩。

範例: 二元搜尋法，例如用字典查House這個單字時，會先對半翻開字典，此時落在L的章節，因為H在L之前，所以就可以直接略過字典的後半部，接著再翻到前半部的一半…，以此類推。因此當資料量越大，執行時間增加的情況越不明顯。

function binarySearch(arr, key) {
  var low = 0;
  var high = arr.length -1;
  var mid;
  var 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;
}

參考來源: Learning Algorithms in JavaScript from Scratch by Eric Traub