109 年 國立臺北大學資訊工程研究所《資料結構與演算法》

核心觀念

本題要求在長度為 $n$ 的陣列中尋找第 $i$ 小元素，且期望時間為 $O(n)$。核心方法是：

• 隨機選擇 pivot。
• 進行一次 partition，將元素分成小於、等於、大於 pivot 的區域。
• 根據第 $i$ 小元素所在區域，只遞迴處理其中一側。

這種方法稱為 Randomized Quickselect，是 Quicksort 的選擇問題版本。

與 Quicksort 必須遞迴處理左右兩側不同，Quickselect 每一層只處理一個子問題，因此期望時間可以達到線性。

---

解題方法：Randomized Quickselect

假設要找第 $i$ 小元素，其中 $1\leq i\leq n$。

隨機選擇一個 pivot，並將陣列分成三部分：

$$L=\{x:x<\text{pivot}\},$$ $$E=\{x:x=\text{pivot}\},$$ $$G=\{x:x>\text{pivot}\}.$$

令

$$\ell=|L|,\qquad e=|E|.$$

則：

1. 若 $i\leq \ell$，第 $i$ 小元素位於 $L$，遞迴尋找 $L$ 中的第 $i$ 小元素。
2. 若 $\ell<i\leq \ell+e$，第 $i$ 小元素就是 pivot。
3. 若 $i>\ell+e$，第 $i$ 小元素位於 $G$，遞迴尋找 $G$ 中的第
   $i-\ell-e$ 小元素。

關鍵程式碼

RandomizedSelect(A, i):
    if length(A) == 1:
        return A[1]

    randomly choose pivot from A

    partition A into:
        L = elements smaller than pivot
        E = elements equal to pivot
        G = elements greater than pivot

    if i <= length(L):
        return RandomizedSelect(L, i)

    else if i <= length(L) + length(E):
        return pivot

    else:
        return RandomizedSelect(
            G,
            i - length(L) - length(E)
        )

若陣列元素互異，$E$ 只有 pivot 一個元素；若有重複元素，使用三向 partition 可以一次處理所有等於 pivot 的元素。

---

正確性說明

Partition 後，所有元素均符合以下順序：

$$L<E<G.$$

因此排序後：

• $L$ 佔據最前面的 $\ell$ 個位置；
• $E$ 接續佔據接下來的 $e$ 個位置；
• $G$ 佔據剩餘位置。

核心觀念

Floyd–Warshall 演算法利用動態規劃，逐步允許頂點作為最短路徑的中繼點。

令 $D^{(k)}_{ij}$ 表示：只允許頂點 $1,2,\ldots,k$ 作為中繼點時，從頂點 $i$ 到頂點 $j$ 的最短距離，則有

$$D^{(k)}_{ij} = \min\left( D^{(k-1)}_{ij}, D^{(k-1)}_{ik}+D^{(k-1)}_{kj} \right).$$

其中：

• $D^{(0)}$：不允許任何中繼點。
• $D^{(1)}$：允許頂點 $1$ 作為中繼點。
• $D^{(2)}$：允許頂點 $1,2$ 作為中繼點。
• $D^{(3)}$：允許頂點 $1,2,3$ 作為中繼點。
• $D^{(4)}$：允許頂點 $1,2,3,4$ 作為中繼點，亦即最後的全點對最短距離矩陣。

題目要求產生五個矩陣，因此可合理推定圖形有四個頂點。

解題方法

初始矩陣 $D^{(0)}$ 的建立方式如下：

$$D^{(0)}_{ij} = \begin{cases} 0, & i=j,\\ w(i,j), & \text{若圖中有邊 }i\to j,\\ \infty, & \text{若圖中沒有邊 }i\to j. \end{cases}$$

接著依序計算：

$$D^{(1)}_{ij} = \min\left(D^{(0)}_{ij},D^{(0)}_{i1}+D^{(0)}_{1j}\right),$$ $$D^{(2)}_{ij} = \min\left(D^{(1)}_{ij},D^{(1)}_{i2}+D^{(1)}_{2j}\right),$$ $$D^{(3)}_{ij} = \min\left(D^{(2)}_{ij},D^{(2)}_{i3}+D^{(2)}_{3j}\right),$$ $$D^{(4)}_{ij} = \min\left(D^{(3)}_{ij},D^{(3)}_{i4}+D^{(3)}_{4j}\right).$$

每次更新只需比較兩種路徑：

給定輸入陣列 $A = (7, 6, 7, 5, 5, 4, 2, 5, 1, 3, 1, 7, 1, 2, 3)$，長度 $n = 15$，元素數值範圍為 $1 \le A[i] \le 7$（即最大值 $k = 7$）。

步驟 1：建立次數統計陣列（Count Array $C$）

