演算法導論 Introduction to Algorithms (CLRS)

📌 30 秒摘要（Layer 3）

演算法領域最權威、最全面的教科書。與演算法圖解的直覺入門不同，本書提供嚴謹的數學基礎：如何用「迴圈不變式」證明演算法正確、如何用「攤還分析」算出一連串操作的平均成本、如何解「遞迴式」求出分治演算法的複雜度，並系統性涵蓋排序、資料結構、圖論、動態規劃、NP 完全等。是把演算法從「會用」提升到「能證明、能分析」的參考書。

🗺 心智圖（Canvas）

演算法導論
📗 演算法導論

Introduction to Algorithms (CLRS)
🔬 即用分析工具
工具-迴圈不變式
🎯 什麼情境該想到我

當你想「嚴謹確認一個迴圈/演算法真的正確」，或迴圈邏輯容易出 off-by-one、難以推理時。

⚙️ 怎麼用（找出並驗證一條在迴圈中恆成立的性質）

找不變式：一句在「每次迭代開始前都成立」的陳述（例：排序中「A[0..i-1] 已排好序」）。

證三件事：

初始化：第一次迭代前，不變式成立。

保持：若某次迭代前成立，執行後（下次前）仍成立。

終止：迴圈結束時，不變式 + 終止條件 → 推出「演算法正確」。

實務上，即使不寫形式證明，「在腦中維持一條不變式」也能讓你迴圈寫得更對、更少邊界錯誤。

★ 真實例子：Go 標準函式庫的 sort.Search

Go 1.26.4 的 sort/search.go 把不變式直接寫在註解裡：
func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}
逐一對照三個步驟：

步驟這裡的證明
初始化 i=0、j=n。約定 f(-1)=false、f(n)=true，所以 f(i-1)=false、f(j)=true 成立
保持 !f(h) → 設 i=h+1，則 f(i-1)=f(h)=false ✓；f(h) → 設 j=h，則 f(j)=true ✓
終止每輪 j−i 至少縮小 1（因為 i ≤ h < j），所以一定會停；停時 i==j，不變式給出 f(i-1)=false 且 f(i)=true → i 就是第一個讓 f 為真的位置

這段程式碼寫得對的原因，就是每一行賦值都在維持不變式——註解 preserves f(i-1) == false 就是「保持」的證明。

順帶一提 uint(i+j) >> 1：寫成 (i+j)/2 在 i+j 超過 int 範圍時會溢位成負數。這是二分搜尋最有名的 bug——在各種語言的標準函式庫裡潛伏多年才被發現。

★ 用不變式決定邊界：半開區間的好處

二分搜尋的 off-by-one 錯誤，幾乎都來自「沒先想清楚不變式」。先選一種區間語義，再寫程式：

語義不變式迴圈條件縮小方式
半開 [i, j) 答案在 [i, j) 裡 i < j i = h+1 或 j = h
閉區間 [i, j] 答案在 [i, j] 裡 i <= j i = h+1 或 j = h-1

混用兩種語義就會出錯（例如用 [i, j) 的初值 j = n，卻用閉區間的 j = h-1）。Go 的 slice 表示法 s[i:j] 本身就是半開區間，所以在 Go 裡一律用半開最自然。

★ 插入排序：教科書的經典例子

《演算法導論》用插入排序介紹迴圈不變式：
for i := 1; i < len(a); i++ {
	// 不變式：a[0:i] 是原本 a[0:i] 的元素，且已排序
	key := a[i]
	j := i - 1
	for j >= 0 && a[j] > key {
		a[j+1] = a[j]
		j--
	}
	a[j+1] = key
}
初始化：i=1，a[0:1] 只有一個元素，當然有序。

保持：內層迴圈把比 key 大的元素右移一格，把 key 放進正確位置 → a[0:i+1] 有序。

終止：i = len(a)，不變式說 a[0:len(a)] 有序 → 整個陣列已排序。

★ 實務用法：把不變式變成斷言

