115 年 國立臺灣大學資料科學碩士學位學程《資料結構與演算法》

核心觀念

本題結合「堆疊（Stack）資料結構」與「多項式求值的霍納法則（Horner's Method）」。

1. 堆疊（Stack）的後進先出（LIFO）特性：
   依題意，堆疊 $S$ 由頂端至底端依序為 $a_n, a_{n-1}, \dots, a_0$。因此在迴圈中，第一次執行 pop() 會取出位於最頂端的最高次項係數 $a_n$，第二次 pop() 則取出次高次項係數 $a_{n-1}$。
2. 霍納法則（Horner's Method）：
   對於 $n$ 次多項式 $f(x) = \sum_{i=0}^n a_i x^i = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$，霍納法則將其改寫為嵌套乘法形式：
   $f(x) = (\dots((a_n \cdot x + a_{n-1}) \cdot x + a_{n-2}) \cdot x + \dots + a_1) \cdot x + a_0$
   這種計算方式只需 $n$ 次乘法與 $n$ 次加法，是多項式求值最有效率的演算法。

解題方法

透過追蹤演算法在迴圈中的堆疊彈出（pop）與壓入（push）過程，可推導出空格 $\square$ 應填入的運算式。

1. 初始狀態與變數賦值
堆疊內部內容由頂端至底端為：
$\text{Stack } S = [a_n, a_{n-1}, a_{n-2}, \dots, a_0] \quad (\text{Top } \rightarrow \text{ Bottom})$

2. 第一輪迴圈（Iteration 1）

• 執行第 2 行 u = S.pop()：取出頂端元素，此時 $u = a_n$。
• 執行第 3 行 v = S.pop()：取出次頂端元素，此時 $v = a_{n-1}$。
• 根據霍納法則，第一階段需計算出 $a_n \cdot x + a_{n-1}$。
• 將 $u = a_n$ 與 $v = a_{n-1}$ 代入，該計算式即為：
  $u \cdot x + v$
• 執行第 4 行 S.push(u * x + v) 後，堆疊頂端變為 $(a_n x + a_{n-1})$。

3. 第二輪迴圈（Iteration 2）

• 執行第 2 行 u = S.pop()：此時 $u = a_n x + a_{n-1}$。
• 執行第 3 行 v = S.pop()：此時 $v = a_{n-2}$。

核心觀念

本題旨在考驗**漸近記號（Asymptotic Notation）**的嚴格數學定義及其代數運算性質。主要涵蓋以下關鍵觀念：

1. $O$ 記號與 $\Omega$ 記號的雙重性（Duality）：對正函數而言，$f(n) = O(g(n)) \iff g(n) = \Omega(f(n))$。
2. 正函數與常數下界：條件 $f(n) = \Omega(1)$ 代表存在常數 $c_0 > 0$，使得對足夠大的 $n$，恆有 $f(n) \ge c_0$。此條件確保對數與冪次運算時不會產生趨近於零或未定義的極限異常。
3. 單調函數對漸近比較的保序性：分析 $f(n) = O(g(n))$ 在經過對數、冪次與指數函數作用後，其漸近等級是否仍被保持。

解題方法

本題包含四個獨立的命題判定，切入點如下：

1. 定義法（直接推導）：針對第一項與第四項敘述，直接利用 $O$ 記號的數學定義（常數倍不等式）進行同方向的移項與次冪縮放。
2. 不等式放縮法：針對第二項敘述，結合 $f(n) = \Omega(1)$ 提供的不等式下界，利用對數函數在正數區間的對數放縮性質進行比較。
3. 反例排除法（Counterexample）：針對第三項敘述，考慮 $f(n) = O(g(n))$ 只限定了 $g(n)$ 的增長下界而非上界，構造超指數增長函數來反駁。

選項分析

• 敘述一：$g(n) = \Omega(f(n))$ — 【正確】

  • 證明：依據 $f(n) = O(g(n))$ 的定義，存在正實數常數 $c_1 > 0$ 與正整數 $n_0$，使得對所有 $n \ge n_0$，恆有：
    $f(n) \le c_1 \cdot g(n)$
  • 由於 $c_1 > 0$，將不等式兩邊同除以 $c_1$，可得：
    $g(n) \ge \left(\frac{1}{c_1}\right) \cdot f(n)$
  • 取常數 $c_2 = \frac{1}{c_1} > 0$，即符合 $\Omega$ 記號之定義：存在常數 $c_2 > 0$，對所有 $n \ge n_0$ 均有 $g(n) \ge c_2 \cdot f(n)$，故 $g(n) = \Omega(f(n))$ 成立。

