🎯 什麼情境該想到我
當你想判斷「這段程式在資料量變大時會不會爆掉」，或在兩個方案間比較效率時。
⚙️ 怎麼用
- 看主導項：只看輸入 n 變大時成長最快的部分，忽略常數與低階項。
- 常見等級（由快到慢）：O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ)。
- 快速估：單層迴圈 O(n)、巢狀雙迴圈 O(n²)、每次砍半 O(log n)、排序多為 O(n log n)。
- 同時看空間複雜度：記憶體也可能是瓶頸（時間換空間的取捨）。
先估複雜度，再決定「資料規模下這個方案可不可行」，避免上線才發現慢爆。
★ 從程式碼讀出複雜度：四個模式
| 程式碼的形狀 | 複雜度 | 注意 |
|---|---|---|
| 一層迴圈跑 n 次 | O(n) | |
| 兩層巢狀，內層也跑 n 次 | O(n²) | |
兩層巢狀，內層從 i 開始（for j := i; j < n; j++） | 仍是 O(n²) | 總次數 ，常數減半但階數不變 |
每次把問題砍半（n /= 2） | O(log n) | 二分搜尋、平衡樹 |
| 外層 n 次，內層砍半 | O(n log n) | |
| 兩個獨立的輸入 | O(n + m) 或 O(n·m) | 不要合併成 n：for a in A { for b in B } 是 O(n·m) |
★ Go 裡藏起來的成本：看起來是 O(1)，其實不是
| 寫法 | 實際成本 | 為什麼 |
|---|---|---|
迴圈裡 s += x（字串） | O(n²) 總計 | 字串不可變，每次 += 都配置新字串並複製全部內容 → 用 strings.Builder |
迴圈裡 slices.Contains(list, x) | O(n·m) | Contains 是線性搜尋 → 先把 list 轉成 map[T]struct{} |
迴圈裡 append | 攤還 O(1) | 但偶爾一次 O(n) 的擴容；知道大小就 make([]T, 0, n)（見 工具-攤還分析） |
copy、slices.Clone、傳大陣列（非 slice）當參數 | O(n) | 陣列是值型別，傳參數會整個複製；slice 只複製 header |
len(s)、len(m) | O(1) | 長度是存起來的 |
把 string 轉 []byte（或反過來） | 通常 O(n) | 需要複製，除非編譯器能證明不需要 |
| 在 slice 開頭插入或刪除 | O(n) | 要搬移後面所有元素；需要頻繁操作頭部就用環形緩衝區 |
TS 對應：array.includes()、indexOf()、shift()、unshift()、splice() 都是 O(n)；在迴圈裡用它們一樣會變成 O(n²)。
★ 用限制條件反推可行的複雜度
一秒大約能做 量級的簡單操作（經驗法則，實際取決於操作種類與語言）。反推：
| n 的上限 | 可以接受的複雜度 | 常見的解法 |
|---|---|---|
| ≤ 10 | O(n!) | 列舉所有排列 |
| ≤ 20–25 | O(2ⁿ) | 列舉子集、位元遮罩 DP |
| ≤ 500 | O(n³) | 三層迴圈、Floyd-Warshall |
| ≤ 5,000 | O(n²) | 兩層迴圈、二維 DP |
| ≤ 10⁶ | O(n log n) | 排序、堆積、二分搜尋 |
| ≤ 10⁸ | O(n) | 一次走訪、雙指標 |
| 更大 | O(log n) 或 O(1) | 數學公式、二分搜尋 |
這張表在面試時特別有用：看到 n ≤ 10⁵，就知道 O(n²) 不行，不用寫完才發現超時。
★ Big-O、Θ、Ω 的差別（和為什麼平常說的 O 其實是 Θ）
- O(g)：上界——「最多這麼慢」。O(n) 的演算法技術上也是 O(n²)，因為 n² 也是上界。
- Ω(g)：下界——「至少這麼慢」。例如比較式排序是 Ω(n log n)，不可能更快。
- Θ(g)：同時是上界和下界——「剛好是這個量級」。
日常說「合併排序是 O(n log n)」時，意思其實是 Θ(n log n)。這個區別在證明下界時才重要：說「這個問題的任何解法都是 Ω(n log n)」，才能證明你不可能再做得更好。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
- Big-O 是趨勢不是絕對；小 n 時常數/實作細節可能主導，別過早為漸進最佳而犧牲可讀性（見 工具-簡單清楚至上）。
🔗 相關工具
- 工具-資料結構的選擇 —— 複雜度多半是資料結構決定的；估完發現會爆，第一個該換的就是它
- 工具-演算法設計策略 —— 換結構還不夠時的下一層：先辨認問題屬於分治／貪婪／動態規劃哪一類再重寫