最近開始接觸演算法之後，常常看到一些奇怪的符號：

O(1)、O(n)、O(n²)……

第一次看到的時候真的有點害怕，瞬間勾起數學惡夢（笑）。

但也因為一直看到它們，讓我很好奇：

「這些 O 到底代表什麼？」

查了一下才知道，全名是 Big O（Big O Notation），是一種用來描述演算法「花費時間」以及「佔用記憶體空間」如何隨著資料量增加而成長的表示方式。

Big O 的用途是看什麼？

Big O 關心的是：

當資料量越來越大時，程式需要處理的工作量會怎麼成長？

常見的 Big O 還有 O(log n)、O(n log n) 等，不過這次先從三個比較容易理解的開始：

• O(1)：常數時間複雜度
• O(n)：線性時間複雜度
• O(n²)：平方時間複雜度

假設今天我是動物園管理員

系統裡記錄著所有動物：

const animals = ["獅子", "老虎", "猴子", "大象"];

O(1)：已經知道動物的位置

今天我想查詢編號 2 的動物是誰，因為已經知道牠的位置，可以直接取得資料：

function getAnimal(animals, index) {
  return animals[index];
}

不管有 10、100 還是 10,000 筆資料，都不需要從頭開始找。

資料增加，但操作次數基本不變，可以理解成 O(1)。

O(n)：不知道動物在哪裡，只能一隻一隻找

如果今天我要確認動物園裡有沒有「大象」，卻不知道牠的位置：

function findAnimal(animals, target) {
  for (const animal of animals) {
    if (animal === target) return true;
  }

  return false;
}

最壞的情況下，大象剛好在最後面。

10 筆資料最多找 10 次，100 筆最多找 100 次。

資料量 n 增加，需要處理的次數也跟著增加，這就是 O(n)。

O(n²)：檢查有沒有重複登記

假設動物園的資料可能重複登記，所以要檢查每一筆資料是否跟其他資料重複：

function checkDuplicate(animals) {
  for (let i = 0; i < animals.length; i++) {
    for (let j = 0; j < animals.length; j++) {
      if (i !== j && animals[i] === animals[j]) {
        return true;
      }
    }
  }

  return false;
}

外層每處理一筆資料，內層又要把所有資料檢查一次。

如果有 10 筆，就是大約 10 × 10 = 100 次；100 筆則會來到 100 × 100 = 10,000 次。

也就是：

n × n = n²

因此可以理解成 O(n²)。

所以，程式做得出來，不代表做得有效率

當資料只有 10 筆時，可能感覺不出 O(n) 和 O(n²) 有什麼差別。

但資料變成 100 筆時，一個大約是 100 次操作，另一個卻可能來到 10,000 次。

所以現在看到一段程式，我也可以開始多問自己一個問題：

「如果今天資料越來越多，我現在這個寫法，需要做的事情會增加多少？」

這就是我目前對「時間複雜度」最初步的理解。

最後附上一個互動圖，可以觀察不同的 Big O 在資料量增加時，工作量會有什麼變化：

常見的時間複雜度互動圖

參考資料

PJCHENder，〈演算法與資料結構簡介〉
https://pjchender.dev/dsa/algo-intro/

iT 邦幫忙，〈時間複雜度相關文章〉
https://ithelp.ithome.com.tw/m/articles/10213615

Gary Lin，〈演算法複雜度新手指南〉
https://garylin.dev/blog/posts/algorithm-complexity-beginner-guide