第二部分：演算法設計技巧¶

< 上一題：Rabin-Karp | 返回目錄 | 下一題：貪心法 >

場景：合併多個爬蟲的結果¶

SearchX 有 \(k\) 台爬蟲伺服器，每台都回傳一個**已排序的網頁列表**。你需要把它們合併成一個大的排序列表。

最直覺的方法：把所有列表串起來，然後排序。但這浪費了「已排序」的性質。

「每個列表都已經排序好了，有沒有更聰明的合併方法？」

第 3 題：大規模資料處理 - 分治法設計¶

分治法（Divide and Conquer）是演算法設計的核心技巧：把大問題拆成小問題，遞迴解決，再合併結果。

(a) 分治法的三步驟¶

3 分 ・大二

你需要知道：分治法的基本框架是什麼？

題目：

說明分治法的三個步驟：Divide, Conquer, Combine
Merge Sort 如何體現這三個步驟？
寫出分治法的一般遞迴式

解答

1. 三步驟：

步驟	說明
Divide	把問題分成若干子問題
Conquer	遞迴解決子問題
Combine	把子問題的解合併成原問題的解

2. Merge Sort：

Divide：把陣列分成兩半
Conquer：遞迴排序左半和右半
Combine：合併兩個已排序陣列

3. 一般遞迴式：

\[T(n) = aT(n/b) + f(n)\]

\(a\)：子問題數量
\(n/b\)：子問題大小
\(f(n)\)：Divide + Combine 的成本

(b) Master Theorem¶

4 分 ・大三

你需要知道：如何快速分析分治演算法的時間複雜度？

題目：

陳述 Master Theorem 的三種情況
分析以下遞迴式的時間複雜度：
- \(T(n) = 2T(n/2) + n\)
- \(T(n) = 4T(n/2) + n\)
- \(T(n) = 2T(n/2) + n^2\)

解答

1. 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)\)
Case 2	\(f(n) = \Theta(n^c \log^k n)\)	\(T(n) = \Theta(n^c \log^{k+1} n)\)
Case 3	\(f(n) = \Omega(n^{c+\epsilon})\)	\(T(n) = \Theta(f(n))\)

2. 分析：

(i) \(T(n) = 2T(n/2) + n\)

\(a = 2, b = 2, c = \log_2 2 = 1\)

\(f(n) = n = \Theta(n^1)\) → Case 2，\(k = 0\)

\(T(n) = \Theta(n \log n)\)（Merge Sort）

(ii) \(T(n) = 4T(n/2) + n\)

\(a = 4, b = 2, c = \log_2 4 = 2\)

\(f(n) = n = O(n^{2-1})\) → Case 1

\(T(n) = \Theta(n^2)\)

(iii) \(T(n) = 2T(n/2) + n^2\)

\(a = 2, b = 2, c = 1\)

\(f(n) = n^2 = \Omega(n^{1+1})\) → Case 3

\(T(n) = \Theta(n^2)\)

© Merge K Sorted Lists¶

4 分 ・大三（考古題 112 Q15）

你需要知道：如何高效合併 \(k\) 個已排序列表？

題目：

有 \(k\) 個已排序列表，每個長度為 \(n\)。比較以下三種合併策略的時間複雜度：

Student A：每次合併兩個列表，直到剩一個
Student B：用 Min-Heap 維護 \(k\) 個列表的頭元素
Student C：分治法，兩兩合併

解答

Student A：Sequential Merge

合併順序：((L1 + L2) + L3) + L4 + ...

第 \(i\) 次合併：合併長度 \(in\) 和 \(n\) 的列表，成本 \(O((i+1)n)\)

總成本：\(\sum_{i=1}^{k-1} O(in) = O(k^2 n)\)

Student B：Min-Heap

import heapq

def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))

    return result

總共 \(kn\) 個元素
每個元素進出 heap 一次
每次操作 \(O(\log k)\)

總成本：\(O(kn \log k)\)

Student C：Divide and Conquer

合併順序：(L1 + L2) 和 (L3 + L4) 並行，然後合併結果

遞迴式：\(T(k) = 2T(k/2) + O(kn)\)

用 Master Theorem：\(a = 2, b = 2, c = 1\)

\(f(k) = kn = \Theta(k)\) → Case 2

\(T(k) = O(kn \log k)\)

比較：

方法	時間複雜度
Sequential	\(O(k^2 n)\)
Min-Heap	\(O(kn \log k)\)
Divide & Conquer	\(O(kn \log k)\)

(d) 分治法設計練習¶

3 分 ・大三

你需要知道：如何用分治法解決新問題？

題目：

設計分治演算法解決 Closest Pair 問題：給定平面上 \(n\) 個點，找出距離最近的兩個點。

解答

演算法：

Divide：按 x 座標排序，從中間分成左右兩半
Conquer：遞迴找左半和右半的最近點對
Combine：
設左半最近距離 \(d_L\)，右半最近距離 \(d_R\)
\(d = \min(d_L, d_R)\)
檢查「跨越中線」的點對：只需檢查距離中線 \(< d\) 的點
對這些點按 y 座標排序，每個點只需檢查接下來 7 個點

時間複雜度：

\[T(n) = 2T(n/2) + O(n \log n)\]

但用聰明的預排序技巧可以做到：

\[T(n) = 2T(n/2) + O(n)\]

\(T(n) = O(n \log n)\)

第 3 題小結：你的分治工具箱¶

「怎麼合併多個排序列表？」
    │
    ├─► (a) 分治三步驟
    │       → Divide, Conquer, Combine
    │
    ├─► (b) Master Theorem
    │       → 快速分析 T(n) = aT(n/b) + f(n)
    │
    ├─► (c) Merge K Lists
    │       → Sequential: O(k²n)
    │       → Heap / D&C: O(kn log k)
    │
    └─► (d) 設計練習
            → Closest Pair: O(n log n)

問題	分治複雜度
Merge Sort	\(O(n \log n)\)
Quick Sort	\(O(n \log n)\) 期望
Merge K Lists	\(O(kn \log k)\)
Closest Pair	\(O(n \log n)\)

< 上一題：Rabin-Karp | 返回目錄 | 下一題：貪心法 >