• 敘述二：$f(n) \cdot \log(1+f(n)) = O(g(n) \cdot \log(1+g(n)))$ — 【正確】

  • 證明：由已知條件，存在 $c_1 > 0$ 與 $c_0 > 0$，使得當 $n \ge n_0$ 時，$c_0 \le f(n) \le c_1 \cdot g(n)$。
  • 由於 $g(n) \ge \frac{1}{c_1} f(n) \ge \frac{c_0}{c_1} > 0$，設 $a = \frac{c_0}{c_1} > 0$，故 $g(n)$ 亦具備正常數下界。
  • 考慮對數部分的縮放：
    • 若 $c_1 \le 1$，則 $f(n) \le g(n)$。由於 $h(x) = \log(1+x)$ 在 $x > 0$ 為嚴格單調遞增函數，故 $\log(1+f(n)) \le \log(1+g(n))$ 直接成立。
    • 若 $c_1 > 1$，則：
      $\log(1+f(n)) \le \log(1+c_1 g(n)) = \log\left(c_1\left(\frac{1}{c_1} + g(n)\right)\right) < \log(c_1(1+g(n))) = \log c_1 + \log(1+g(n))$
    • 因 $g(n) \ge a > 0$，可知 $\log(1+g(n)) \ge \log(1+a) > 0$。因此：

核心觀念

本題考驗分治法（Divide-and-Conquer）矩陣乘法的時間複雜度分析，以及**主定理（Master Theorem）**的應用。

1. 矩陣乘法分治法：
   將邊長為 $N$ 的矩陣切分為邊長為 $\frac{N}{b}$ 的子矩陣，若完成一次大矩陣乘法需要 $a$ 次子矩陣乘法，則時間複雜度遞迴式為：
   $T(N) = a T\left(\frac{N}{b}\right) + O(N^2)$
2. 主定理（Master Theorem）：
   對於遞迴式 $T(N) = a T\left(\frac{N}{b}\right) + O(N^d)$：
   • 若 $a > b^d$（即 $\log_b a > d$），則時間複雜度為 $O\left(N^{\log_b a}\right)$，指數 $x = \log_b a$。

解題方法

1. 確定分割基底與子問題數量：

   • 傳統 Strassen 演算法是將 $N \times N$ 矩陣視為 $2 \times 2$ 個大小為 $\frac{N}{2} \times \frac{N}{2}$ 的子矩陣，使用 7 次乘法。若連續遞迴應用兩層於 $4 \times 4$ 結構，乘法次數為 $7 \times 7 = 49$ 次。
   • DeepMind 的 AlphaTensor 演算法針對 $4 \times 4$ 矩陣結構進行優化，將 $N \times N$ 矩陣分割為 $4 \times 4$ 個大小為 $\frac{N}{4} \times \frac{N}{4}$ 的子矩陣（故分割基底 $b = 4$），且僅需 47 次子矩陣乘法（故子問題數量 $a = 47$）。

2. 建立遞迴關係式：
   $T(N) = 47 T\left(\frac{N}{4}\right) + O(N^2)$

核心觀念

1. 均勻隨機排列（Uniformly Random Permutation）與 Fisher-Yates 洗牌演算法：

   • 長度為 $n$ 的陣列 $A$ 共有 $n!$ 種不同的排列方式。若一個隨機化演算法能生成「均勻隨機排列」，則每一種排列產生的機率必須精確等於 $\frac{1}{n!}$。
   • 根據經典的 Fisher-Yates 隨機洗牌演算法（即《Introduction to Algorithms》CLRS 中的 RANDOMIZE-IN-PLACE），在第 $i$ 輪迴圈迭代時（$i = 1, 2, \dots, n$），必須將位於位置 $i$ 的元素與從剩餘未確定區間 $\{i, i+1, \dots, n\}$ 中均勻隨機選出的元素進行交換。

2. 迴圈不變性（Loop Invariant）：

   • 不變性條件：在第 $i$ 輪迴圈執行前，子陣列 $A[1 \dots i-1]$ 包含從原本 $n$ 個元素中均勻選出的 $i-1$ 個元素之任意排列，且每一種可能的 $(i-1)$-排列出現機率均為 $\frac{(n - (i - 1))!}{n!} = \frac{(n-i+1)!}{n!}$。
   • 終止條件：當迴圈結束（$i = n + 1$）時，子陣列 $A[1 \dots n]$ 即形成完整的均勻隨機排列，其出現機率為 $\frac{1}{n!}$。

解題方法

為了確保演算法產生的每種排列機率皆為 $\frac{1}{n!}$，必須保證在第 $i$ 步時，從包含位置 $i$ 及其後續共 $n - i + 1$ 個候選位置中，以相等的機率 $\frac{1}{n - i + 1}$ 隨機選擇一個索引與 $A[i]$ 交換。

