本篇是索引,不是另一套演算法。它把資料夾裡的教學文件對上三份公開課綱裡會出現、而本站原先沒有獨立筆記的主題,並給出一條讀的順序。已有長篇的圖論、NP、KMP、模糊搜尋、模擬退火與蒙地卡羅不在這次重寫之列,只標出它們該在什麼時候讀。
對照用的課綱(只取主題清單,不搬運內文):
- CLRS 第 4 版:分治、堆積、排序下界、順序統計、DP、貪心、攤還、B 樹、圖、字串、數論、NP。
- Princeton Algorithms(Sedgewick / Wayne):堆疊與佇列、優先佇列、字典樹、子字串搜尋、B 樹。
- 台大演算法實戰班與 NTUCPC Guide:前綴和、雙指標、二分答案、字典樹、基礎 DP、貪心、線段樹與樹狀陣列。
建議順序
1. 工具
| 順序 | 檔案 | 你要帶走的一句話 |
|---|---|---|
| 1 | Chapter2_Algorithm_Analysis_Teaching_Materials.md |
迴圈怎麼變成大 O |
| 2 | Divide_And_Conquer_Teaching_Materials.md |
主定理的三種情況 |
| 3 | Recursion_Teaching_Materials.md |
基底、進展、呼叫堆疊 |
| 4 | Amortized_Analysis_Teaching_Materials.md |
貴的那一次可以被一串便宜的操作補上 |
| 5 | Number_Theory_Algorithms_Teaching_Materials.md |
gcd、模反元素、快速冪 |
2. 線性結構與搜尋
| 順序 | 檔案 | 你要帶走的一句話 |
|---|---|---|
| 6 | Stack_Queue_Linked_List_Teaching_Materials.md |
堆疊與佇列是順序契約,不是某一種陣列寫法 |
| 7 | Prefix_Sum_Two_Pointers_Teaching_Materials.md |
靜態區間和、區間加值、正數滑動視窗 |
| 8 | Binary_Search_Teaching_Materials.md |
半開區間,以及對答案二分 |
| 9 | Sorting_Algorithms_Teaching_Materials.md |
穩定性、(\Omega(n\log n)) 下界、桶排序、選擇指南 |
| 10 | Order_Statistics_Quickselect_Teaching_Materials.md |
只要第 k 小,不必全排序 |
3. 樹、雜湊、區間
| 順序 | 檔案 | 你要帶走的一句話 |
|---|---|---|
| 11 | Tree_Teaching_Materials.md |
二元樹的形狀與走訪 |
| 12 | Heap_Priority_Queue_Teaching_Materials.md |
堆積序不是全序;建堆是線性 |
| 13 | Balanced_BST_Teaching_Materials.md |
AVL 與紅黑樹 |
| 14 | Splay_Tree_Teaching_Materials.md |
攤還平衡 |
| 15 | BTree_Teaching_Materials.md |
磁碟頁上的多路樹 |
| 16 | Hash/Hash_Algorithms_Teaching_Materials.md |
碰撞、負載因子、滾動雜湊 |
| 17 | Trie_Teaching_Materials.md |
前綴是一等公民 |
| 18 | Segment_Tree_Fenwick_Teaching_Materials.md |
會修改的區間和 |
| 19 | Disjoint_Set_Teaching_Materials.md |
近乎常數的合併與查詢 |
4. 方法,而不只是題目
| 順序 | 檔案 | 你要帶走的一句話 |
|---|---|---|
| 20 | Dynamic_Programming_Teaching_Materials.md |
狀態、轉移、基底、順序 |
| 21 | Greedy_Algorithms_Teaching_Materials.md |
交換論證;反例比程式先寫 |
| 22 | Graph_Algorithms_Complete_Teaching_Materials.tex |
BFS/DFS、最短路、MST、最大流 |
| 23 | KMP_Complete_Teaching_Materials.md |
失敗函數。另兩份 KMP 筆記是同一演算法的不同講法,讀完一份即可 |
| 24 | Fuzzy_Search_Complete_Teaching_Materials.md |
編輯距離與其索引 |
5. 難問題與隨機
| 順序 | 檔案 | 你要帶走的一句話 |
|---|---|---|
| 25 | Advanced/NP_Complete_Teaching_Materials.tex |
P、NP、歸約 |
| 26 | Advanced/01 到 13 與退火、蒙地卡羅 |
每一題的精確算法、近似或取樣。總覽在 NP 那篇 |
圖論筆記已經含括 Kruskal、Prim、Dijkstra、流量與二分匹配。貪心筆記只解釋它們為什麼算貪心,不重複證明。
這三輪補了什麼
對照上面的課綱,原先只有程式片段或只有一句話的主題,現在有獨立筆記:
| 主題 | 原先 | 現在 |
|---|---|---|
| 二元堆積與 decrease-key | 排序篇裡的堆積排序程式 | Heap_Priority_Queue_Teaching_Materials.md |
| DP 怎麼設計 | 散在背包、編輯距離、位元 DP | Dynamic_Programming_Teaching_Materials.md |
| 貪心的證明與反例 | 集合覆蓋近似、圖演算法各講各的 | Greedy_Algorithms_Teaching_Materials.md |
| 主定理 | 分析教材停在遞迴式出現 | Divide_And_Conquer_Teaching_Materials.md |
| 二分的邊界與二分答案 | 分析教材只有找到一個數 | Binary_Search_Teaching_Materials.md |
| 第 k 小 | 排序篇最後一行 | Order_Statistics_Quickselect_Teaching_Materials.md |
| 字典樹 | 模糊搜尋篇的一個小節 | Trie_Teaching_Materials.md |
| 攤還三種算法 | 並查集與伸展樹各自證明 | Amortized_Analysis_Teaching_Materials.md |
| 比較排序下界、穩定性、桶排序 | 排序表有穩定性欄,沒有論證 | 排序教材第 12–15 節 |
| 線段樹與樹狀陣列 | 無 | Segment_Tree_Fenwick_Teaching_Materials.md |
| B 樹分裂 | 樹教材表格的一行 | BTree_Teaching_Materials.md |
| 模反元素 | 只有 gcd 與快速冪的複雜度例子 | Number_Theory_Algorithms_Teaching_Materials.md |
| 前綴和、差分、雙指標 | 無獨立筆記 | Prefix_Sum_Two_Pointers_Teaching_Materials.md |
| 堆疊與佇列的契約 | 有 C++ 實作與 README | Stack_Queue_Linked_List_Teaching_Materials.md |
Python 進階裡原本缺的產生器與情境管理器協定,以及用 GIL 判斷三種並行的選法,寫在 Python/03_advanced_level/10_generators_context_managers_gil.md(並行本身的完整範例在同資料夾的 03_concurrency_parallelism.md)。Web、資料庫與機器學習仍以站上既有分類為準,不在演算法資料夾重寫。
故意沒有另開長篇的主題
這些在課綱邊緣,而且站上已有可用的材料,再寫一篇只會重複:
- 最大流、二分匹配、MST、最短路:圖論長篇已有定義、演算法與練習。
- KMP 的第三種講法:已有三份。新的字串結構是字典樹,不是再一份失敗函數。
- NP 各題的程式:
Advanced/每題一份,含手算與 C++。 - 模擬退火與蒙地卡羅:各自已是完整長篇,含實驗。
讀到圖論的「進階主題」仍覺得太快時,先回到本頁第 4 節的 DP 與貪心,不要從最大流開始。