第五部分：效能調校¶
< 上一題：傳輸成本最小化 | 返回目錄 | 總結 >
場景：Log 分析要用什麼排序？¶
你要分析過去一個月的網路 log（數十億筆），找出流量最大的 top 100 連線。
資料量太大，不同排序演算法的效能差異會被放大。
「排序是基礎中的基礎，但選對演算法很重要。」
第 10 題：效能瓶頸分析 - 排序演算法選擇¶
(a) 排序演算法總覽¶
3 分 ・ 大二
你需要知道：常見排序演算法的比較
題目：
填完以下表格：
| 演算法 | 最佳 | 平均 | 最壞 | 空間 | 穩定 |
|---|---|---|---|---|---|
| Bubble Sort | ? | ? | ? | ? | ? |
| Selection Sort | ? | ? | ? | ? | ? |
| Insertion Sort | ? | ? | ? | ? | ? |
| Merge Sort | ? | ? | ? | ? | ? |
| Quick Sort | ? | ? | ? | ? | ? |
| Heap Sort | ? | ? | ? | ? | ? |
解答
| 演算法 | 最佳 | 平均 | 最壞 | 空間 | 穩定 |
|---|---|---|---|---|---|
| Bubble Sort | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ✓ |
| Selection Sort | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ✗ |
| Insertion Sort | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ✓ |
| Merge Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n)\) | ✓ |
| Quick Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n^2)\) | \(O(\log n)\) | ✗ |
| Heap Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(1)\) | ✗ |
穩定性：相等元素的相對順序是否保持。
(b) Quick Sort 深入分析¶
4 分 ・ 大三
你需要知道：Quick Sort 為什麼通常最快？什麼時候會最壞？
題目：
-
說明 Quick Sort 的步驟（Partition 過程）
-
什麼情況下會退化成 \(O(n^2)\)？如何避免？
-
實現 3-way Partition（處理大量重複元素）
解答
1. Quick Sort：
def quicksort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
2. 最壞情況：
每次 pivot 選到最大或最小 → 分割不平衡 → \(T(n) = T(n-1) + O(n) = O(n^2)\)
觸發條件： - 已排序的陣列 + 選第一個/最後一個當 pivot - 所有元素相同
避免方法： - Randomized Quick Sort：隨機選 pivot - Median-of-Three：取頭、中、尾的中位數
3. 3-way Partition（Dutch National Flag）：
處理大量重複元素時，把等於 pivot 的放中間。
def partition_3way(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # arr[lt..i-1] == pivot
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
return lt, gt # 返回等於 pivot 的區間
© 排序下界證明¶
4 分 ・ 碩一
你需要知道：為什麼比較排序不能比 \(O(n \log n)\) 更快？
題目：
證明：任何基於比較的排序演算法，最壞情況下需要 \(\Omega(n \log n)\) 次比較。
解答
決策樹模型：
- 每次比較是一個「是/否」決策
- 排序演算法可以表示成一棵決策樹
- 葉節點對應排列結果
葉節點數量：至少 \(n!\)（\(n\) 個元素的所有排列）
樹高 \(h\)：二元樹最多 \(2^h\) 個葉節點
用 Stirling 近似：\(n! \approx (n/e)^n\)
結論：比較排序最壞需要 \(\Omega(n \log n)\) 次比較。
(d) 非比較排序¶
3 分 ・ 大三
你需要知道：什麼時候可以突破 \(O(n \log n)\)？
題目：
-
說明 Counting Sort 的原理和限制
-
說明 Radix Sort 的原理
解答
1. Counting Sort：
條件：元素是整數，範圍 \([0, k]\)
def counting_sort(arr, k):
count = [0] * (k + 1)
for x in arr:
count[x] += 1
result = []
for i in range(k + 1):
result.extend([i] * count[i])
return result
時間：\(O(n + k)\)
限制：\(k\) 不能太大（否則空間爆炸）
2. Radix Sort：
想法：從最低位到最高位，對每一位做穩定排序（如 Counting Sort）。
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
時間：\(O(d(n + k))\)，\(d\) = 位數，\(k\) = 每位的範圍（通常 10）
適用：整數或固定長度字串
進階挑戰：External Sorting¶
3 分 ・ 碩一
你需要知道：資料太大放不進記憶體怎麼辦？
解答
External Merge Sort：
- 分割階段：把資料分成多個 chunk，每個 chunk 讀入記憶體排序，寫回磁碟
- 合併階段：用 k-way merge 合併所有 chunk
k-way merge： - 維護一個大小為 \(k\) 的 Min-Heap - 每次取出最小的，補入該 chunk 的下一個元素
I/O 複雜度：\(O(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B})\)
- \(N\) = 資料量
- \(M\) = 記憶體大小
- \(B\) = 磁碟 block 大小
實務：資料庫的排序、Hadoop MapReduce 的 shuffle 階段。
第 10 題小結：你的排序工具箱¶
「大量資料怎麼排序最快？」
│
├─► (a) 基本比較？
│ → Merge/Quick/Heap 都是 O(n log n)
│ → Quick 通常最快（cache friendly）
│
├─► (b) Quick Sort 細節？
│ → 隨機 pivot 避免最壞
│ → 3-way partition 處理重複
│
├─► (c) 能更快嗎？
│ → 比較排序下界 Ω(n log n)
│
├─► (d) 特殊情況？
│ → Counting Sort: O(n+k)
│ → Radix Sort: O(d(n+k))
│
└─► 進階：記憶體不夠？
→ External Merge Sort
| 場景 | 推薦 | 原因 |
|---|---|---|
| 通用排序 | Quick Sort | 平均最快，cache friendly |
| 保證最壞 | Merge/Heap Sort | \(O(n \log n)\) 保證 |
| 需要穩定 | Merge Sort | 穩定且高效 |
| 整數小範圍 | Counting Sort | \(O(n+k)\) |
| 大量資料 | External Sort | 磁碟 I/O 優化 |
< 上一題：傳輸成本最小化 | 返回目錄 | 總結 >