演算法圖解 Algorithms（Illustrated for Curious Programmers）

📌 30 秒摘要（Layer 3）

用大量圖解把演算法基礎講清楚：先學會用 Big-O 分析成本（時間/空間），再認識常見資料結構（陣列、鏈結串列、雜湊表、樹、圖）各自的取捨，最後掌握幾種演算法設計策略（分治、貪婪、動態規劃）。重點不是背程式碼，而是建立「面對問題時，該選什麼結構、用什麼策略、成本多少」的判斷力。

🗺 心智圖（Canvas）

演算法圖解

演算法圖解

📈 Big-O 成本分析

工具-時間複雜度分析

🎯 什麼情境該想到我

當你想判斷「這段程式在資料量變大時會不會爆掉」，或在兩個方案間比較效率時。

⚙️ 怎麼用

1. 看主導項：只看輸入 n 變大時成長最快的部分，忽略常數與低階項。
2. 常見等級（由快到慢）：O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ)。
3. 快速估：單層迴圈 O(n)、巢狀雙迴圈 O(n²)、每次砍半 O(log n)、排序多為 O(n log n)。
4. 同時看空間複雜度：記憶體也可能是瓶頸（時間換空間的取捨）。

先估複雜度，再決定「資料規模下這個方案可不可行」，避免上線才發現慢爆。

★ 從程式碼讀出複雜度：四個模式

程式碼的形狀	複雜度	注意
一層迴圈跑 n 次	O(n)
兩層巢狀，內層也跑 n 次	O(n²)
兩層巢狀，內層從 i 開始（for j := i; j < n; j++）	仍是 O(n²)	總次數 $n+(n-1)+\cdots +1=n(n+1)/2$，常數減半但階數不變
每次把問題砍半（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²)。

★ 用限制條件反推可行的複雜度

一秒大約能做 $10^8$ 量級的簡單操作（經驗法則，實際取決於操作種類與語言）。反推：

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 時常數/實作細節可能主導，別過早為漸進最佳而犧牲可讀性（見 工具-簡單清楚至上）。

🔗 相關工具

• 工具-資料結構的選擇 —— 複雜度多半是資料結構決定的；估完發現會爆，第一個該換的就是它
• 工具-演算法設計策略 —— 換結構還不夠時的下一層：先辨認問題屬於分治／貪婪／動態規劃哪一類再重寫

成長趨勢排序 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

🗂 資料結構取捨

工具-資料結構的選擇

🎯 什麼情境該想到我

分工：這張是「選哪個結構」的決策卡。每個結構的內部機制、複雜度推導、Go 實作細節 → reference/演算法導論/（雜湊表、二元堆積、紅黑樹、堆疊與佇列、鏈結串列、併查集）。

當你要決定「一堆資料該用什麼結構存」，或發現查找/插入很慢時。選對結構，效能天差地別。

⚙️ 怎麼用（依「主要操作」選）

• 常隨機存取、少增刪 → 陣列（O(1) 索引）。
• 常在中間插入/刪除 → 鏈結串列。
• 常用鍵查值 / 去重 → 雜湊表（平均 O(1)）。
• 需要保持有序 + 範圍查詢 → 平衡樹 / 有序結構（O(log n)）。
• 常取最大/最小 → 堆積（Heap / 優先佇列）。
• 關係/連通/最短路 → 圖。

先問：這份資料最常做哪個操作？ 那個操作要快，就選對應結構。

★ Go 裡的實際對照表

Go 標準函式庫沒有內建的有序 map、樹、集合型別。實際可用的選項：

需求	Go 的做法	備註
有序、按索引存取	[]T	預設選擇。連續記憶體，快取友善
用鍵查值	map[K]V	走訪順序刻意隨機，不要依賴
集合（去重）	map[T]struct{}	struct{} 不佔空間
有序 + 範圍查詢	排序好的 slice + slices.BinarySearch	讀多寫少時最實用；插入是 O(n) 的搬移
有序 + 頻繁插入刪除	第三方 B-tree（如 github.com/google/btree）	標準函式庫沒有
取最小／最大	container/heap（實作 5 個方法的介面）	優先佇列、Top-K、Dijkstra
FIFO 佇列	slice（q = q[1:]）或 channel（跨 goroutine 時）	q[1:] 不會釋放前面的記憶體，長期運作的佇列要定期重新配置或用環形緩衝區
雙向鏈結串列	container/list	幾乎永遠不該用：每個節點獨立配置、快取極不友善（見 鏈結串列）

