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

< 上一題：貪心法 | 返回目錄 | 下一題：NP 基礎 >

場景：動態擴展的倒排索引¶

SearchX 的索引需要頻繁插入新網頁。你用 Dynamic Array 實作：滿了就擴容到兩倍。

單次擴容要複製所有元素，代價 $O(n)$。這樣效能能接受嗎？

「雖然偶爾很慢，但平均下來其實很快？」

第 5 題：動態索引更新 - 平攤分析¶

平攤分析（Amortized Analysis）分析一系列操作的**平均**成本，而非最壞情況。

(a) 平攤分析 vs 平均分析¶

3 分 ・大二

你需要知道：平攤分析和平均分析有什麼不同？

題目：

區分 Amortized Analysis 和 Average-Case Analysis
為什麼平攤分析不需要機率假設？

解答

1. 關鍵區別：

分析方法	考慮對象	是否需要機率
Average-Case	所有可能輸入的平均	是，需要輸入分布
Amortized	一系列操作的平均	否，是最壞情況保證

2. 為什麼不需要機率？

平攤分析考慮的是：

「對於**任何**操作序列，$n$ 次操作的總成本 $\le c \cdot n$」

這是一個**確定性**的上界，不依賴輸入的機率分布。

例子：Dynamic Array

不管你插入什麼元素、以什麼順序插入
$n$ 次插入的總成本一定 $\le 3n$
因此平攤成本 $\le 3$，是**保證**而非期望

(b) Aggregate Method¶

3 分 ・大三（考古題 113 Q3）

你需要知道：最直觀的平攤分析方法

題目：

分析 Dynamic Array 的插入操作。當陣列滿時，擴容為兩倍大小。

用 Aggregate Method 證明平攤成本是 $O(1)$。

解答

Aggregate Method：計算 $n$ 次操作的總成本，除以 $n$。

分析：

從空陣列開始，插入 $n$ 個元素。

擴容發生在 size = 1, 2, 4, 8, ..., $2^k$（其中 $2^k \le n < 2^{k+1}$）

總成本：

類型	次數	每次成本	小計
普通插入	$n$	1	$n$
擴容複製	1次	1	1
擴容複製	1次	2	2
擴容複製	1次	4	4
...	...	...	...
擴容複製	1次	$2^k$	$2^k$

擴容總成本：$1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 < 2n$

總成本：$n + 2n = 3n$

平攤成本：$\frac{3n}{n} = 3 = O(1)$

© Accounting Method¶

4 分 ・大三

你需要知道：用「存款」的概念分析平攤成本

題目：

用 Accounting Method 重新分析 Dynamic Array。

提示

每次插入「預付」一些費用，存起來給未來的擴容用

解答

Accounting Method：為每個操作設定「收費」，多收的存起來，不足的從存款扣。

策略：每次插入收 3 元

用途	費用
實際插入	1 元
存款（給自己未來搬家）	1 元
存款（給舊元素搬家）	1 元

為什麼夠用？

考慮擴容時刻（從 size $k$ 擴到 $2k$）：

需要搬移 $k$ 個元素
這 $k$ 個元素中，有 $k/2$ 個是「舊的」（上次擴容後就在的）
另外 $k/2$ 個是「新的」（上次擴容後插入的）

每個「新」元素插入時存了 2 元： - 1 元給自己搬家 - 1 元給一個「舊」元素搬家

所以 $k/2$ 個新元素提供 $k$ 元，剛好夠搬 $k$ 個元素！

結論：平攤成本 = 3 = $O(1)$

(d) Potential Method¶

4 分 ・大三

你需要知道：最數學化但最強大的方法

題目：

用 Potential Method 分析 Dynamic Array。

解答

Potential Method：定義「勢能函數」$\Phi$，平攤成本 = 實際成本 + $\Delta\Phi$

勢能函數：

\[\Phi = 2 \cdot \text{num} - \text{size}\]

$\text{num}$：目前元素數量
$\text{size}$：目前陣列大小

條件：$\Phi_0 = 0$，且 $\Phi_i \ge 0$（確保總平攤成本 $\ge$ 總實際成本）

Case 1：普通插入（不擴容）

實際成本：1
$\Delta\Phi = 2(num+1) - size - (2 \cdot num - size) = 2$
平攤成本：$1 + 2 = 3$

Case 2：擴容插入

