資料結構關係全景圖¶
你學到了什麼？¶
從「CloudNet 路由引擎開發者」的視角，你已經走過了一趟完整的資料結構與演算法之旅：
┌─────────────────────────────────────────────────────────────────────┐
│ CloudNet 路由引擎 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ 基礎路由 │ │ 優先處理 │ │ 路徑規劃 │ │
│ │ │ │ │ │ │ │
│ │ Q1 Hash │ │ Q3 Heap │ │ Q5 Dijkstra │ │
│ │ Q2 Stack │ │ Q4 BST/AVL │ │ Q6 MST │ │
│ │ Queue │ │ │ │ Q7 Max Flow │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │
│ ┌──────────────┐ ┌──────────────┐ │
│ │ 系統最佳化 │ │ 效能調校 │ │
│ │ │ │ │ │
│ │ Q8 拓撲排序 │ │ Q10 排序 │ │
│ │ Q9 DP │ │ │ │
│ └──────────────┘ └──────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────┘
資料結構關係圖¶
┌─────────────┐
│ Array │
└──────┬──────┘
│
┌─────────────────┼─────────────────┐
│ │ │
▼ ▼ ▼
┌───────────┐ ┌───────────┐ ┌───────────┐
│ Stack │ │ Queue │ │ Heap │
│ (LIFO) │ │ (FIFO) │ │ (Priority)│
└─────┬─────┘ └─────┬─────┘ └─────┬─────┘
│ │ │
└────────┬───────┘ │
▼ │
┌───────────┐ │
│ Deque │ │
│ (雙端佇列) │ │
└───────────┘ │
│
┌──────────────────────┘
▼
┌───────────┐
│ Tree │
└─────┬─────┘
│
┌──────────────┼──────────────┐
│ │ │
▼ ▼ ▼
┌───────┐ ┌───────────┐ ┌───────┐
│ BST │ │ AVL/RBT │ │B-Tree │
│ │ │ (平衡樹) │ │(磁碟) │
└───────┘ └───────────┘ └───────┘
┌─────────────┐
│ Hash Table │
│ (O(1) 查詢) │
└─────────────┘
┌─────────────┐
│ Graph │
└──────┬──────┘
│
┌───────────┼───────────┐
│ │ │
▼ ▼ ▼
┌───────┐ ┌───────┐ ┌───────┐
│Dijkstra│ │ MST │ │Max Flow│
│BFS/DFS │ │Kruskal│ │Min Cut│
│ │ │ Prim │ │ │
└───────┘ └───────┘ └───────┘
時間複雜度速查表¶
資料結構操作¶
| 結構 | 查詢 | 插入 | 刪除 | 備註 |
|---|---|---|---|---|
| Array | \(O(1)\) | \(O(n)\) | \(O(n)\) | 隨機存取 |
| Linked List | \(O(n)\) | \(O(1)\) | \(O(1)\) | 已知位置 |
| Stack | \(O(n)\) | \(O(1)\) | \(O(1)\) | LIFO |
| Queue | \(O(n)\) | \(O(1)\) | \(O(1)\) | FIFO |
| Hash Table | \(O(1)\) avg | \(O(1)\) avg | \(O(1)\) avg | 雜湊 |
| BST | \(O(h)\) | \(O(h)\) | \(O(h)\) | \(h\) 可能 \(= n\) |
| AVL/RBT | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | 平衡 |
| Heap | \(O(1)\) max | \(O(\log n)\) | \(O(\log n)\) | 優先佇列 |
圖論演算法¶
| 演算法 | 時間複雜度 | 空間 | 用途 |
|---|---|---|---|
| BFS/DFS | \(O(V+E)\) | \(O(V)\) | 遍歷 |
| Dijkstra | \(O((V+E)\log V)\) | \(O(V)\) | 單源最短（非負） |
| Bellman-Ford | \(O(VE)\) | \(O(V)\) | 單源最短（允許負） |
| Floyd-Warshall | \(O(V^3)\) | \(O(V^2)\) | 全對最短 |
| Kruskal | \(O(E \log E)\) | \(O(V)\) | MST |
| Prim | \(O(E \log V)\) | \(O(V)\) | MST |
| 拓撲排序 | \(O(V+E)\) | \(O(V)\) | DAG 順序 |
| Edmonds-Karp | \(O(VE^2)\) | \(O(V^2)\) | 最大流 |
排序演算法¶
| 演算法 | 最佳 | 平均 | 最壞 | 穩定 |
|---|---|---|---|---|
| Quick Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n^2)\) | ✗ |
| Merge Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | ✓ |
| Heap Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | ✗ |
| Counting Sort | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | ✓ |
問題 → 工具 對照表¶
| 我遇到的問題 | 我需要的工具 | 本專題題號 |
|---|---|---|
| 快速查詢 key-value | Hash Table | Q1 |
| 先進先出處理 | Queue | Q2 |
| 後進先出處理 | Stack | Q2 |
| 找最大/最小 | Heap | Q3 |
| 範圍查詢 | BST / 平衡樹 | Q4 |
| A 到 B 最短路徑 | Dijkstra | Q5 |
| 最小成本連通 | MST (Kruskal/Prim) | Q6 |
| 最大流量 | Max Flow | Q7 |
| 有依賴的順序 | 拓撲排序 | Q8 |
| 最佳化決策 | Dynamic Programming | Q9 |
| 大量資料排序 | Quick/Merge Sort | Q10 |
學習路線建議¶
如果你是初學者¶
如果你要準備考試¶
如果你想深入研究¶
考試重點提醒¶
必考主題（幾乎每年出現）¶
- Hash Table 碰撞處理
- Heap 操作（Build-Heap 時間證明）
- BST / AVL 旋轉
- Dijkstra 正確性
- MST 性質
- 排序穩定性
常考主題（經常出現）¶
- Stack 排列數（Catalan Number）
- Bellman-Ford 與負環
- 拓撲排序
- 0/1 背包
- LCS
進階主題（偶爾出現）¶
- Red-Black Tree 性質
- Universal Hashing
- Max Flow / Min Cut
- 矩陣鏈乘法
回顧：從問題到工具¶
這個專題的設計理念是：
不是「先學資料結構，再找應用」，而是「遇到問題 → 需要什麼工具 → 引入資料結構」
希望你在走完這趟旅程後，不只是記住了公式和複雜度，更理解了**為什麼需要這些工具**。
當你未來遇到新問題時，能夠：
- 分析問題的特性（需要什麼操作？有什麼限制？）
- 選擇適合的資料結構（查詢多？插入多？有序？）
- 設計高效的演算法（貪心？DP？分治？）
這才是資料結構與演算法的真正價值。
祝你學習順利！