1. 關鍵推導與機率計算：
   • 第 $i = 1$ 步：從 $A[1 \dots n]$ 的 $n$ 個位置中隨機選擇一個放入 $A[1]$，選擇機率為 $\frac{1}{n}$。
   • 第 $i = 2$ 步：從 $A[2 \dots n]$ 的 $n-1$ 個位置中隨機選擇一個放入 $A[2]$，選擇機率為 $\frac{1}{n-1}$。
   • 第 $i$ 步：從 $A[i \dots n]$ 的 $n - i + 1$ 個位置中隨機選擇一個放入 $A[i]$，選擇機率為 $\frac{1}{n - i + 1}$。
   • 生成任何特定排列的總機率為各步選擇機率之連乘積：
     $P = \frac{1}{n} \times \frac{1}{n-1} \times \frac{1}{n-2} \times \dots \times \frac{1}{1} = \frac{1}{n!}$
   • 由此可明確導出：隨機抽樣區間的下界必須為 $a = i$，上界必須為 $b = n$。

核心觀念

本題考驗計算複雜度理論（Computational Complexity Theory）中**多項式時間歸約（Polynomial-time Reduction）**的嚴格定義，以及複雜度類別 $\text{P}$、$\text{NP}$、$\text{NP-complete}$ 與 $\text{NP-hard}$ 的性質。

1. 多項式時間多一歸約（Polynomial-time Many-one Reduction / Karp Reduction）定義：
   語言（問題）$A$ 可在多項式時間內歸約至語言 $B$（記為 $A \le_P B$），當且僅當存在一個可在多項式時間內計算的函數 $f: \Sigma^* \to \Sigma^*$，使得對所有輸入字串 $x$，下列條件恆成立：
   $x \in A \iff f(x) \in B$
   這意味著 $B$ 的難度「至少與 $A$ 一樣高」（或 $A$ 的難度不大於 $B$）。

2. 極端語言（Trivial Languages）：

   • 空集合 $\emptyset$ 與全集合 $\Sigma^*$ 皆屬於 $\text{P} \subseteq \text{NP}$（可在 $O(1)$ 時間內判定）。
   • 對於任何非空且非全集（即非平凡，Non-trivial）的語言 $A$：
     • 若歸約至 $B = \emptyset$，則對任意 $x \in A$，$f(x) \in \emptyset$ 永遠為假，無法滿足 $x \in A \iff f(x) \in B$。
     • 若歸約至 $B = \Sigma^*$，則對任意 $x \notin A$，$f(x) \in \Sigma^*$ 永遠為真，亦無法滿足 $x \in A \iff f(x) \in B$。
   • 結論：任何非平凡語言都無法多項式時間歸約至 $\emptyset$ 或 $\Sigma^*$。

解題方法

要判斷一個敘述「Every problem in class $\mathcal{C}$ is polynomial-time reducible to every problem in $\text{NP}$」是否已知為真，必須驗證是否對 $\text{NP}$ 中的每一個問題 $B$（包含極端問題 $\emptyset$ 與 $\Sigma^*$）都能找到對應的歸約函數。

1. 反例檢驗法（極端語言）：
   因為 $\emptyset \in \text{NP}$ 且 $\Sigma^* \in \text{NP}$，若選項所述的語言集合包含任何非平凡問題，該問題便無法歸約至 $\emptyset$ 或 $\Sigma^*$，導致敘述不成立。

2. 複雜度難易度邏輯：
   若問題 $A$ 比問題 $B$ 更難（例如 $A \notin \text{P}$ 而 $B \in \text{P}$），除非 $\text{P} = \text{NP}$，否則不可能存在 $A \le_P B$。目前已知科學界並未證明 $\text{P} = \text{NP}$，因此不能假設此類歸約恆成立。

綜合以上兩點推導，選項 (A)、(B)、(C)、(D) 皆存在明確反例或依賴未證實之假設，故均非已知為真。

核心觀念

本題考驗計算複雜度理論（Computational Complexity Theory）中關於**多項式時間規約（Polynomial-time Reduction, $\le_P$）**以及複雜度類別 $\text{P}$、$\text{NP}$、$\text{NP-Hard}$、$\text{NP-Complete}$ 與 $\text{EXPTIME}$ 的基本定義與定理性質。

關鍵定義與性質