寫不出形式證明也沒關係，把不變式寫成測試時才檢查的斷言：
if debugInvariants && !slices.IsSorted(a[:i]) {
	panic(fmt.Sprintf("invariant broken at i=%d", i))
}
配合 fuzzing（go test -fuzz）跑大量隨機輸入，不變式一被破壞就會停在第一個出錯的迭代——比在最終結果上除錯快得多。

🧪 我實際套用的紀錄

2026-07-15：（待填）

⚠️ 注意

不變式要選「強到能推出正確性、又真的每輪都成立」的那條——太弱沒用、太強不成立。

🔗 相關工具

工具-遞迴式與主定理 —— 姊妹工具，一個證正確性，一個算複雜度，配成一組看演算法

工具-系統化除錯 —— 實務用途，迴圈出 off-by-one 時用不變式定位是哪一輪開始不成立

二分搜尋 —— 不變式最常被用到、也最常寫錯的演算法
工具-攤還分析
🎯 什麼情境該想到我

分工：append 的聚合法推導 → 堆疊與佇列；雜湊表 rehash 的攤還分析與「攤還 O(1) 不代表延遲穩定」→ 雜湊表；併查集的攤還 α(n) → 併查集。這張補三種方法的完整對照與 Go 真實的擴容公式。

當一個操作「偶爾很貴、多數很便宜」（如動態陣列滿了才擴容），你想算「一連串操作」的整體平均成本時。

⚙️ 怎麼用（三種方法擇一）

攤還分析算的是「一序列操作的總成本 ÷ 操作數」，而非單次最壞。

聚合法（Aggregate）：直接算 n 個操作的總成本，再除以 n。

記帳法（Accounting）：對便宜操作「多收費」存起來，用來支付未來昂貴操作。

位能法（Potential）：定義一個位能函數，把成本變化攤到整個序列。

經典例：動態陣列 push——雖然擴容那次是 O(n)，但攤還到每次 push 是 O(1)。

★ 同一題用三種方法算：動態陣列的 push

設定：容量滿了就加倍，搬移每個元素成本 1，寫入一個元素成本 1。

1. 聚合法——直接加總

插入 n 個元素，擴容發生在大小為 1, 2, 4, …, 不超過 n 時，搬移總量 $1 + 2 + 4 + \dots < 2 n$ 。加上 n 次寫入，總成本 $< 3 n$ ，平均每次 < 3 → O(1)。

2. 記帳法——每次多收錢存起來

每次 push 收 3 元：1 元付自己的寫入，2 元存在這個元素身上。容量 k 滿了要擴到 2k 時，上次擴容之後插入的 k/2 個元素身上各有 2 元、共 k 元，剛好付 k 個元素的搬移費——每個新元素付自己一份，再替前半段的一個舊元素付一份。存款永遠不會變成負的，所以每次攤還成本 3。

3. 位能法——定義一個「位能」

令 $Φ = 2 \cdot size - capacity$ （剛擴容後 size ≈ capacity/2，Φ ≈ 0；快滿時 Φ ≈ capacity）。

不擴容的 push：實際成本 1，Φ 增加 2 → 攤還成本 3。

擴容的 push（size = cap = k → 容量 2k）：實際成本 k+1（搬 k 個，寫 1 個），Φ 從 $2 k - k = k$ 變成 $2 (k + 1) - 2 k = 2$ ，變化 $2 - k$ → 攤還成本 $(k + 1) + (2 - k) = 3$ 。

三種方法得到同一個答案：3。聚合法最直觀；記帳法和位能法在操作種類很多（push、pop、還會縮小容量）時更好用，因為可以對每種操作分別算。

★ Go 的 append 其實不是單純加倍

Go 1.26.4 的 runtime/slice.go（nextslicecap）：

舊容量 < 256：加倍。

舊容量 ≥ 256：每一輪 newcap += (newcap + 3*256) >> 2，也就是約 1.25 倍再加 192，平滑地從 2 倍過渡到 1.25 倍。

最後還會向上取整到記憶體配置器的 size class，所以實際容量常比公式算出來的大一點。