舊狀態：$num = size = k$
新狀態：$num = k+1$, $size = 2k$
實際成本：$1 + k$（插入 + 複製）
$\Delta\Phi = [2(k+1) - 2k] - [2k - k] = 2 - k$
平攤成本：$(1+k) + (2-k) = 3$

結論：兩種情況平攤成本都是 3 = $O(1)$

(e) Binary Counter¶

4 分 ・大三（考古題 114 Q18）

你需要知道：經典的平攤分析範例

題目：

一個 $k$-bit 二進位計數器，從 0 開始遞增。分析 $n$ 次 INCREMENT 的平攤成本。

解答

操作分析：

INCREMENT 翻轉若干位元，直到遇到 0（或溢位）。

0000 → 0001  (翻 1 bit)
0001 → 0010  (翻 2 bits)
0010 → 0011  (翻 1 bit)
0011 → 0100  (翻 3 bits)
0100 → 0101  (翻 1 bit)
...

Aggregate Method：

位元	翻轉頻率	$n$ 次操作翻轉次數
bit 0	每次	$n$
bit 1	每 2 次	$n/2$
bit 2	每 4 次	$n/4$
bit $i$	每 $2^i$ 次	$n/2^i$

總翻轉次數：$\sum_{i=0}^{k-1} \frac{n}{2^i} < n \sum_{i=0}^{\infty} \frac{1}{2^i} = 2n$

平攤成本：$\frac{2n}{n} = 2 = O(1)$

Potential Method：

設 $\Phi = $ 計數器中 1 的個數

INCREMENT 將 $t$ 個 1 翻成 0，然後（可能）將 1 個 0 翻成 1。

實際成本：$t + 1$
$\Delta\Phi \le 1 - t$
平攤成本：$(t+1) + (1-t) = 2 = O(1)$

(f) 平攤分析應用¶

3 分 ・大三

你需要知道：什麼時候使用哪種方法？

題目：

比較三種平攤分析方法的適用場景。

解答

方法比較：

方法	思路	適用場景
Aggregate	算總成本再平均	操作模式固定、好數
Accounting	預付存款	直觀、好解釋
Potential	勢能變化	最通用、可處理複雜情況

選擇建議：

先試 Aggregate：如果能輕易算出總成本
再試 Accounting：如果有自然的「存款」概念
最後用 Potential：如果前兩者不行

經典應用：

資料結構	平攤成本	常用方法
Dynamic Array	$O(1)$ insert	三種皆可
Binary Counter	$O(1)$ increment	Aggregate/Potential
Splay Tree	$O(\log n)$ 操作	Potential
Fibonacci Heap	$O(1)$ decrease-key	Potential
Union-Find	$O(\alpha(n))$	Potential

第 5 題小結：你的平攤分析工具箱¶

「擴容很貴，但平均呢？」
    │
    ├─► (a) 平攤 vs 平均
    │       → 平攤是最壞情況保證
    │
    ├─► (b) Aggregate Method
    │       → 總成本 / 操作數
    │
    ├─► (c) Accounting Method
    │       → 預付存款，收支平衡
    │
    ├─► (d) Potential Method
    │       → 平攤 = 實際 + ΔΦ
    │
    ├─► (e) Binary Counter
    │       → 經典範例，O(1) 平攤
    │
    └─► (f) 方法選擇
            → Aggregate → Accounting → Potential

三種方法的關係：

             ┌─────────────────┐
             │  Potential      │  最通用
             │  Φ: state → ℝ   │
             └────────┬────────┘
                      │ 特例
             ┌────────▼────────┐
             │  Accounting     │  直觀
             │  存款 = 預付費用  │
             └────────┬────────┘
                      │ 特例
             ┌────────▼────────┐
             │  Aggregate      │  簡單
             │  總成本 / n      │
             └─────────────────┘

< 上一題：貪心法 | 返回目錄 | 下一題：NP 基礎 >

類型	次數	每次成本	小計
普通插入	\(n\)	1	\(n\)
擴容複製	1次	1	1
擴容複製	1次	2	2
擴容複製	1次	4	4
...	...	...	...
擴容複製	1次	\(2^k\)	\(2^k\)

資料結構	平攤成本	常用方法
Dynamic Array	\(O(1)\) insert	三種皆可
Binary Counter	\(O(1)\) increment	Aggregate/Potential
Splay Tree	\(O(\log n)\) 操作	Potential
Fibonacci Heap	\(O(1)\) decrease-key	Potential
Union-Find	\(O(\alpha(n))\)	Potential