1. 多項式時間規約（$A \le_P B$）：若問題 $A$ 可在多項式時間內規約至問題 $B$，代表存在一個多項式時間可計算的函數 $f$，使得對所有輸入 $x$，$x \in A \iff f(x) \in B$。規約表示「問題 $A$ 的難度不超過問題 $B$」；若 $B$ 可在某時間複雜度內解決，則 $A$ 亦可在該複雜度加上規約時間後解決。
2. $\text{NP}$ 類別：可在非確定性多項式時間（Nondeterministic Polynomial Time）內解決的判定問題集合。
3. $\text{NP-Hard}$ 類別：若一個問題 $H$ 滿足「對所有 $L \in \text{NP}$，皆有 $L \le_P H$」，則稱 $H$ 為 $\text{NP-Hard}$。
4. $\text{NP-Complete}$ 類別：若問題 $C$ 同時滿足 (1) $C \in \text{NP}$ 且 (2) $C \in \text{NP-Hard}$，則稱 $C$ 為 $\text{NP-Complete}$。
5. 複雜度類別包含關係：
   $\text{P} \subseteq \text{NP} \subseteq \text{EXPTIME}$
   其中 $\text{EXPTIME}$ 為可在確定性指數時間（$O(2^{n^k})$）內解決的問題集合。

解題方法

針對題目中的四個敘述，依序運用計算複雜度理論的定理與定義檢驗其是否「已被證明為真（Known to be true）」：

1. 檢驗敘述一與敘述二：根據 Cook-Levin 定理，已知存在 $\text{NP-Complete}$ 問題（例如 SAT、3-SAT）。由 $\text{NP-Hard}$ 與 $\text{NP-Complete}$ 的定義即可判斷任何 $\text{NP}$ 問題是否都能規約至這些問題。
2. 檢驗敘述三：分析若所有 $\text{NP}$ 問題皆可規約至 $\text{P}$ 類別問題時會導出何種結論，並判斷該結論是否為已知事實。
3. 檢驗敘述四：利用包含關係 $\text{NP} \subseteq \text{EXPTIME}$ 以及恆等規約（Identity Reduction）來驗證其正確性。

最後統計已知為真的敘述數量並選出對應選項。

選項分析

敘述逐一分析

• 敘述一：Every problem in NP is polynomial-time reducible to some NP-hard problem.

  • 分析：正確（Known to be true）。
  • 推導：根據 $\text{NP-Hard}$ 的定義，問題 $H$ 為 $\text{NP-Hard}$ 當且僅當對任意 $L \in \text{NP}$，均滿足 $L \le_P H$。根據 Cook-Levin 定理，3-SAT 是一個 $\text{NP-Complete}$ 問題，因此 3-SAT 必然屬於 $\text{NP-Hard}$。故對於任意 $A \in \text{NP}$，皆滿足 $A \le_P \text{3-SAT}$。因此，所有 $\text{NP}$ 問題都能多項式時間規約至某個 $\text{NP-Hard}$ 問題（例如 3-SAT），此敘述已知為真。

• 敘述二：Every problem in NP is polynomial-time reducible to some NP-complete problem.

  • 分析：正確（Known to be true）。

核心觀念

本題考查圖論（Graph Theory）中的二分圖匹配（Bipartite Matching）與完美匹配（Perfect Matching）。

• 二分圖（Bipartite Graph）：頂點集可劃分為兩個互斥的集合 $W$（工人集合）與 $T$（工作集合），且圖中的每一條邊皆跨越兩集合（即一端點屬於 $W$，另一端點屬於 $T$）。
• 匹配（Matching）：邊集的子集 $M$，滿足 $M$ 中任意兩條邊都沒有共同的頂點（即每位工人至多分配給一項工作，每項工作至多分配給一位工人）。
• 最大匹配（Maximum Matching）：包含邊數最多的匹配，其邊數稱為最大匹配大小（Size of Maximum Matching）。
• 完全匹配／完美匹配（Perfect Matching）：當二分圖兩側頂點數相等（$|W| = |T| = n$），且存在一個大小為 $n$ 的匹配（即所有頂點均成功配對）時，該匹配即為完美匹配。

解題方法

1. 建立二分圖模型：

   • 工人集合 $W = \{W_1, W_2, W_3\}$
   • 工作集合 $T = \{T_1, T_2, T_3\}$
   • 可執行工作的相連邊為：
     • 工人 $W_1$ 可執行：$T_1, T_2 \implies$ 邊為 $(W_1, T_1), (W_1, T_2)$
     • 工人 $W_2$ 可執行：$T_1 \implies$ 邊為 $(W_2, T_1)$
     • 工人 $W_3$ 可執行：$T_3 \implies$ 邊為 $(W_3, T_3)$