成長率變成 1.25 倍，還是攤還 O(1) 嗎？是。 對任何固定比例 $r > 1$ 的幾何成長，搬移總量是

$n (1 + \frac{1}{r} + \frac{1}{r ^{2}} + \dots) = n \cdot \frac{r}{r - 1}$

$r = 2$ ：總搬移 ≤ 2n，每次攤還 ≤ 2 次搬移。

$r = 1.25$ ：總搬移 ≤ 5n，每次攤還 ≤ 5 次搬移——常數變大，但仍是 O(1)。

取捨：成長率越小，浪費的空間越少（大 slice 不會一次多拿一倍記憶體），但搬移次數越多。Go 選擇小 slice 用 2 倍（快）、大 slice 用 1.25 倍（省記憶體）。

實務推論：知道最終大小時，make([]T, 0, n) 預先配置可以把搬移降到 0——這不改變 Big-O，但省下的常數在熱路徑上很可觀。

★ 攤還 vs 平均 vs 最壞：三個不同的保證

保證了什麼靠什麼
最壞情況 每一次操作都不超過 X 無假設
攤還任何一連串 n 次操作的總成本不超過 n·X 無機率假設，對任何輸入序列都成立
平均（期望） 對隨機輸入，單次成本的期望值是 X 需要輸入分布或隨機化的假設（例：快速排序的期望 O(n log n)）

攤還是一個「總量」保證，不是「每次」保證：延遲敏感的系統（每個請求都要 < 1ms）不能只看攤還——那一次 O(n) 的擴容就會變成一次延遲尖峰。

🧪 我實際套用的紀錄

2026-07-15：（待填）

⚠️ 注意

攤還是「序列平均」不是「機率平均」——它保證的是總量上限，不靠輸入分布假設。

攤還分析的前提是「從空的狀態開始」：如果你拿到一個剛好快滿的資料結構，接下來的第一次操作就可能很貴。攤還保證的是整個序列，不是從序列中間取一段。

🔗 相關工具

工具-時間複雜度分析、工具-儲存引擎B-Tree與LSM-Tree（LSM compaction 的攤還成本）

工具-遞迴式與主定理
🎯 什麼情境該想到我

分工：主定理三種情況的精確條件（含 ε 與正則條件）、套用範例、Karatsuba 與 Strassen → 分治法。這張補主定理管不到的遞迴式——這些在實務和面試中出現得更頻繁。

當你有一個分治/遞迴演算法，想算它的時間複雜度（如「為什麼合併排序是 O(n log n)」）時。

⚙️ 怎麼用

寫出遞迴式：T(n) = a·T(n/b) + f(n)（拆成 a 個大小 n/b 的子問題，合併成本 f(n)）。

用主定理（Master Theorem）比較 f(n) 與 n^(log_b a)：

f(n) 較小 → T(n) = Θ(n^(log_b a))

兩者同量級 → T(n) = Θ(n^(log_b a)·log n)（如合併排序 a=2,b=2 → n log n）

f(n) 較大（且規則）→ T(n) = Θ(f(n))

主定理不適用時，用遞迴樹畫出來加總，或用代入法猜測並歸納證明。

★ 主定理管不到的：「減一」型遞迴式速查表

主定理只處理 T(n) = a·T(n/b) + f(n)（除以 b）。但很多遞迴是減掉常數：

遞迴式結果典型例子
$T (n) = T (n - 1) + O (1)$ $O (n)$ 遞迴走訪鏈結串列、遞迴求陣列總和
$T (n) = T (n - 1) + O (n)$ $O (n^{2})$ 選擇排序；快速排序的最壞情況（每次樞紐都選到極值）
$T (n) = 2 T (n - 1) + O (1)$ $O (2^{n})$ 河內塔；列舉所有子集
$T (n) = T (n - 1) + T (n - 2) + O (1)$ $O (φ^{n}) \approx O (1.61 8^{n})$ 沒有記憶化的 Fibonacci
$T (n) = n \cdot T (n - 1)$ $O (n!)$ 列舉所有排列

推導方法（展開法）：以 $T (n) = T (n - 1) + n$ 為例