統計 $A$ 中每個數值出現的頻率（索引 $1 \sim 7$）：

• $C[1] = 3$ （數字 1 出現 3 次）
• $C[2] = 2$ （數字 2 出現 2 次）
• $C[3] = 2$ （數字 3 出現 2 次）
• $C[4] = 1$ （數字 4 出現 1 次）
• $C[5] = 3$ （數字 5 出現 3 次）
• $C[6] = 1$ （數字 6 出現 1 次）
• $C[7] = 3$ （數字 7 出現 3 次）

次數陣列狀態：$C[1..7] = (3, 2, 2, 1, 3, 1, 3)$

---

步驟 2：計算前綴和陣列（Accumulated Count Array）

累加 $C$ 的次數，決定各數值在最終輸出陣列中的結束放置位置：

• $C[1] = 3$
• $C[2] = 3 + 2 = 5$
• $C[3] = 5 + 2 = 7$
• $C[4] = 7 + 1 = 8$
• $C[5] = 8 + 3 = 11$
• $C[6] = 11 + 1 = 12$
• $C[7] = 12 + 3 = 15$

前綴和陣列狀態：$C[1..7] = (3, 5, 7, 8, 11, 12, 15)$

---

步驟 3：由右至左掃描並填入輸出陣列（Output Array $B$）

為維護排序的穩定性（Stability），由右至左（從 $A[15]$ 至 $A[1]$）掃描原陣列，並將元素放至 $B[C[A[i]]]$，隨後將 $C[A[i]]$ 減 1：

1. 處理 $A[15] = 3$：放置於 $B[C[3]] = B[7] = 3$，$C[3]$ 更新為 $6$
2. 處理 $A[14] = 2$：放置於 $B[C[2]] = B[5] = 2$，$C[2]$ 更新為 $4$

證明過程

一、強化歸納假設
若直接假設 $T(n) \le cn$，帶入遞迴式會得到 $T(n) \le cn + 1$，無法直接推出 $T(n) \le cn$。因此強化歸納假設為：存在正數 $c$ 與 $d$，使得 $T(n) \le cn - d$。

二、基礎步驟（Base Case）
設當 $n = 1$ 時，$T(1) = c_0$（$c_0$ 為已知正常數）。
要使 $T(1) \le c \cdot 1 - d$ 成立，只需選取 $c$ 滿足 $c \ge c_0 + d$。

三、歸納假設（Inductive Hypothesis）
假設對所有滿足 $1 \le k < n$ 的正整數 $k$，均成立 $T(k) \le ck - d$。

四、歸納步驟（Inductive Step）
對正整數 $n > 1$，利用遞迴定義與歸納假設：
$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1$

核心觀念

本題考查兩種典型的分治法：

1. Merge Sort：將數列遞迴分成較小的子數列，排序後再合併。
2. Binary Search：在已排序數列中，每次比較中間元素，排除一半不可能的範圍。

Merge Sort 的合併規則為：

• 比較兩個已排序子數列目前最前面的元素。
• 將較小者放入結果。
• 若兩者相等，可固定取左邊子數列的元素，以維持穩定排序。
• 任一子數列用完後，直接接上另一子數列剩餘元素。

其時間複雜度為：

$$T(N)=2T\left(\frac{N}{2}\right)+O(N)=O(N\log N)$$

合併時需要額外的陣列空間，因此空間複雜度為 $O(N)$。

---

（A）使用 Merge Sort 排序

原數列共有 $20$ 個數字：

$$6\ 9\ 5\ 8\ 5\ 3\ 6\ 1\ 2\ 2\ 0\ 5\ 9\ 4\ 7\ 3\ 3\ 1\ 1\ 7$$

1. 分割數列

先遞迴分割，直到每個子數列只剩一個元素：

$$[6,9,5,8,5,3,6,1,2,2] \quad [0,5,9,4,7,3,3,1,1,7]$$

左半部再分為：

$$[6,9,5,8,5]\quad [3,6,1,2,2]$$

右半部再分為：

$$[0,5,9,4,7]\quad [3,3,1,1,7]$$

2. 由小到大合併

各子數列排序後：

$$[6,9,5,8,5]\longrightarrow[5,5,6,8,9]$$ $$[3,6,1,2,2]\longrightarrow[1,2,2,3,6]$$

合併兩個已排序子數列：

$$[5,5,6,8,9]\ \text{與}\ [1,2,2,3,6]$$

逐次比較最前端元素：

• $1<5$，取 $1$
• $2<5$，取 $2$
• $2<5$，取 $2$
• $3<5$，取 $3$
• $5<6$，取 $5$
• 再取 $5$
• $6=6$，取左側的 $6$
• 右側剩下 $6$，接上
• 再接上 $8,9$

