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

< 上一題：分治法 | 返回目錄 | 下一題：平攤分析 >

---

場景：壓縮索引檔案

SearchX 的倒排索引有 10TB。每天的儲存成本是真金白銀。

觀察：不同字元出現頻率差很多。「the」出現百萬次，「xylophone」可能只出現幾次。

「能不能讓常見字元用更少的位元？」

---

第 4 題：索引壓縮 - 貪心法與 Huffman Coding

貪心法（Greedy）是一種「每步都選當下最好」的策略。看似簡單，但**正確性證明**是關鍵。

---

(a) 貪心法的基本概念

3 分 ・ 大二

你需要知道：什麼是貪心法？什麼時候可以用？

題目：

1. 說明貪心法的核心思想
2. 貪心法需要什麼性質才能保證最優解？
3. 舉一個貪心法**不**能得到最優解的例子

解答

1. 核心思想：

每一步都選「當下最好的選擇」，期望最終得到全局最優解

2. 兩個關鍵性質：

性質	說明
Greedy Choice Property	局部最優選擇能導向全局最優
Optimal Substructure	最優解包含子問題的最優解

3. 反例：找零錢問題

硬幣面額：1, 3, 4 元 目標：6 元

• 貪心：4 + 1 + 1 = 3 枚硬幣
• 最優：3 + 3 = 2 枚硬幣

貪心失敗！因為不具備 Greedy Choice Property。

---

(b) Huffman Coding 原理

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

你需要知道：Huffman 編碼如何達到最優壓縮？

題目：

給定字元頻率：

字元	a	b	c	d	e
頻率	45	13	12	16	9

1. 建立 Huffman Tree
2. 寫出每個字元的編碼
3. 計算平均編碼長度

提示

每次取頻率**最小的兩個**節點合併

解答

1. 建立過程：

初始：a:45, b:13, c:12, d:16, e:9

Step 1：合併最小的 c(12) 和 e(9)

(ce):21, a:45, b:13, d:16

Step 2：合併最小的 b(13) 和 d(16)

(ce):21, a:45, (bd):29

Step 3：合併 (ce)(21) 和 a(45)？不對，應該是 (ce)(21) 和 (bd)(29)

a:45, (cebd):50

Step 4：合併 a(45) 和 (cebd)(50)

(root):95

2. Huffman Tree：

          (95)
         /    \
      a(45)   (50)
             /    \
         (21)     (29)
        /    \   /    \
      c(12) e(9) b(13) d(16)

3. 編碼：

字元	編碼	長度
a	0	1
c	100	3
e	101	3
b	110	3
d	111	3

4. 平均編碼長度：

\[\text{平均長度} = \frac{45 \times 1 + 12 \times 3 + 9 \times 3 + 13 \times 3 + 16 \times 3}{45 + 12 + 9 + 13 + 16}\]

\[= \frac{45 + 36 + 27 + 39 + 48}{95} = \frac{195}{95} \approx 2.05 \text{ bits}\]

比固定 3-bit 編碼（\(\lceil \log_2 5 \rceil = 3\)）節省約 32%！

---

© Huffman 演算法實作

3 分 ・ 大三

你需要知道：如何用 Min-Heap 高效實作？

題目：

1. 寫出 Huffman 演算法的 pseudocode
2. 分析時間複雜度

解答

1. Pseudocode：

def build_huffman_tree(frequencies):
    # 建立 Min-Heap，每個節點包含頻率和子樹
    heap = MinHeap()
    for char, freq in frequencies.items():
        heap.insert(Node(freq, char))

    # 反覆合併直到只剩一個節點
    while heap.size() > 1:
        # 取出兩個最小的
        left = heap.extract_min()
        right = heap.extract_min()

        # 合併
        merged = Node(left.freq + right.freq)
        merged.left = left
        merged.right = right

        # 放回 heap
        heap.insert(merged)

    return heap.extract_min()  # 根節點

2. 時間複雜度：

• \(n\) 個字元
• 建 heap：\(O(n)\)
• 迴圈執行 \(n-1\) 次，每次：
• 2 次 extract_min：\(O(\log n)\)
• 1 次 insert：\(O(\log n)\)
• 總計：\(O(n) + O(n \log n) = O(n \log n)\)

---

(d) Huffman 最優性證明

4 分 ・ 大三

你需要知道：為什麼貪心策略能得到最優解？

題目：

證明 Huffman 演算法產生的編碼具有最小的加權路徑長度。

提示

使用 exchange argument：假設最優解與貪心解不同，證明可以「交換」使其更好或一樣好

解答

證明策略：證明兩個性質

Lemma 1：頻率最小的兩個字元在最優樹中是兄弟

設 \(x, y\) 是頻率最小的兩個字元。

假設在某個最優樹 \(T\) 中，\(x\) 和 \(y\) 不是兄弟。