$T (n) = n + (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n + 1 )}{2} = O (n^{2})$

★ 其他常見但不標準的遞迴式

遞迴式結果例子怎麼算
$T (n) = T (n /2) + O (n)$ $O (n)$ Quickselect 的期望情況（找第 k 小）遞迴樹： $n + n /2 + n /4 + \dots < 2 n$
$T (n) = T (n /3) + T (2 n /3) + O (n)$ $O (n lo g n)$ 不均勻切割遞迴樹：每層總和 ≤ n，最深 $lo g_{3/2} n$ 層
$T (n) = T (n) + O (1)$ $O (lo g lo g n)$ van Emde Boas 樹變數代換：令 $n = 2^{m}$
$T (n) = 2 T (n /2) + O (n lo g n)$ $O (n lo g^{2} n)$ 落在主定理 case 2 和 3 的縫隙遞迴樹：第 i 層成本 $n lo g (n / 2^{i})$ ，加總

★ 遞迴樹：萬用的手算法

主定理背不起來時，畫樹就好：

根：成本 f(n)。

每一層：有 $a^{i}$ 個節點，每個大小 $n / b^{i}$ ，這層總成本 $a^{i} \cdot f (n / b^{i})$ 。

層數： $lo g_{b} n$ 。

加總所有層。

判斷誰主導：每層成本往下遞增 → 葉子主導（case 1）；每層一樣 → 乘上層數得 $lo g n$ （case 2）；每層遞減 → 根主導（case 3）。主定理只是這個畫樹過程的結論。

★ 記憶化如何改變遞迴式

沒有記憶化的 Fibonacci 是 $T (n) = T (n - 1) + T (n - 2) + O (1)$ ，指數級。加上記憶化之後，每個子問題只算一次：總共 n 個不同的子問題，每個 O(1) → O(n)。

判斷規則：有記憶化時，複雜度 = （不同子問題的數量）×（每個子問題不含遞迴的成本）。這是分析動態規劃的標準方法（見動態規劃）。

★ 別忘了空間：遞迴深度就是堆疊用量

$T (n) = T (n - 1) + \dots$ 的遞迴深度是 n。Go 的 goroutine 堆疊會自動成長，但深度到百萬級會用掉大量記憶體；超過上限（64 位元系統預設 1 GB）時程式直接 fatal error。

$T (n) = 2 T (n /2) + \dots$ 的深度只有 log n，幾乎不會有堆疊問題。

深度可能很大的遞迴，改寫成迴圈加顯式的堆疊（見深度優先搜尋）。

🧪 我實際套用的紀錄

2026-07-15：（待填）

⚠️ 注意

主定理有適用前提（子問題等分、f(n) 行為規則）；不符時別硬套，改用遞迴樹。

🔗 相關工具

工具-時間複雜度分析 —— 上位工具，主定理是它在遞迴演算法上的專用解法

工具-演算法設計策略 —— 使用場合，凡是走分治路線的設計都要靠遞迴式算出代價

工具-迴圈不變式 —— 姊妹工具，一個算成本，一個證正確，兩者一起才算把演算法看完

🔢 排序 Sorting

（6 條）
🧱 資料結構 Data Structures

（7 條）
🔍 搜尋與選擇 Searching

（2 條）
🧩 設計範式 Paradigms

（3 條）
🕸 圖論 Graph

（9 條）
🔤 字串 String

（1 條）
🧮 計算理論 Theory

（2 條）

[[插入排序|插入排序 Insertion Sort]]

[[合併排序|合併排序 Merge Sort]]

[[堆積排序|堆積排序 Heapsort]]

[[快速排序|快速排序 Quicksort]]

[[計數排序|計數排序 Counting Sort]]

[[基數排序|基數排序 Radix Sort]]

[[堆疊與佇列|堆疊與佇列 Stack and Queue]]

[[鏈結串列|鏈結串列 Linked List]]

[[雜湊表|雜湊表 Hash Table]]

[[二元搜尋樹|二元搜尋樹 Binary Search Tree]]

