演算法關係全景圖¶
SearchX 工程師的成長之路¶
SearchX 搜尋引擎系統
│
┌───────────────────────┼───────────────────────┐
▼ ▼ ▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│ 爬蟲 │ │ 索引 │ │ 搜尋 │
│ Crawler │ │ Indexer │ │ Search │
└────┬────┘ └────┬────┘ └────┬────┘
│ │ │
▼ ▼ ▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│重複偵測 │ │壓縮儲存 │ │字串匹配 │
│Q2 Rabin │ │Q4 Huffman│ │ Q1 KMP │
└─────────┘ └─────────┘ └─────────┘
│ │ │
└──────────────────────┼──────────────────────┘
│
┌────────────────┼────────────────┐
▼ ▼ ▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│分治處理 │ │動態更新 │ │查詢優化 │
│Q3 Master│ │Q5 平攤 │ │Q6-8 NP │
└─────────┘ └─────────┘ └─────────┘
演算法技術全景圖¶
字串演算法家族¶
字串匹配問題
│
┌───────────┼───────────┐
▼ ▼ ▼
┌───────┐ ┌───────┐ ┌───────┐
│暴力法 │ │ KMP │ │ Rabin │
│O(nm) │ │O(n+m) │ │ -Karp │
└───────┘ └───┬───┘ └───┬───┘
│ │
Prefix Rolling
Function Hash
│ │
└─────┬─────┘
▼
有限狀態自動機
演算法設計技巧¶
演算法設計
│
┌─────────────┼─────────────┐
▼ ▼ ▼
┌───────┐ ┌───────┐ ┌───────┐
│分治法 │ │貪心法 │ │ 動態 │
│Divide │ │Greedy │ │規劃DP │
└───┬───┘ └───┬───┘ └───┬───┘
│ │ │
▼ ▼ ▼
Master Exchange 狀態轉移
Theorem Argument 方程
│ │ │
▼ ▼ ▼
Merge K Huffman 背包、LCS
Lists Coding （見資料結構專題）
複雜度理論¶
計算複雜度
│
┌───────────────┼───────────────┐
▼ ▼ ▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│ P │ │ NP │ │ NP-Hard │
│可解問題 │ │可驗證 │ │ 至少和 │
└────┬────┘ └────┬────┘ │ NP 一樣 │
│ │ │ 難 │
│ ▼ └────┬────┘
│ ┌─────────┐ │
│ │ NPC │◄─────────┘
│ │NP∩NP-Hard│
│ └────┬────┘
│ │
└────────────┼────────────────┐
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│歸約證明 │ │近似演算 │
│Reduction│ │Algorithm│
└─────────┘ └─────────┘
考點對照表¶
按年度分布¶
| 年度 | 字串 | 分治 | 貪心 | 平攤 | NP |
|---|---|---|---|---|---|
| 114 | Q16 KMP | - | - | Q18 Binary Counter | Q17, Q19 |
| 113 | - | - | - | Q3 Dynamic Array | Q13 Vertex Cover |
| 112 | Q16 Prefix | Q15 Merge K | Q3 Huffman | - | - |
| 110 | Q10,11 KMP | - | - | - | Q12 NPC |
| 109 | - | - | - | - | Q15 Reduction |
| 107 | - | - | Q5 Activity | Q? | - |
按主題分類¶
| 主題 | 核心概念 | 經典題型 | 難度 |
|---|---|---|---|
| KMP | Prefix Function | 計算失敗函數、DFA | ★★★ |
| Rabin-Karp | Rolling Hash | 多模式匹配 | ★★☆ |
| 分治法 | Master Theorem | Merge K Lists | ★★★ |
| 貪心法 | Exchange Argument | Huffman, Activity | ★★★ |
| 平攤分析 | Potential Method | Dynamic Array, Counter | ★★★★ |
| NP 基礎 | P/NP/NPC 定義 | 類別關係推理 | ★★★ |
| NP 證明 | Reduction | 3-SAT → 各種問題 | ★★★★ |
| 近似 | 近似比 | Vertex Cover, Set Cover | ★★★★ |
時間複雜度速查表¶
字串演算法¶
| 演算法 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| 暴力匹配 | \(O(nm)\) | \(O(1)\) |
| KMP | \(O(n+m)\) | \(O(m)\) |
| Rabin-Karp | \(O(n+m)\) 期望 | \(O(m)\) |
| 多模式 Rabin-Karp | \(O(n \cdot k + m)\) | \(O(m)\) |
分治法經典問題¶
| 問題 | 遞迴式 | 時間複雜度 |
|---|---|---|
| Merge Sort | \(T(n) = 2T(n/2) + O(n)\) | \(O(n \log n)\) |
| Quick Sort | \(T(n) = 2T(n/2) + O(n)\) | \(O(n \log n)\) 期望 |
| Merge K Lists | \(T(k) = 2T(k/2) + O(kn)\) | \(O(kn \log k)\) |
| Closest Pair | \(T(n) = 2T(n/2) + O(n)\) | \(O(n \log n)\) |
貪心與近似¶
| 問題 | 時間複雜度 | 近似比 |
|---|---|---|
| Huffman Coding | \(O(n \log n)\) | 最佳 |
| Activity Selection | \(O(n \log n)\) | 最佳 |
| Vertex Cover | \(O(E)\) | 2 |
| Set Cover | \(O(mn)\) | \(O(\ln n)\) |
公式速查表¶
Master Theorem¶
\[T(n) = aT(n/b) + f(n)\]
設 \(c = \log_b a\)：
| Case | 條件 | 結果 |
|---|---|---|
| 1 | \(f(n) = O(n^{c-\epsilon})\) | \(T(n) = \Theta(n^c)\) |
| 2 | \(f(n) = \Theta(n^c \log^k n)\) | \(T(n) = \Theta(n^c \log^{k+1} n)\) |
| 3 | \(f(n) = \Omega(n^{c+\epsilon})\) | \(T(n) = \Theta(f(n))\) |
KMP Prefix Function¶
\[\pi[i] = \max\{k : P[0..k-1] = P[i-k+1..i]\}\]
Huffman 平均編碼長度¶
\[L = \sum_{i} f_i \cdot d_i\]
其中 \(f_i\) 是頻率，\(d_i\) 是深度。
平攤分析（Potential Method）¶
\[\hat{c}_i = c_i + \Phi_{i} - \Phi_{i-1}\]
\[\sum \hat{c}_i = \sum c_i + \Phi_n - \Phi_0\]
解題策略總結¶
遇到字串問題¶
字串匹配問題
│
▼
單一模式？───是───► KMP（O(n+m)）
│
否
▼
多模式？───是───► Rabin-Karp 或 Aho-Corasick
│
否
▼
近似匹配？───是───► DP（編輯距離）
遇到設計題¶
演算法設計
│
▼
可以分解成相同子問題？───是───► 分治法
│
否
▼
有最佳子結構 + 重疊子問題？───是───► DP
│
否
▼
每步都有明顯最佳選擇？───是───► 貪心
│ （記得證明！）
否
▼
回溯搜尋 / 其他技術
遇到複雜度問題¶
遇到 NP 問題¶
證明 NP-Complete
│
├─► Step 1: 在 NP 中
│ → 定義證據
│ → O(poly) 驗證
│
└─► Step 2: NP-Hard
→ 選適當來源問題
→ 設計 poly-time 轉換
→ 證明等價性
與資料結構專題的關係¶
| 主題 | 資料結構專題 | 演算法專題 |
|---|---|---|
| Hash Table | ✓ 完整 | ✗ |
| Heap | ✓ 完整 | ✗（Huffman 用到） |
| BST/AVL | ✓ 完整 | ✗ |
| 圖論 | ✓ Dijkstra, MST, Max Flow | ✗ |
| 字串 | ✗ | ✓ KMP, Rabin-Karp |
| 分治 | 部分（排序） | ✓ 完整設計技巧 |
| 貪心 | 部分（MST） | ✓ Huffman, 正確性證明 |
| DP | ✓ 背包、LCS | ✗ |
| NP | ✗ | ✓ 完整覆蓋 |
| 平攤 | 部分（Hash） | ✓ 完整方法 |
建議學習順序：
- 資料結構專題（基礎工具）
- 演算法專題（設計技巧）
- 兩者交互練習
考前檢查清單¶
字串演算法¶
- 能手算 KMP Prefix Function
- 理解 KMP 為什麼是 \(O(n+m)\)
- 能寫出 Rolling Hash 公式
分治法¶
- 能用 Master Theorem 三種情況
- 能分析 Merge K Sorted Lists
貪心法¶
- 能建 Huffman Tree 並計算平均長度
- 知道 Exchange Argument 怎麼用
平攤分析¶
- 能用 Aggregate 分析 Dynamic Array
- 能用 Potential 分析 Binary Counter
- 知道三種方法的關係
NP 完備性¶
- 能定義 P, NP, NP-Complete
- 能做 NPC 類別推理
- 知道經典歸約：3-SAT → Vertex Cover → Independent Set → Clique
近似演算法¶
- 能證明 Vertex Cover 2-近似
- 知道 Set Cover 是 \(O(\ln n)\) 近似