考前 30 分鐘
速翻表
考試前 30 分鐘掃一遍。不會有新東西，全部都是前面章節的重點摘要。
📊 Big-O 順序
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
看到「砍一半」想 log n；看到雙層 for 想 n²；看到指數想 DP 救援。
🎯 排序演算法總表
| 演算法 | 最壞 | 平均 | 最好 | 空間 | 穩定 | 套路 |
|---|---|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(n) | O(1) | ✓ | 兩兩比，大的右擠 |
| Insertion | O(n²) | O(n²) | O(n) | O(1) | ✓ | 新牌往左塞 |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ✗ | 挑最小放前面 |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ | 切半、各排、合併 |
| Quick | O(n²) | O(n log n) | O(n log n) | O(log n) | ✗ | 挑 pivot，左小右大 |
🗂 資料結構速查
| 結構 | 查詢 | 插入 | 刪除 | 特性 |
|---|---|---|---|---|
| 陣列 | O(n) | O(n) | O(n) | 隨機存取 O(1)、cache 友善 |
| 鏈結串列 | O(n) | O(1)* | O(1)* | 頭尾操作快、隨機存取慢 |
| Stack | — | O(1) | O(1) | 後進先出 (LIFO) |
| Queue | — | O(1) | O(1) | 先進先出 (FIFO) |
| BST 平衡 | O(log n) | O(log n) | O(log n) | 中序走訪 = 排序 |
| 雜湊表 | O(1) | O(1) | O(1) | 最壞 O(n)、不能排序 |
| Heap | O(1) 頂 | O(log n) | O(log n) | 優先佇列、最大/最小一定在頂 |
🌐 圖演算法速查
BFS（廣度優先）
- 用 Queue
- O(V + E)
- 無權重圖找最短路
- 一層層擴散
DFS（深度優先）
- 用 Stack 或遞迴
- O(V + E)
- 偵測環、拓撲排序
- 鑽到底再回來
Dijkstra
- 用 Priority Queue (min-heap)
- O((V + E) log V)
- 非負權重最短路
- 不能有負邊
圖的表示
- 鄰接矩陣：O(V²) 空間，稠密適合
- 鄰接串列：O(V+E) 空間，稀疏適合
- 握手定理：度數總和 = 2E
🎲 解題套路口訣
最佳化問題 + 子問題重複 → DP 寫狀態方程
每步選當下最好 → Greedy（要驗證貪婪選擇性質）
能切一半各自處理再合 → 分治（Merge Sort、Quick Sort、二分搜尋）
無權重最短路 → BFS
非負權重最短路 → Dijkstra
「有沒有出現過」/「對應到什麼」 → 雜湊表 O(1)
📝 紙筆考試 5 大訣竅
- 畫表格追蹤：排序、DP、Dijkstra 一律畫表格，每輪一行。
- 寫複雜度別忘 O()：寫 n² 沒寫 O(n²) 會被扣。
- 畫遞迴樹：費氏、階乘、Merge Sort 都常考遞迴樹。
- 沒把握也要寫思路：部分分數比 0 分好。
- 看清楚問哪種情況：最壞 vs 平均 vs 最好。
🎓
深呼吸。你準備好了。
考完回來告訴自己一聲「我會了」。