2. 推導最大匹配：

   • 觀察度數（Degree）限制：
     • 工人 $W_3$ 只有單一選擇 $T_3$，故若要匹配 $W_3$，必須選擇 $(W_3, T_3)$。
     • 工人 $W_2$ 只有單一選擇 $T_1$，故若要匹配 $W_2$，必須選擇 $(W_2, T_1)$。
   • 分配工人 $W_1$：
     • 工作 $T_1$ 已被 $W_2$ 佔用，因此 $W_1$ 僅剩工作 $T_2$ 可選，即選擇 $(W_1, T_2)$。
   • 組合出匹配集合：

本題的核心考點為 Knuth-Morris-Pratt (KMP) 演算法 中的 前綴函數 (Prefix Function / Failure Function $\pi$) 之計算。前綴函數 $\pi[i]$ 定義為子字串 $S[0 \dots i]$ 的**最長真前綴（Proper Prefix）同時也是真後綴（Proper Suffix）**的長度。掌握此觀念的關鍵在於理解：

• 真前綴與真後綴：不可包含整個子字串本身（長度必須嚴格小於 $i+1$）。
• 轉移與回溯（Backtracking）機制：當字串比對失敗時，利用先前計算好的 $\pi$ 值快速跳轉，避免重複比對，達到線性時間複雜度。

完整解題過程與詳細推導

題目細節與印錯勘誤說明

若依題幹印出的字串 $S = \text{wwvwuv}$（長度為 6），其 0-based 前綴函數計算結果應為長度 6 的陣列 $\pi[0 \dots 5] = [0, 1, 0, 1, 0, 0]$。
然而觀察各選項：

• 選項 (A) 包含 7 個元素：$[0, 1, 0, 1, 2, 0, 0]$
• 其餘選項皆包含 8 個元素。

對照字串結構與選項 (A) 的數值可發現，原題目的完整字串應為長度為 7 的 $S = \text{wwvwwuv}$（第 4 個字元為 $\text{w}$，題目漏印了一個 $\text{w}$），其對應的前綴函數範圍為 $\pi[0 \dots 6]$。以下依據 KMP 前綴函數定義對 $S = \text{wwvwwuv}$ 進行逐字元詳細推導：

逐一計算 $\pi[i]$：

1. $i = 0$ ($S[0 \dots 0] = \text{"w"}$)：

   • 子字串長度為 1，其真前綴與真後綴皆僅有空字串 $\varepsilon$。
   • 因此 $\pi[0] = 0$。

2. $i = 1$ ($S[0 \dots 1] = \text{"ww"}$)：

   • 真前綴集合：$\{\text{"w"}\}$
   • 真後綴集合：$\{\text{"w"}\}$
   • 最長相同前後綴為 $\text{"w"}$，長度為 1。
   • 因此 $\pi[1] = 1$。

3. $i = 2$ ($S[0 \dots 2] = \text{"wwv"}$)：

   • 真前綴集合：$\{\text{"w"}, \text{"ww"}\}$
   • 真後綴集合：$\{\text{"v"}, \text{"wv"}\}$
   • 無任何重疊交集，最長相同前後綴長度為 0。
   • 因此 $\pi[2] = 0$。

4. $i = 3$ ($S[0 \dots 3] = \text{"wwvw"}$)：

   • 真前綴集合：$\{\text{"w"}, \text{"ww"}, \text{"wwv"}\}$
   • 真後綴集合：$\{\text{"w"}, \text{"vw"}, \text{"wvw"}\}$
   • 最長相同前後綴為 $\text{"w"}$，長度為 1。
   • 因此 $\pi[3] = 1$。

5. $i = 4$ ($S[0 \dots 4] = \text{"wwvww"}$)：

   • 真前綴集合：$\{\text{"w"}, \text{"ww"}, \text{"wwv"}, \text{"wwvw"}\}$
   • 真後綴集合：$\{\text{"w"}, \text{"ww"}, \text{"vww"}, \text{"wvww"}\}$

核心觀念

本題考驗**離散傅立葉變換（Discrete Fourier Transform, DFT）**與 Cooley-Tukey 快速傅立葉變換演算法（Fast Fourier Transform, FFT） 的核心數學性質。

傳統 DFT 計算 $N$ 點多項式求值的時間複雜度為 $O(N^2)$。Cooley-Tukey 演算法利用分治法（Divide-and-Conquer）將複雜度降低至 $O(N \log N)$，其關鍵在於 $N$ 次單位複數根（Roots of Unity） $W_N = e^{2\pi i / N}$ 所具備的折半性質（Halving Lemma）與對稱性質（Symmetry Property / Negation Lemma）。

解題方法

假設有一 $N-1$ 次多項式：
$A(x) = \sum_{j=0}^{N-1} a_j x^j$

