演算法導論 Introduction to Algorithms (CLRS)

📌 30 秒摘要（Layer 3）

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

🗺 心智圖（Canvas）

演算法導論

📗 演算法導論

Introduction to Algorithms (CLRS)

🔬 即用分析工具

工具-迴圈不變式

🎯 什麼情境該想到我

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

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

1. 找不變式：一句在「每次迭代開始前都成立」的陳述（例：排序中「A[0..i-1] 已排好序」）。
2. 證三件事：
   • 初始化：第一次迭代前，不變式成立。
   • 保持：若某次迭代前成立，執行後（下次前）仍成立。
   • 終止：迴圈結束時，不變式 + 終止條件 → 推出「演算法正確」。

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

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

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

🔗 相關工具

• 工具-遞迴式與主定理 —— 姊妹工具，一個證正確性，一個算複雜度，配成一組看演算法
• 工具-系統化除錯 —— 實務用途，迴圈出 off-by-one 時用不變式定位是哪一輪開始不成立

工具-攤還分析

🎯 什麼情境該想到我

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

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

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

1. 聚合法（Aggregate）：直接算 n 個操作的總成本，再除以 n。
2. 記帳法（Accounting）：對便宜操作「多收費」存起來，用來支付未來昂貴操作。
3. 位能法（Potential）：定義一個位能函數，把成本變化攤到整個序列。

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

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

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

🔗 相關工具

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

工具-遞迴式與主定理

🎯 什麼情境該想到我

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

⚙️ 怎麼用

1. 寫出遞迴式：T(n) = a·T(n/b) + f(n)（拆成 a 個大小 n/b 的子問題，合併成本 f(n)）。
2. 用主定理（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))
3. 主定理不適用時，用遞迴樹畫出來加總，或用代入法猜測並歸納證明。

🧪 我實際套用的紀錄

• 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

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

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

📖 演算法型錄（詳解在 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