3-SAT 完整教材:回溯與 DPLL
史上第一個被證明 NP-Complete 的問題:給一堆「三選一」的條件,找出讓全部條件成立的真假指派
阅读文章 →0/1 背包問題完整教材
容量有限、每件物品拿或不拿:NP-Hard 卻有偽多項式解法的代表作
阅读文章 →Subset Sum 與 Partition 完整教材
初始 reach[0]= 真。每加入一個數 a_i,把所有可達的 s 推進到 s+a_i(一維陣列需由大到小掃,避免同一數字用兩次)。時間 O(nT)、空間 O(T)。
阅读文章 →N-Queens 完整教材:回溯法入門
回溯法的「Hello World」:學會在死路上及早回頭,一輩子受用
阅读文章 →Graph Coloring 完整教材
相鄰的點不能同色,最少要幾種顏色?從排課到暫存器分配都是它
阅读文章 →Vertex Cover 完整教材
用最少的守衛看住所有走廊:FPT 分支與「保證不超過兩倍」的近似法的最佳教室
阅读文章 →Independent Set 與 Clique 完整教材
「彼此都不認識的最大群體」與「彼此都認識的最大群體」——在補圖裡它們是同一個問題
阅读文章 →Hamiltonian Path 完整教材
每個點恰好經過一次:用位元把「走過哪些點」壓成一個整數,n! 變 2^n
阅读文章 →TSP 完整教材:Held-Karp 與最近鄰啟發式
最著名的 NP-Hard 問題:精確解的極限在哪、啟發式又能多接近最優
阅读文章 →Set Cover 完整教材:貪心近似
用最少的集合蓋住全部元素:貪心法的近似保證與它「已是最優」的驚人事實
阅读文章 →Bin Packing 完整教材:First Fit Decreasing
固定容量的箱子最少用幾個:從搬家打包到雲端 VM 調度,以及「先放大件」的智慧
阅读文章 →Job Scheduling 完整教材:列表排程近似
n 個工作分給 m 台機器、最晚完工時間最短:近似演算法理論的誕生地(Graham 1966)
阅读文章 →遺傳演算法完整教材
把「物競天擇」寫成程式:不懂問題結構也能逼近好解的通用武器,本篇以 TSP 與背包實戰
阅读文章 →模擬退火演算法完整教材
最佳化也一樣。「只往下走」的爬山法就是淬火——快,但凍在第一個遇到的谷底。模擬退火則給演算法一個「溫度」:高溫時容忍往上爬(走出谷底),然後慢慢降溫,讓它最終安定在最深的那個谷。
阅读文章 →蒙地卡羅方法完整教材
在演算法理論中,「蒙地卡羅演算法」有更狹義的意思——使用隨機性、執行時間有界、但答案可能錯的演算法。它的對照組是 Las Vegas 演算法:答案一定對、但執行時間是隨機變數(例如隨機化快速排序)。
阅读文章 →NP、NP-Complete 與 NP-Hard 完整白話教材
寫程式的人遲早會撞到一種牆:問題明明「聽起來很簡單」,程式卻怎麼寫都跑不完。 例如「把 40 個包裹分給兩台車,讓兩台車的重量儘量平均」——聽起來像小學數學, 但暴力枚舉有 2^40 10^12 種分法;再快的電腦,指數成長都能讓它跪下。
阅读文章 →演算法教材地圖 — 學習順序與涵蓋範圍
本篇是索引,不是另一套演算法。它把資料夾裡的教學文件對上三份公開課綱裡會出現、而本站原先沒有獨立筆記的主題,並給出一條讀的順序。已有長篇的圖論、NP、KMP、模糊搜尋、模擬退火與蒙地卡羅不在這次重寫之列,只標出它們該在什麼時候讀。
阅读文章 →攤還分析(Amortized Analysis)— 方法論完整教材
並查集與伸展樹各自證明了「單次可以很慢,一串操作仍然很快」。那兩篇把位能算在特定結構上。本篇把三種通用算法寫清楚:聚集法、記帳法、位能法,並用二元計數器與動態陣列當可以手算的例子。之後再回去看並查集與伸展樹,會知道它們只是位能函數不同。
阅读文章 →B 樹與 B+ 樹(B-Tree / B+ Tree)— 完整教材
平衡 BST 教材把 B 樹列成「磁碟用的多路樹」,但沒有一次插入分裂的推演。記憶體內的紅黑樹每個節點只有一個鍵,磁碟一次讀寫卻是一整頁。B 樹讓一個節點裝滿一頁,樹高跟著頁數的對數走,而不是鍵數的對數乘上一個很大的常數。
阅读文章 →Balanced Binary Search Tree — AVL Tree、Red-Black Tree、由遍歷重建樹
Part I — AVL Tree AVL Tree 定義與性質 Balance Factor 與高度 AVL 的四種旋轉 AVL 插入 AVL 刪除 AVL 完整範例推演
阅读文章 →銀行系統前後端完整教學 — 架構、流程、API、安全與交易一致性
本教材從工程角度介紹一個現代銀行系統如何設計前端、後端、資料庫、交易流程、安全控管與 API。 > 內容適合作為系統設計、金融科技後端、全端開發與面試準備教材。 > > 注意:真實銀行系統會受到法規、內控、資安稽核與核心銀行主機限制,本教材以教學用架構為主,不構成金融或法遵建議。
阅读文章 →二元搜尋(Binary Search)— 完整教材
分析教材與遞迴教材都把二元搜尋當成 (O(log n)) 的例子,但沒有處理邊界、lower_bound / upper_bound,也沒有「對答案二分」——後者在課程與實作裡比在陣列裡找一個數更常出現。本篇把迴圈不變量寫死,避免 off-by-one。
阅读文章 →Disjoint Set(並查集 / Union-Find)演算法完整教學
Disjoint Set(不相交集合),又稱 Union-Find 或 並查集,是一種維護「互不相交集合的動態分組(partition)」的資料結構。
阅读文章 →分治法與主定理(Divide and Conquer / Master Theorem)— 完整教材
分析教材用最大子段和展示了一次分治,遞迴教材列出了合併排序與快速排序,但沒有把「遞迴式怎麼解」收成可以套用的定理。本篇補上替換法的一個完整例子、遞迴樹的直覺,以及主定理的三個標準情況。
阅读文章 →