TS 對應：Array、Map（保留插入順序）、Set；沒有內建堆積，需要自己寫或用套件。用 Map 而不是一般物件當字典——物件會繼承原型上的鍵，也只能用字串當鍵。

★ 小資料量時，Big-O 會說謊

Big-O 只描述「n 很大時」的趨勢。n 很小時，常數與記憶體存取模式才是主角。實測（Apple M4、Go 1.26.4，字串鍵、查詢都命中，2026-09-25）：

n	slice 線性搜尋	排序 slice + 二分搜尋	map
4	4.6 ns	8.7 ns	6.1 ns
8	7.9 ns	11.4 ns	7.5 ns
16	14.0 ns	14.9 ns	5.3 ns
64	53.0 ns	18.9 ns	5.6 ns
1024	627 ns	30.9 ns	5.4 ns

讀法：

• n ≤ 8 左右，線性搜尋和 map 打平甚至更快——不用為了 5 個元素建 map。
• map 的查詢時間幾乎不隨 n 變（O(1) 的實際樣子）；線性搜尋隨 n 線性上升（O(n)）；二分搜尋緩慢上升（O(log n)）。
• 交叉點會隨鍵的型別、CPU、快取狀態移動，所以要自己量，不要背數字。

★ 選擇的決策順序

1. 最常做的操作是什麼？ 查、插、刪、排序、取極值、範圍查詢。
2. 資料量級？ 小於幾十個 → 幾乎用什麼都行，選最簡單的（通常是 slice）。
3. 讀寫比例？ 讀遠多於寫 → 可以接受寫入慢的結構（排序 slice），換取查詢快又省記憶體。
4. 需要有序嗎？ Go 的 map 不保證順序；需要穩定輸出（例如產生 JSON、測試比對）時，先把鍵取出來排序：slices.Sorted(maps.Keys(m))。
5. 會被多個 goroutine 同時存取嗎？ 內建 map 不是併發安全的，同時讀寫會直接讓程式 fatal error。加 sync.RWMutex，或在「寫一次、讀很多次」的情況用 sync.Map。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 選擇是「操作頻率」的取捨，沒有全能結構；查得快的常插得慢，反之亦然。

• 記憶體也是成本：map 每個條目有額外的桶與中繼資料開銷；存一億個小整數時，排序 slice 可能只用 map 的幾分之一記憶體。選結構時要同時看時間與空間（見 工具-時間複雜度分析）。

🔗 相關工具

• 工具-時間複雜度分析、工具-儲存引擎B-Tree與LSM-Tree（DB 層的資料結構取捨）

陣列 vs 鏈結串列 陣列隨機存取快、插入慢；鏈結串列插入快、查找慢

雜湊表 平均 O(1) 查找，代價是無序與雜湊衝突

樹／堆積／圖 有序查找、取極值、關係網路各有專屬結構

🧠 演算法設計策略

工具-演算法設計策略

🎯 什麼情境該想到我

分工：這張是「看到題目，辨認該用哪個策略」的分類卡。各策略的機制、證明、程式碼 → 分治法、貪婪演算法、動態規劃；具體演算法 → reference/演算法導論/。

當你面對一個計算/最佳化問題、暴力解太慢、想不到更好解法時。先辨認它屬於哪種策略。

⚙️ 怎麼用（辨認問題型態 → 套對應策略）

1. 分治（Divide & Conquer）：能把問題拆成同型的小問題、各自解完再合併 → 如合併排序、快排、二分。
2. 貪婪（Greedy）：每一步都取「當下看起來最好」的選擇即可得全域最佳 → 如區間排程、Huffman。（要能證明貪婪選擇性質）
3. 動態規劃（DP）：有重疊子問題 + 最佳子結構 → 把子問題結果記下來（記憶化/表格），避免重算 → 如背包、最長公共子序列。
4. 想不到時：先寫暴力解，再找「重複計算」或「可拆解」的結構往上述三類靠。

★ 從題目的「訊號」辨認策略