[[紅黑樹|紅黑樹 Red-Black Tree]]

[[二元堆積|二元堆積 Binary Heap]]

[[併查集|併查集 Union-Find]]

[[二分搜尋|二分搜尋 Binary Search]]

[[順序統計量與中位數|順序統計量與中位數 Order Statistics]]

[[分治法|分治法 Divide and Conquer]]

[[動態規劃|動態規劃 Dynamic Programming]]

[[貪婪演算法|貪婪演算法 Greedy]]

[[廣度優先搜尋|廣度優先搜尋 BFS]]

[[深度優先搜尋|深度優先搜尋 DFS]]

[[拓撲排序|拓撲排序 Topological Sort]]

[[Kruskal 最小生成樹]]

[[Prim 最小生成樹]]

[[Dijkstra 最短路徑]]

[[Bellman-Ford 最短路徑]]

[[Floyd-Warshall 全對最短路]]

[[最大流|最大流 Max Flow]]

[[KMP 字串比對]]

[[NP 完備性|NP 完備性 NP-Completeness]]

[[近似演算法|近似演算法 Approximation]]
Link to original

步驟	這裡的證明
初始化	i=0、j=n。約定 f(-1)=false、f(n)=true，所以 f(i-1)=false、f(j)=true 成立
保持	`!f(h)` → 設 i=h+1，則 f(i-1)=f(h)=false ✓；`f(h)` → 設 j=h，則 f(j)=true ✓
終止	每輪 j−i 至少縮小 1（因為 i ≤ h < j），所以一定會停；停時 i==j，不變式給出 f(i-1)=false 且 f(i)=true → i 就是第一個讓 f 為真的位置

語義	不變式	迴圈條件	縮小方式
半開 `[i, j)`	答案在 `[i, j)` 裡	`i < j`	`i = h+1` 或 `j = h`
閉區間 `[i, j]`	答案在 `[i, j]` 裡	`i <= j`	`i = h+1` 或 `j = h-1`

	保證了什麼	靠什麼
最壞情況	每一次操作都不超過 X	無假設
攤還	任何一連串 n 次操作的總成本不超過 n·X	無機率假設，對任何輸入序列都成立
平均（期望）	對隨機輸入，單次成本的期望值是 X	需要輸入分布或隨機化的假設（例：快速排序的期望 O(n log n)）

遞迴式	結果	典型例子
$T (n) = T (n - 1) + O (1)$	$O (n)$	遞迴走訪鏈結串列、遞迴求陣列總和
$T (n) = T (n - 1) + O (n)$	$O (n^{2})$	選擇排序；快速排序的最壞情況（每次樞紐都選到極值）
$T (n) = 2 T (n - 1) + O (1)$	$O (2^{n})$	河內塔；列舉所有子集
$T (n) = T (n - 1) + T (n - 2) + O (1)$	$O (φ^{n}) \approx O (1.61 8^{n})$	沒有記憶化的 Fibonacci
$T (n) = n \cdot T (n - 1)$	$O (n!)$	列舉所有排列

遞迴式	結果	例子	怎麼算
$T (n) = T (n /2) + O (n)$	$O (n)$	Quickselect 的期望情況（找第 k 小）	遞迴樹： $n + n /2 + n /4 + \dots < 2 n$
$T (n) = T (n /3) + T (2 n /3) + O (n)$	$O (n lo g n)$	不均勻切割	遞迴樹：每層總和 ≤ n，最深 $lo g_{3/2} n$ 層
$T (n) = T (n) + O (1)$	$O (lo g lo g n)$	van Emde Boas 樹	變數代換：令 $n = 2^{m}$
$T (n) = 2 T (n /2) + O (n lo g n)$	$O (n lo g^{2} n)$	落在主定理 case 2 和 3 的縫隙	遞迴樹：第 i 層成本 $n lo g (n / 2^{i})$ ，加總

🧰 這本書給我的工具（即用分析方法）

工具-迴圈不變式 — 想嚴謹驗證演算法「一定正確」時
工具-攤還分析 — 分析「一連串操作」的整體成本時
工具-遞迴式與主定理 — 分析分治演算法的複雜度時