將 $A(x)$ 依據係數下標的奇偶性拆分為偶數項多項式 $A_{\text{even}}(x)$ 與奇數項多項式 $A_{\text{odd}}(x)$：
$A(x) = A_{\text{even}}(x^2) + x \cdot A_{\text{odd}}(x^2)$
其中：
$A_{\text{even}}(y) = \sum_{j=0}^{N/2-1} a_{2j} y^j, \quad A_{\text{odd}}(y) = \sum_{j=0}^{N/2-1} a_{2j+1} y^j$

當我們在 $x = W_N^k$ （其中 $0 \le k < N/2$）評估多項式時，利用折半性質 $W_N^{2k} = W_{N/2}^k$ 可得：
$A(W_N^k) = A_{\text{even}}(W_{N/2}^k) + W_N^k \cdot A_{\text{odd}}(W_{N/2}^k)$

而評估後半段 $x = W_N^{k + N/2}$ 時，利用對稱性質 $W_N^{k + N/2} = -W_N^k$ 與 $W_N^{2(k+N/2)} = W_N^{2k + N} = W_N^{2k} = W_{N/2}^k$ 可得：
$A(W_N^{k + N/2}) = A_{\text{even}}(W_{N/2}^k) - W_N^k \cdot A_{\text{odd}}(W_{N/2}^k)$

關鍵推導結論：

透過對稱性質 $W_N^{k + N/2} = -W_N^k$，只要計算出子問題 $A_{\text{even}}(W_{N/2}^k)$ 與 $A_{\text{odd}}(W_{N/2}^k)$，就能同時在 $O(1)$ 時間內算出 $A(W_N^k)$ 與

在 0‑index 陣列 $A=[0,4,5,10,3,2,8]$，$n=7$，BUILD‑MAX‑HEAP 從最後一個非葉節點 $i=\lfloor n/2\rfloor-1=2$ 開始向上呼叫 MAX‑HEAPIFY。

1. i = 2

   • 左子 $A[5]=2$，右子 $A[6]=8$，最大為 $8$。
   • 交換 $A[2]\leftrightarrow A[6]$ → $[0,4,8,10,3,2,5]$。

2. i = 1

   • 左子 $A[3]=10$，右子 $A[4]=3$，最大為 $10$。

核心觀念

本題考查**快速排序（Quicksort）**的樞紐（Pivot）選擇策略及其對時間複雜度的影響。

1. 分治法與遞迴樹結構：Quicksort 採用分治法（Divide and Conquer）。將大小為 $n$ 的問題分割為兩個子問題，其時間複雜度遞迴式為：
   $T(n) = T(k) + T(n - 1 - k) + \Theta(n)$
   其中 $k$ 與 $n - 1 - k$ 為劃分（Partition）後兩個子陣列的長度（$0 \le k \le n-1$）。
2. 最壞時間複雜度 $O(n^2)$：當樞紐選擇極度不平均（例如每次皆選到當前陣列的最大值或最小值，導致 $k = 0$ 或 $k = n-1$）時，遞迴樹深度退化至 $O(n)$，總比較次數為：
   $\sum_{i=1}^{n} (i - 1) = \frac{n(n-1)}{2} = \Theta(n^2)$
3. 隨機化演算法（Randomized Quicksort）：透過隨機選擇樞紐（Select a random element），使算法表現與輸入資料的初始排列順序解耦（Decoupled）。對於任意輸入分佈（Arbitrary Input Distributions），其**期望時間複雜度（Expected Time Complexity）**均保持為 $O(n \log n)$，有效消除特定惡意輸入（Adversarial Input）引發 $O(n^2)$ 最壞情況的風險。

解題方法

Quicksort 的效能完全取決於劃分點的平衡度：

• 理想劃分：若樞紐始終能將陣列大致對分（例如 $k \approx n/2$），遞迴樹深度為 $O(\log n)$，時間複雜度為最佳與平均的 $O(n \log n)$。
• 確定性樞紐策略的局限：任何固定的選擇規則（如固定選首項、尾項、或特定位置的極值）都是確定性演算法（Deterministic Algorithm）。對於確定性策略，必然存在某種特定的輸入排列（例如已排序或逆序陣列），使得每一次劃分都落在極端邊界（$k=0$），從而觸發最壞時間複雜度 $O(n^2)$。
• 隨機化樞紐策略的優勢：在每次劃分前，隨機均勻選取一個元素作為樞紐。選中落在中間 $50\%$ 範圍（即第 $25$ 百分位數與第 $75$ 百分位數之間）的樞紐之概率恆為 $1/2$。即便面對惡意設計的輸入資料，隨機數產生器確保了每次劃分極大概率能有效縮減問題規模。經推導證明，隨機化 Quicksort 的期望比較次數為：
  $E[T(n)] = 2n \ln n + O(n) = \Theta(n \log n)$

