Big-O：資料變大時，工作量怎麼成長

Learning outcomes

• 能讀 O(1)、O(n)、O(log n)、O(n²)。
• 能從 loop 結構推估基本 complexity。
• 能區分 asymptotic growth 與實際常數成本。
• 能理解 data structure choice 如何改變 complexity。

1. O(1)：與 n 無關的固定步驟模型

function first(items) {
  return items[0];
}

不論 array 有 10 筆或 100 萬筆，取得第一個索引的抽象步驟數不隨 n 線性增加。

2. O(n)：每個 item 看一次

function hasTitle(
  courses,
  title
) {
  for (const course of courses) {
    if (course.title === title) {
      return true;
    }
  }

  return false;
}

Worst case 可能掃完整個 collection。

3. O(n²)：nested work

for (const a of items) {
  for (const b of items) {
    compare(a, b);
  }
}

n 翻 10 倍，pair combinations 可接近 100 倍。資料小時沒感覺，資料大時差距迅速放大。

4. O(log n)：每一步大幅縮小搜尋空間

sorted data
  ↓ compare middle
half discarded
  ↓
compare middle again

Binary search 是典型例子，但前提是資料有適合的排序/結構。

5. Big-O 不取代 benchmark

O(n) 的高常數 implementation 可能在小資料比某個 O(n log n) 慢；I/O、cache、database index、network 都會影響實際 latency。Big-O 是設計層的成長模型，不是 stopwatch。

Project checkpoint：Course Lookup

比較每次用 Array.find 線性查找，與先建立 Map index 的成本。

// repeated lookup
courses.find(
  c => c.id === targetId
);

// pre-index once
const byId =
  new Map(
    courses.map(
      c => [c.id, c]
    )
  );

byId.get(targetId);

Debug evidence：資料量變 100 倍後才慢

這種症狀很值得檢查 asymptotic behavior。先量測 input size、operation count、hot path，再判斷是否有 nested scan、重複 parse、重複 DB query。