📖 演算法型錄（詳解在 reference/）

🔢 排序 Sorting

插入排序 Insertion Sort、合併排序 Merge Sort、堆積排序 Heapsort、快速排序 Quicksort、計數排序 Counting Sort、基數排序 Radix Sort

🧱 資料結構 Data Structures

堆疊與佇列 Stack and Queue、鏈結串列 Linked List、雜湊表 Hash Table、二元搜尋樹 Binary Search Tree、紅黑樹 Red-Black Tree、二元堆積 Binary Heap、併查集 Union-Find

🔍 搜尋與選擇 Searching

二分搜尋 Binary Search、順序統計量與中位數 Order Statistics

🧩 設計範式 Paradigms

分治法 Divide and Conquer、動態規劃 Dynamic Programming、貪婪演算法 Greedy

🕸 圖論 Graph

廣度優先搜尋 BFS、深度優先搜尋 DFS、拓撲排序 Topological Sort、Kruskal 最小生成樹、Prim 最小生成樹、Dijkstra 最短路徑、Bellman-Ford 最短路徑、Floyd-Warshall 全對最短路、最大流 Max Flow

🔤 字串 String

KMP 字串比對

🧮 計算理論 Theory

NP 完備性 NP-Completeness、近似演算法 Approximation

✨ 關鍵重點（Layer 1–2）

正確性證明：用迴圈不變式（初始化、保持、終止）證明。
成本分析：最壞/平均/攤還；漸進符號 Θ、O、Ω 的嚴謹定義。
分治與遞迴式：用遞迴樹、代入法、主定理求解。
廣度：排序、堆積、雜湊、平衡樹、圖演算法（BFS/DFS/最短路/MST）、DP、貪婪、NP 完全。

💬 金句原文（Layer 0）

「一個演算法若正確，對每個輸入實例都必須以正確輸出停止。」

🔗 相關

直覺入門版見演算法圖解；面試應用見劍指offer

Quartz 5

Explorer

演算法導論 Introduction to Algorithms (CLRS)

📌 30 秒摘要（Layer 3）

🗺 心智圖（Canvas）

演算法導論

📗 演算法導論

🔬 即用分析工具

🎯 什麼情境該想到我

⚙️ 怎麼用（找出並驗證一條在迴圈中恆成立的性質）

★ 真實例子：Go 標準函式庫的 sort.Search

★ 用不變式決定邊界：半開區間的好處

★ 插入排序：教科書的經典例子

★ 實務用法：把不變式變成斷言

🧪 我實際套用的紀錄

⚠️ 注意

🔗 相關工具

🎯 什麼情境該想到我

⚙️ 怎麼用（三種方法擇一）

★ 同一題用三種方法算：動態陣列的 push

★ Go 的 append 其實不是單純加倍

★ 攤還 vs 平均 vs 最壞：三個不同的保證

🧪 我實際套用的紀錄

⚠️ 注意

🔗 相關工具

🎯 什麼情境該想到我

⚙️ 怎麼用

★ 主定理管不到的：「減一」型遞迴式速查表

★ 其他常見但不標準的遞迴式

★ 遞迴樹：萬用的手算法

★ 記憶化如何改變遞迴式

★ 別忘了空間：遞迴深度就是堆疊用量

🧪 我實際套用的紀錄

⚠️ 注意

🔗 相關工具

🔢 排序 Sorting

🧱 資料結構 Data Structures

🔍 搜尋與選擇 Searching

🧩 設計範式 Paradigms

🕸 圖論 Graph

🔤 字串 String

🧮 計算理論 Theory

🧰 這本書給我的工具（即用分析方法）

📖 演算法型錄（詳解在 reference/）

✨ 關鍵重點（Layer 1–2）

💬 金句原文（Layer 0）

🔗 相關

Graph View

Table of Contents

Backlinks

★ 真實例子：Go 標準函式庫的 `sort.Search`

★ Go 的 `append` 其實不是單純加倍