核心觀念

桶排序（Bucket Sort） 是一種基於數值分佈假設的非比較型／分配型排序演算法。其基本運作原理如下：

1. 將區間 $[0, 1)$ 平均劃分為 $n$ 個子區間（稱為「桶」, Buckets）。
2. 將 $n$ 個輸入元素依據數值映射至對應的桶中。
3. 對每一個桶內部的元素分別進行排序（通常採用 Insertion Sort）。
4. 依序收集並串聯所有桶中的元素，完成排序。

Bucket Sort 能達到期望線性時間複雜度 $O(n)$ 的核心統計前提為：輸入資料必須獨立且均勻分佈（Uniformly Distributed）於給定區間內。在此假設下，每個桶分得的元素數量期望值為 $O(1)$，進而保證整體排序時間與元素數量 $n$ 成正比。

解題方法

推導與複雜度分析：

1. 基本假設與變數設定：
   設輸入陣列長度為 $n$，劃分出 $k$ 個桶子（標準演算法通常取 $k = n$）。假設輸入資料均勻分佈於區間 $[0, 1)$。

2. 單一桶子內元素量的統計特性：
   任一元素落入第 $i$ 個桶子的機率為 $p = \frac{1}{k} = \frac{1}{n}$。
   設第 $i$ 個桶子內含有的元素個數為隨機變數 $n_i$，則 $n_i$ 服從二項分佈 $\text{Binomial}(n, p)$。
   其二次矩（Second Moment）期望值計算如下：
   $E[n_i^2] = \text{Var}(n_i) + (E[n_i])^2 = n p (1 - p) + (n p)^2$
   將 $p = \frac{1}{n}$ 代入：
   $E[n_i^2] = n \cdot \frac{1}{n} \left(1 - \frac{1}{n}\right) + \left(n \cdot \frac{1}{n}\right)^2 = 1 - \frac{1}{n} + 1 = 2 - \frac{1}{n}$

3. 總執行時間期望值計算：
   Bucket Sort 的總執行時間包含三個部分：

   • 散列與配置元素至各桶：$\Theta(n)$
   • 對各桶執行 Insertion Sort（單一桶耗時 $O(n_i^2)$）：$\sum_{i=0}^{n-1} O(n_i^2)$
   • 串聯所有桶內元素：$\Theta(n)$

   計算總時間 $T(n)$ 的期望值：
   $E[T(n)] = \Theta(n) + \sum_{i=0}^{n-1} O(E[n_i^2])$
   代入 $E[n_i^2] = 2 - \frac{1}{n} = O(1)$：
   $E[T(n)] = \Theta(n) + \sum_{i=0}^{n-1} O(1) = \Theta(n) + O(n) = O(n)$

核心觀念

• 順序統計量（Order Statistics）與中位數（Median）：在含有 $n$ 個元素的未排序陣列中，尋找第 $k$ 小元素（第 $k$ 階順序統計量）的過程稱為選擇問題（Selection Problem）。當 $k = \lfloor n/2 \rfloor$ 或 $\lceil n/2 \rceil$ 時，即為中位數。
• 最壞時間複雜度（Worst-case Time Complexity）：題目重點在於「保證（guarantees）」與「最壞時間複雜度（worst-case time）」。
• Median-of-Medians 演算法（BFPRT 演算法）：由 Blum、Floyd、Pratt、Rivest 與 Tarjan 五位學者提出的確定性選擇演算法。透過將陣列劃分為若干個大小為 5 的小組，遞迴求出「中位數的中位數」作為 Pivot（基準值），從而確保每一次 Partition 都能排除固定比例的元素，將最壞時間複雜度嚴格控制在 $O(n)$。

解題方法

本題評量對各種尋找中位數／順序統計量演算法時間複雜度的掌握度。

1. BFPRT（Median-of-Medians）演算法的遞迴式與證明：
   將 $n$ 個元素每 5 個分為一組，共有 $\lceil n/5 \rceil$ 組：
   • 找出每組的中位數：耗時 $O(n)$。
   • 遞迴尋找這 $\lceil n/5 \rceil$ 個中位數的中位數作為 Pivot $x$：耗時 $T(\lceil n/5 \rceil)$。
   • 以 $x$ 進行 Partition：至少有約半數的組，其組內中位數大於等於 $x$，而在這些組中又有至少 3 個元素大於等於 $x$（組內中位數本身及比它大的 2 個元素）。因此，大於等於 $x$ 的元素數量至少為：
     $3 \times \left( \left\lceil \frac{1}{2} \left\lceil \frac{n}{5} \right\rceil \right\rceil - 2 \right) \ge \frac{3n}{10} - 6$
   • 同理，小於等於 $x$ 的元素數量也至少為 $\frac{3n}{10} - 6$。因此劃分後，較大一方的子陣列元素數量至多為 $\frac{7n}{10} + 6$。
   • 整體時間複雜度遞迴式可寫為：
     $T(n) \le T\left(\left\lceil \frac{n}{5} \right\rceil\right) + T\left(\frac{7n}{10} + 6\right) + O(n)$
   • 利用代入法（Substitution Method）假設 $T(n) \le c n$，可解得 $T(n) = O(n)$。因此該演算法能確定保證最壞情況為 $O(n)$。