得到：

$$[1,2,2,3,5,5,6,6,8,9]$$

右半部：

$$[0,5,9,4,7]\longrightarrow[0,4,5,7,9]$$ $$[3,3,1,1,7]\longrightarrow[1,1,3,3,7]$$

合併：

$$[0,4,5,7,9]\ \text{與}\ [1,1,3,3,7]$$

逐次比較後得到：

$$[0,1,1,3,3,4,5,7,7,9]$$

3. 最後合併左右兩半

合併：

$$[1,2,2,3,5,5,6,6,8,9]$$

與

$$[0,1,1,3,3,4,5,7,7,9]$$

依序比較兩邊最前端元素：

$$\begin{aligned} &0,\ 1,\ 1,\ 1,\ 2,\ 2,\ 3,\ 3,\ 3,\ 4,\\ &5,\ 5,\ 5,\ 6,\ 6,\ 7,\ 7,\ 8,\ 9,\ 9 \end{aligned}$$

因此排序結果為：

$$\boxed{0\ 1\ 1\ 1\ 2\ 2\ 3\ 3\ 3\ 4\ 5\ 5\ 5\ 6\ 6\ 7\ 7\ 8\ 9\ 9}$$

也可連寫為：

$$\boxed{01112233345556677899}$$

解題技巧

Merge Sort 合併時，不必重新搜尋整個子數列，只需要比較兩個子數列目前的第一個未處理元素。每取出一個元素，就將該子數列的指標向右移動一格。

常見錯誤包括：

核心觀念

本題考查：

1. 中序式（inorder／infix）：運算子位於兩個運算元之間，例如 $A+B$。

2. 後序式（postorder／postfix）：運算子位於兩個運算元之後，例如 $AB+$。

3. 二元運算樹：

   • 左子樹
   • 根節點
   • 右子樹

   對運算樹進行中序走訪可得到中序式，進行後序走訪可得到後序式。

4. 運算子優先權與結合性：

   $\text{括號} > \text{乘除} > \text{加減}$

   同一優先權的運算子由左至右結合，因此：

   $A*B+C*(D-E)/(F+H)$

   代表：

   $((A*B)+(C*(D-E))/(F+H))$

---

（A）轉換為後序式並建立二元樹

1. 依優先權加上結構

原式為：

$A*B+C*(D-E)/(F+H)$

依照括號、乘除、加減的規則，可解析為：

$((A*B)+((C*(D-E))/(F+H)))$

因此最外層運算子是加號 $+$。

2. 二元運算樹

              +
            /   \
           *     /
          / \   / \
         A   B *   +
              / \ / \
             C  - F  H
               / \
              D   E

其中右子樹的結構為：

$\frac{C*(D-E)}{F+H}$

所以：

• 左子樹 $A*B$ 的後序式為 $AB*$
• $D-E$ 的後序式為 $DE-$
• $C*(D-E)$ 的後序式為 $CDE-*$
• $F+H$ 的後序式為 $FH+$
• 整個除法的後序式為 $CDE-*FH+/$
• 最後與左子樹以 $+$ 合併

3. 後序式

$\boxed{AB*CDE-*FH+/+}$

若以空格分隔，寫成：

$\boxed{A\ B\ *\ C\ D\ E\ -\ *\ F\ H\ +\ /\ +}$

4. 快速驗算

後序式中每個二元運算子都應在其左右兩個運算結果之後：

• $AB*$：先計算 $A*B$
• $DE-$：先計算 $D-E$
• $CDE-*$：再計算 $C*(D-E)$
• $FH+$：計算 $F+H$
• /：計算 $\dfrac{C*(D-E)}{F+H}$
• 最後 +：與 $A*B$ 相加

---

（B）使用 Stack 將中序式轉為後序式

1. 演算法原理

掃描中序式，依序處理每個符號：

• 運算元：直接輸出。
• 左括號 (：直接推入 stack。
• 右括號 )：持續彈出並輸出運算子，直到遇到左括號；左括號彈出但不輸出。
• 運算子：
  • 若 stack 頂端是優先權較高的運算子，先彈出並輸出。
  • 若 stack 頂端是相同優先權且採左結合的運算子，也先彈出並輸出。
  • 再將目前運算子推入 stack。
• 掃描結束：將 stack 中剩餘的運算子依序彈出並輸出。

優先權函式如下：

$$\operatorname{prec}('+' )=\operatorname{prec}('-')=1$$ $$\operatorname{prec}('*')=\operatorname{prec}('/')=2$$

由於本題的運算子皆為左結合，因此判斷條件為：

$$\operatorname{prec}(\text{stack top}) \geq \operatorname{prec}(\text{current operator})$$

---

2. 演算法虛擬碼