Big O — 時間複雜度與空間複雜度

每一種題目可能有數種的解法，那我們應該怎麼評估每種解法的優劣呢?以前的我應該會回答，當然是越簡短的寫法越好呀! 不過，寫過 leetcode 之後，會發現有時候很簡短的解法，執行效率反而看不見別人的車尾燈(吊車尾)，那麼 leetcode 是怎麼評斷解法的好壞呢? 答案是透過時間複雜度和空間複雜度來評估。

• 時間複雜度(Time Complexity):執行函式需要花費的時間
• 空間複雜度(Space Complexity):執行函式會占用的記憶體空間

關於時間複雜度

• 演算法運算次數的增長效率
• 演算法的執行時間不是以秒計算的， 是以運算次數計算的
• 演算法的執行時間 ，不一定會隨著元素數量的增加而等比增加

這邊要特別注意，執行的時間並非以秒為單位，因為家用電腦與超級電腦的運算速度根本天差地遠，比較秒數的話其實沒有多大的意義，因此是用次數來作計算，而我們習慣用 O 來表示演算法的執行效率，作為評估演算法執行效率好不好的指標，當函式輸入的 Input 長度變長的時候，就可以了解演算法的效率趨勢，效能差的演算法的曲線就會陡峭上升像是 O(n²)而好的演算法的曲線會趨於平緩 O(log n)。

• O(1) —  常數，不管輸入的 n 為多少，都只要執行一次

無論 arr 的 length 有多長，都只要執行一次即可

//ex:找出 index=2 的值為何?
const arr = ["andy", "peggy", "debby"];
console.log(arr[2]);

• O(log n) —  對數(n 是 2 的幾次方)

輸入 8 的話，log 8 = 3，也就是 8 = 2³ (8 是 n 的 3 次方)，所以經過 3 個步驟就可以找到我們要的答案，簡單來說就是不斷的剖半，像是二分搜尋法

• O(n) —  線性

跑一次迴圈，所以如果輸入的 n 越長，執行的次數也會等比增加

//ex:找出這個陣列有沒有 debby 這個人,不用 indexOf 和 includes 話，就是土法煉鋼，從頭找到尾，一個一個慢慢找

const arr = ["andy", "peggy", "debby"];
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === "debby") return true;
}

• O(n*log n) —  線性對數

ex:快速排序法，在之後的文章會有更詳細的解說

• O(n²) —  平方，n 的平方

ex:用雙迴圈印出一個九九乘法表
//n*n=n²

for (let i = 1; i <= 9; i++) {
  for (let j = i; j <= 9; j++) {
    console.log(`${i}*${j} = ${i * j}`);
  }
}

• O(n!) —  階乘，像是 n 階乘，ex: n x n-1 x … x 3 x 2 x 1

最理想的時間複雜度就是 O(log n)或是 O(1)

關於空間複雜度

執行程式佔用的記憶體空間 ，占用越多越吃資源，一樣也是用 Big O 來表示，而時間複雜度和空間複雜度兩者是可以互相 trade off 的。

甚麼是 trade off? 有時候可以用空間來換取時間 ，或是用時間換取空間，依照當時的使用情境來做取捨。

O(1)

不管輸入的 n 為多少，都只會建立一個變數 total，因此空間複雜度為 O(n)

const add = (n) => {
  let total = 0;
  for (let i = 0; i < n; i++) {
    total += i;
  }
  return total;
};

O(n)

arr 的長度會根據使用者輸入的 n 來增長，因此空間複雜度為 O(n)

const createArray = (n) => {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
};