選項分析

• (A) Sorting the array and then picking the median.（錯誤）
  基於比較的排序演算法（如 Quick Sort、Merge Sort、Heap Sort）在最壞情況下的時間複雜度下界為 $\Omega(n \log n)$。

核心觀念

本題考查的核心觀念為雙堆疊實作佇列（Queue via Two Stacks）以及均攤分析（Amortized Analysis）。

1. 資料結構特性：

   • 堆疊（Stack）遵從後進先出（LIFO, Last-In-First-Out）原則，Push 與 Pop 操作之時間複雜度均為 $O(1)$。
   • 佇列（Queue）遵從先進先出（FIFO, First-In-First-Out）原則。
   • 利用兩個堆疊 $S_{in}$ 與 $S_{out}$，其中 $S_{in}$ 負責接收新進元素（ENQUEUE），$S_{out}$ 負責輸出元素（DEQUEUE）。當 $S_{out}$ 為空且執行 DEQUEUE 時，將 $S_{in}$ 中的所有元素依序 Pop 並 Push 至 $S_{out}$，可將 LIFO 順序翻轉為 FIFO 順序。

2. 均攤分析（Amortized Analysis）：

   • 用於評估一連串操作（Sequence of Operations）中，平均每次操作所花費的時間上限。即使個別操作在最壞情況下耗時較長，若發生頻率極低，整體平均成本仍可維持在較低的常數階層。
   • 主要分析方法包含：聚合分析法（Aggregate Method）與位能法（Potential Method）。

解題方法

此題可分別透過聚合分析法與位能法進行精確推導。

方法一：聚合分析法（Aggregate Analysis）

考慮由 $m$ 個合法佇列操作組成的序列，初始狀態佇列為空。

1. 單一元素的生命週期分析：
   對於任意一個加入佇列的元素 $z$，在整個操作序列中，最多只會經歷以下 4 次堆疊操作：

   • ENQUEUE 時：Push 入 $S_{in}$（1 次 Push）。
   • 轉移至 $S_{out}$ 時：從 $S_{in}$ Pop 出（1 次 Pop），並 Push 入 $S_{out}$（1 次 Push）。
   • DEQUEUE 時：從 $S_{out}$ Pop 出（1 次 Pop）。

2. 總成本計算：
   在 $m$ 次佇列操作中，最多只能 ENQUEUE $m$ 個元素。因此，所有元素在整個生命週期中所產生的堆疊操作總次數上限為：
   $4 \times m = 4m$
   除堆疊操作外，每次 ENQUEUE 與 DEQUEUE 的條件判斷與控制流程時間均為 $O(1)$。因此 $m$ 次佇列操作的總花費時間上限為 $O(m)$。

3. 均攤成本：
   每次操作的平均（均攤）成本為：
   $\text{Amortized Cost} = \frac{\text{Total Cost}}{m} = \frac{O(m)}{m} = O(1)$

方法二：位能法（Potential Method）

定義位能函數 $\Phi(D) = 2 \cdot |S_{in}|$，其中 $|S_{in}|$ 表示堆疊 $S_{in}$ 中的元素個數。

• 初始狀態：$D_0$ 為空佇列，$\Phi(D_0) = 0$。
• 合法性：對任意狀態 $D_i$，由於 $|S_{in}| \ge 0$，故 $\Phi(D_i) \ge \Phi(D_0) = 0$ 恆成立。

對第 $i$ 次佇列操作計算真實成本 $c_i$ 與均攤成本 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$：

在使用separate chaining的雜湊表，所有元素均放在長度為 $m$ 的陣列的桶中，每個桶含一條鏈表。
當加入 $n$ 個鍵後，負載係數 $\alpha = \frac{n}{m}$，平均鏈長即為 $\alpha$。若 $\alpha$ 持續增大，鏈表長度將與 $n$ 成線性關係，導致搜尋、插入、刪除的期望時間從 $O(1)$ 退化為 $O(\alpha)=O(n)$.