題目裡出現的訊號	優先考慮	為什麼
「最多／最少／最大／最小」+「有很多種選法」	動態規劃	最佳化問題；選法之間常共享子問題
「有幾種方法」	動態規劃	計數問題幾乎都是 DP
每一步的選擇不會影響之後的選項	貪婪	但要能證明（見下）
資料可以切成獨立的兩半各自處理	分治	合併排序、最近點對
輸入已排序，或答案有單調性（「值越大越容易滿足」）	二分搜尋（包括對答案二分）	每步砍掉一半
「連續子陣列／子字串」+ 某種條件	滑動視窗或雙指標	O(n) 而不是 O(n²)
「列出所有」組合／排列／路徑	回溯（DFS + 剪枝）	答案本身就是指數級，只能靠剪枝加速
關係、依賴、連通、路徑	圖演算法（BFS、DFS、拓撲排序、最短路徑）	先把問題建模成圖

★ 貪婪：一個反例就能推翻

找零問題：硬幣面額 {1, 3, 4}，湊出 6 元，最少幾枚？

• 貪婪（每次拿最大的）：4 → 剩 2 → 1 + 1，共 3 枚。
• 最佳解：3 + 3，共 2 枚。

貪婪在台幣面額 {1, 5, 10, 50} 上是對的，換一組面額就錯了。所以「貪婪看起來很合理」不是證明。

證明貪婪正確的標準方法（交換論證）：假設有一個最佳解和貪婪的選擇不同，證明可以把最佳解中的某個選擇換成貪婪的選擇，而結果不會變差。如果換得過去，貪婪就是對的；換不過去，通常就找到了反例。

實務做法：寫一個暴力解，用小輸入（n ≤ 10）大量比對貪婪解和暴力解。對不上就代表貪婪錯了。

★ 動態規劃的四步設計法

1. 定義狀態：dp[i] 代表什麼？要精確到一句話——「前 i 個物品、容量 j 時的最大價值」。狀態定義錯了，後面全錯。
2. 寫轉移方程式：dp[i] 怎麼從更小的狀態算出來？通常是「最後一步做了什麼選擇」的所有可能取最佳。
3. 確定初始值與計算順序：dp[0] 是什麼？計算 dp[i] 時，它依賴的狀態已經算好了嗎？
4. 複雜度 = 狀態數 × 每個狀態的轉移成本。例如 LCS：狀態 m×n，每個 O(1) → O(mn)。

★ 暴力解 → 最佳解的標準路線

暴力解（列舉所有可能）
  ↓ 發現大量重複計算？ → 記憶化（DP）
  ↓ 發現不需要考慮所有可能？ → 剪枝（回溯）或貪婪
  ↓ 發現有序或單調？ → 二分搜尋
  ↓ 發現內層迴圈在找東西？ → 換資料結構（map、heap）把內層降到 O(1) 或 O(log n)

第一步永遠是寫出暴力解：它是正確性的基準，也是找出「哪裡在浪費」的起點。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 貪婪不是萬用——很多問題貪婪會得到次佳解，需要 DP。用小例子驗證。

🔗 相關工具

• 工具-時間複雜度分析 —— 挑策略的量尺，判斷換策略後真的降階了還是只是換寫法
• 工具-程式問題解決策略 —— 上位流程，這張是它「辨認問題類型」那一步的專用工具箱

分治 拆小再合併，如快速排序／合併排序

貪婪 每步取當下最佳，簡單但不一定全域最佳

動態規劃 重疊子問題記憶化，避免重複計算

🔎 搜尋與排序

二分搜尋 有序資料下 O(log n)

遞迴 用基準情形＋自我呼叫描述問題

常見排序的複雜度 快排／合併 O(n log n)、氣泡／插入 O(n²)

Link to original

🧰 這本書給我的工具

• 工具-時間複雜度分析 — 判斷一段程式/方案「會不會太慢」時
• 工具-資料結構的選擇 — 決定資料要用什麼結構存時
• 工具-演算法設計策略 — 面對演算法題、想不到解法時

✨ 關鍵重點（Layer 1–2）

• Big-O：描述輸入變大時成本的成長趨勢；O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
• 資料結構取捨：陣列（隨機存取快、插入慢）、鏈結串列（插入快、查找慢）、雜湊表（平均 O(1) 查找）、樹/堆積、圖。
• 設計策略：分治（拆小再合，如快排/合併排序）、貪婪（每步取當下最佳）、動態規劃（重疊子問題記憶化）。
• 搜尋與排序：二分搜尋、遞迴、常見排序的複雜度。

💬 金句原文（Layer 0）

• 「選對資料結構，問題就解一半了。」

🔗 相關

• 像程式設計師一樣思考 —— 互補視角，本書給演算法知識，那本給卡住時的解題策略
• 程式設計方法 —— 互補視角，補上「從問題到程式」的系統化流程