設 \(a, b\) 是 \(T\) 中深度最大的兄弟節點。

交換 \(x\) 和 \(a\)： - 因為 \(f(x) \le f(a)\) 且 \(d(a) \ge d(x)\) - 交換後加權路徑長度 \(\le\) 原來

同理交換 \(y\) 和 \(b\)。

結論：存在最優樹使 \(x, y\) 是兄弟。

Lemma 2：Optimal Substructure

設 \(T\) 是字元集 \(C\) 的最優 Huffman 樹。

將 \(x, y\) 合併為 \(z\)（頻率 \(f(z) = f(x) + f(y)\)）。

則 \(T' = T\) 把 \(x, y\) 替換成 \(z\) 後，是字元集 \(C' = C - \{x, y\} \cup \{z\}\) 的最優樹。

綜合：

• Greedy Choice Property ✓（Lemma 1）
• Optimal Substructure ✓（Lemma 2）

因此 Huffman 貪心演算法產生最優解。

---

(e) Prefix-Free Code 性質

3 分 ・ 大二

你需要知道：為什麼 Huffman 編碼可以無歧義解碼？

題目：

1. 什麼是 Prefix-Free Code？
2. 為什麼 Huffman 編碼是 Prefix-Free？
3. 給定編碼串 0100101110，用 (b) 的編碼表解碼

解答

1. Prefix-Free Code：

沒有任何編碼是另一個編碼的前綴。

特性	說明
定義	\(\forall c_1, c_2: \text{code}(c_1)\) 不是 \(\text{code}(c_2)\) 的前綴
好處	可以即時解碼，不需分隔符

2. 為什麼 Huffman 是 Prefix-Free？

在 Huffman Tree 中，所有字元都在**葉節點**。

從根到任一葉的路徑，不會經過另一個葉。

因此沒有編碼是另一個的前綴。

3. 解碼：

使用 (b) 的編碼表：a=0, c=100, e=101, b=110, d=111

0 | 100 | 101 | 110
a |  c  |  e  |  b

解碼結果：aceb

---

(f) 貪心法設計練習

3 分 ・ 大三（考古題 107 Q5a）

你需要知道：如何判斷貪心法是否適用？

題目：

Activity Selection Problem：有 \(n\) 個活動，每個有開始和結束時間。選出最多不重疊的活動。

1. 設計貪心策略
2. 證明正確性

解答

1. 貪心策略：

每次選**結束時間最早**的活動。

def activity_selection(activities):
    # 按結束時間排序
    activities.sort(key=lambda x: x.end)

    result = [activities[0]]
    last_end = activities[0].end

    for activity in activities[1:]:
        if activity.start >= last_end:
            result.append(activity)
            last_end = activity.end

    return result

2. 正確性證明（Exchange Argument）：

設 OPT 是最優解，按結束時間排序為 \(o_1, o_2, \ldots, o_k\)。

設 GREEDY 選的第一個是 \(g_1\)（結束最早）。

Claim：\(g_1.end \le o_1.end\)

• 因為 \(g_1\) 是所有活動中結束最早的
• \(o_1\) 在所有活動中，所以 \(g_1.end \le o_1.end\)

Exchange：把 OPT 中的 \(o_1\) 換成 \(g_1\)

• 因為 \(g_1.end \le o_1.end\)
• 所有原本與 \(o_1\) 不重疊的活動，也與 \(g_1\) 不重疊
• 新解仍然有 \(k\) 個活動

結論：存在最優解的第一個選擇是 \(g_1\)。

遞迴地對剩餘活動應用相同論證，證明 GREEDY = OPT。

---

第 4 題小結：你的貪心工具箱

「怎麼壓縮索引？」
    │
    ├─► (a) 貪心法基礎
    │       → 局部最優 ≠ 全局最優（需證明）
    │
    ├─► (b) Huffman Tree
    │       → 頻率低 = 編碼長
    │
    ├─► (c) 實作
    │       → Min-Heap，O(n log n)
    │
    ├─► (d) 最優性證明
    │       → Exchange Argument
    │
    ├─► (e) Prefix-Free
    │       → 葉節點 = 無前綴衝突
    │
    └─► (f) 設計練習
            → Activity Selection

問題	貪心策略	時間複雜度
Huffman Coding	合併最小頻率	\(O(n \log n)\)
Activity Selection	選最早結束	\(O(n \log n)\)
Fractional Knapsack	選最高單位價值	\(O(n \log n)\)
Dijkstra	選最近未訪問	\(O((V+E) \log V)\)

貪心 vs DP：

比較	貪心法	動態規劃
決策	一次性	考慮所有可能
回溯	不回溯	可以回溯
證明	需要證明正確性	正確性較明顯
效率	通常更快	通常較慢

---

< 上一題：分治法 | 返回目錄 | 下一題：平攤分析 >