111 年 國立臺灣大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

本題考查選擇排序法（Selection Sort）的時間複雜度分析，特別是其期望時間複雜度（Expected Time Complexity / Average-case Time Complexity）。

選擇排序法的基本原理為：在未排序的序列中尋找最小（或最大）元素，將其與未排序序列的第一個元素交換位置；接著在剩餘未排序元素中重複此過程，直到所有元素皆完成排序。

解題方法

對於包含 $n$ 個元素的陣列，選擇排序法的執行過程與比較次數推導如下：

1. 比較次數分析：

   • 第 $1$ 輪：在 $n$ 個未排序元素中尋找最小值，需要 $n-1$ 次比較。
   • 第 $2$ 輪：在 $n-1$ 個未排序元素中尋找最小值，需要 $n-2$ 次比較。
   • 依此類推，第 $i$ 輪需要 $n-i$ 次比較。
   • 第 $n-1$ 輪：最後在 $2$ 個未排序元素中尋找最小值，需要 $1$ 次比較。

   總比較次數 $C(n)$ 為等差級數求和：
   $C(n) = \sum_{i=1}^{n-1} (n - i) = (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$

2. 資料交換次數分析：
   每一輪最多進行 $1$ 次元素交換，總交換次數最多為 $n-1$ 次，時間複雜度為 $O(n)$。

3. 綜合複雜度評估：
   由於比較次數完全取決於迴圈次數，不受輸入資料初始排列順序（如已排序、反向排序或隨機分佈）之影響，因此選擇排序法在最佳情況（Best case）、最壞情況（Worst case）與平均／期望情況（Average/Expected case）下，其比較次數恆為 $\frac{n(n-1)}{2}$。

核心觀念

本題考查合併排序法（Merge Sort）的時間複雜度分析，特別是期望時間複雜度（Expected Time Complexity / Average-case Time Complexity）。

涉及的核心觀念與工具如下：

1. 分治法（Divide and Conquer）：將大問題分割為兩個大小約為一半的子問題，遞迴求解後再將結果合併。
2. 確定性排序（Deterministic Sorting）：Merge Sort 的分割與合併過程不依賴資料的初始順序或隨機選擇 Pivot（與 Quick Sort 不同），因此其最佳（Best）、最壞（Worst）與期望/平均（Expected/Average）時間複雜度完全相同。
3. 遞迴關係式與主定理（Master Theorem）：用於求解分治演算法的時間複雜度。

解題方法

Step 1：建立 Merge Sort 的遞迴關係式

假設處理長度為 $n$ 的陣列所需時間為 $T(n)$：

1. Divide（分割）：找出陣列中點，將陣列切分為兩半，耗時 $\Theta(1)$。
2. Conquer（解決）：遞迴對左右兩個長度各為 $n/2$ 的子陣列進行 Merge Sort，耗時 $2T(n/2)$。
3. Combine（合併）：將兩個已排序的子陣列合併為一個排序陣列。不管元素初始順序為何，合併過程所需的比較與複製次數均為 $\Theta(n)$。

綜上所述，Merge Sort 的遞迴關係式為：
$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$

Step 2：求解遞迴關係式

方法一：主定理（Master Theorem）

對於標準遞迴式 $T(n) = a T(n/b) + f(n)$：

• $a = 2$
• $b = 2$
• $f(n) = \Theta(n)$

計算臨界值 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$。
因為 $f(n) = \Theta(n^{\log_b a}) = \Theta(n)$，符合主定理之 Case 2：
$T(n) = \Theta(n^{\log_b a} \cdot \log n) = \Theta(n \log n)$

方法二：遞迴樹法（Recursion Tree Method）

1. 樹的根節點代價為 $c \cdot n$。
2. 第 $1$ 層有 $2$ 個節點，每個節點代價為 $c \cdot (n/2)$，該層總代價為 $c \cdot n$。

核心觀念

本題考查**最大堆積（Max-Heap）**的核心操作 MAX-HEAPIFY 的時間複雜度分析。

1. 最大堆積的樹高性質：包含 $n$ 個元素的完全二元樹（Complete Binary Tree），其樹高（Height）為 $h = \lfloor \lg n \rfloor$。
2. MAX-HEAPIFY 運作機制：MAX-HEAPIFY 是一個向下調整（Shift-down / Bubble-down）的維護過程。當某節點的左右子樹皆已滿足 Max-Heap 性質，但該節點自身鍵值小於其子節點時，MAX-HEAPIFY 會將該節點與較大的子節點交換，並持續向下調整，直到滿足 Max-Heap 性質或到達葉節點（Leaf）為止。
3. 時間複雜度界限：在高度為 $h$ 的節點上執行 MAX-HEAPIFY，每下降一層所需的比較與交換時間為 $O(1)$，故時間複雜度正比於該節點的高度 $h$，即 $O(h)$。在大小為 $n$ 的堆積中，最大樹高為 $\lfloor \lg n \rfloor$，因此其漸近時間複雜度界限為 $O(\lg n)$。

解題方法

步驟一：分析單次 MAX-HEAPIFY 的執行路徑

設堆積大小為 $n$，對於給定的節點 $i$：

• 比較節點 $i$ 與其左子節點 LEFT(i)、右子節點 RIGHT(i) 的鍵值（Key）。
• 若根節點非最大值，則與較大者交換，並對該子節點繼續實施 MAX-HEAPIFY。
• 最壞情況與期望情況下，下沉路徑長度皆不會超過堆積的總高度 $h = \lfloor \lg n \rfloor$。

步驟二：時間複雜度遞迴式與推導

對於包含 $n$ 個節點的 Max-Heap 根節點，其子樹大小最多為 $2n/3$（當底層半滿時的最壞情況）。MAX-HEAPIFY 沿著單一路徑向下移動，每層僅執行常數次 $O(1)$ 的比較與交換：
$T(n) \le T(2n/3) + \Theta(1)$

核心觀念

快速排序（Quick Sort）是一種採用「分治法」（Divide and Conquer）的比較排序演算法，其基本運作過程包含三個步驟：

1. 基準值選擇（Pivot Selection）：從子陣列中挑選出一個元素作為 Pivot。
2. 分割（Partition）：重排陣列，使小於 Pivot 的元素皆位於其左側，大於或等於 Pivot 的元素皆位於其右側。此步驟花費 $\Theta(n)$ 時間。
3. 遞迴求解（Recursion）：分別對左、右兩個子陣列重複進行 Quick Sort。

Quick Sort 的最壞時間複雜度（Worst-case Time Complexity）取決於分割（Partition）結果是否極度不對稱。當每次選擇的 Pivot 恰好都是當前子陣列的極值（極大值或極小值）時，分割將無法有效縮減問題規模，導致演算法結構退化成單向的線性遞迴。

解題方法

1. 建立遞迴關係式

設處理長度為 $n$ 的陣列所需之時間複雜度為 $T(n)$。

在最壞狀況（Worst Case）下，每次 Partition 操作後，分割出的兩個子陣列長度分別為 $0$ 與 $n - 1$：

• 處理長度為 $0$ 的子陣列需 $T(0) = O(1)$
• 處理長度為 $n - 1$ 的子陣列需 $T(n - 1)$
• 當前層級的 Partition 掃描時間為 $\Theta(n)$

因此，最壞狀況下的遞迴關係式（Recurrence Relation）為：
$T(n) = T(n - 1) + T(0) + \Theta(n)$

忽略常數項後可寫為：
$T(n) = T(n - 1) + c \cdot n \quad (c > 0 \text{ 為常數})$

2. 展開與級數求和

利用展開法（Substitution / Unrolling Method）逐步替換 $T(n - 1)$：
$T(n) = T(n - 2) + c(n - 1) + cn$
$T(n) = T(n - 3) + c(n - 2) + c(n - 1) + cn$
$\vdots$
$T(n) = T(1) + c \sum_{i=2}^{n} i$

根據等差級數公式 $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$，可得：
$T(n) = O(1) + c \cdot \left[ \frac{n(n + 1)}{2} - 1 \right] = \Theta(n^2)$

故 Quick Sort 在最壞狀況下的時間複雜度為 $O(n^2)$。

核心觀念

本題考驗**桶排序（Bucket Sort）的演算法運作機制、時間複雜度分析，以及概率論中的期望值（Expected Time Complexity）**推導。

Bucket Sort 是一種非比較型的排序演算法，其基本原理如下：

1. 假設條件：假設輸入資料均勻獨立地位於區間 $[0, 1)$ 上（Uniform Distribution）。
2. 分配至桶：將 $[0, 1)$ 劃分成 $m$ 個大小相同的區間（稱為桶, Buckets），將 $n$ 個輸入元素根據數值大小放入對應的桶中。
3. 桶內排序：對每個桶內的元素單獨進行排序（通常採用插入排序 Insertion Sort）。
4. 合併結果：按順序串聯所有桶中的元素即完成排序。

Bucket Sort 的總執行時間由三部分組成：
$T(n) = \Theta(n) + \sum_{i=1}^{m} O(n_i^2) + \Theta(m)$
其中：

• $\Theta(n)$ 為將 $n$ 個元素指派至對應桶的時間。
• $n_i$ 為第 $i$ 個桶中的元素個數，$O(n_i^2)$ 為對第 $i$ 個桶執行插入排序的時間。
• $\Theta(m)$ 為走訪並串聯 $m$ 個桶的時間。

解題方法

根據題意，輸入元素個數為 $n$，桶的數量為 $m = 6n$（即桶數與元素量成正比，$m = \Theta(n)$）。

數學推導步驟：

1. 單一桶內元素數量的概率分布：
   在均勻分布假設下，任意一個元素落入特定桶 $i$ 的機率為 $p = \frac{1}{m} = \frac{1}{6n}$。
   因此，第 $i$ 個桶中的元素個數 $n_i$ 服從參數為 $n$ 與 $p$ 的二項分布（Binomial Distribution）：$n_i \sim \text{Binomial}\left(n, \frac{1}{6n}\right)$。

2. 計算 $E[n_i^2]$ 的期望值：
   根據二項分布的性質：

   • 期望值 $E[n_i] = n \cdot p = n \cdot \frac{1}{6n} = \frac{1}{6}$
   • 變異數 $\text{Var}(n_i) = n \cdot p \cdot (1 - p) = \frac{1}{6}\left(1 - \frac{1}{6n}\right)$

   利用變異數定義式 $\text{Var}(n_i) = E[n_i^2] - (E[n_i])^2$，可得：

核心觀念

本題考查**原地排序演算法（In-place Sorting Algorithm）**的定義與常見排序演算法的空間複雜度（Space Complexity）。

1. 原地排序（In-place Sorting）的定義：
   若一個排序演算法在運作過程中，除了儲存原始資料所需的陣列空間外，僅額外需要常數大小的輔助空間（即 Auxiliary Space 為 $O(1)$），則稱該演算法為 In-place 排序演算法。
2. 常見排序演算法之輔助空間複雜度：
   • 氣泡排序（Bubble Sort）：額外空間複雜度為 $O(1)$，屬於 In-place。
   • 插入排序（Insertion Sort）：額外空間複雜度為 $O(1)$，屬於 In-place。
   • 堆積排序（Heap Sort）：額外空間複雜度為 $O(1)$，屬於 In-place。
   • 合併排序（Merge Sort）：標準實現需要額外大小為 $O(n)$ 的暫存陣列來進行合併（Merge）操作，不屬於 In-place。

解題方法

判斷一個排序演算法是否為 In-place 排序，關鍵在於分析其標準實現（Standard Implementation）下所使用的輔助空間（Auxiliary Space）：

1. 分析演算法在排序過程中額外宣告的變數、暫存陣列或遞迴呼叫堆疊（Recursion Stack）所佔用的空間。
2. 若輔助空間與資料量 $n$ 無關（即 $O(1)$），則判定為 In-place 排序。
3. 若輔助空間需要與資料量 $n$ 成正比（如 $O(n)$），則判定為非 In-place 排序。

根據上述原則，合併排序（Merge Sort）的標準分割與合併過程，在 Merge 階段必須將兩半邊已排序的元素複製到長度為 $n$ 的輔助陣列（Auxiliary Array）中進行比較與填回，故其輔助空間複雜度為 $O(n)$，並非 In-place 排序演算法。

選項分析

• (A) bubble sort（氣泡排序）：錯誤。
  氣泡排序透過重複比較與交換相鄰元素將最大值逐步移至尾端。整個過程僅需宣告一個用於暫存交換值的變數，輔助空間複雜度為 $O(1)$，因此屬於 In-place 排序演算法。

• (B) insertion sort（插入排序）：錯誤。
  插入排序將未排序的元素逐一插入已排序部分的適當位置。排序過程中僅需要常數個輔助變數來儲存目前欲插入的目標值與迴圈控制索引，輔助空間複雜度為 $O(1)$，因此屬於 In-place 排序演算法。

核心觀念

1. 最大堆積（Max-Heap）定義：
   最大堆積為一種完滿二元樹（Complete Binary Tree），滿足「任意節點的鍵值皆大於或等於其子節點鍵值」之特性。即對所有非根節點 $i$，皆滿足：
   $A[\text{parent}(i)] \ge A[i]$

2. 陣列儲存表示法（1-indexed）：
   若將根節點置於陣列索引 $1$ 的位置，對任意索引為 $i$ 的節點：

   • 父節點索引：$\text{parent}(i) = \lfloor i / 2 \rfloor$
   • 左子節點索引：$\text{left}(i) = 2i$
   • 右子節點索引：$\text{right}(i) = 2i + 1$

3. 堆積插入演算法（Percolate Up / Swim）：

   • 將新元素放入陣列末端（即當前完滿二元樹的第一個空位 $N$）。
   • 將該節點與其父節點 $\lfloor N / 2 \rfloor$ 比較；若新元素大於父節點，則兩者對調。
   • 重複向上比較與交換，直到新元素小於等於父節點，或已到達根節點（索引 $1$）為止。

解題方法

依序插入元素 $5, 4, 2, 6, 1, 3$，推導每一步驟之陣列內容變化：

1. 插入 $5$：

   • 置於索引 $1$。
   • 陣列狀態：[-, 5]

2. 插入 $4$：

   • 置於索引 $2$。
   • 父節點為索引 $\lfloor 2/2 \rfloor = 1$（數值 $5$）。因 $4 \le 5$，無需調整。
   • 陣列狀態：[-, 5, 4]

3. 插入 $2$：

   • 置於索引 $3$。
   • 父節點為索引 $\lfloor 3/2 \rfloor = 1$（數值 $5$）。因 $2 \le 5$，無需調整。
   • 陣列狀態：[-, 5, 4, 2]

4. 插入 $6$：

   • 置於索引 $4$。
   • 父節點為索引 $\lfloor 4/2 \rfloor = 2$（數值 $4$）。因 $6 > 4$，交換索引 $4$ 與索引 $2$ 的元素。
     • 暫時陣列：[-, 5, 6, 2, 4]
   • 目前位於索引 $2$，其父節點為索引 $\lfloor 2/2 \rfloor = 1$（數值 $5$）。因 $6 > 5$，交換索引 $2$ 與索引 $1$ 的元素。
   • 陣列狀態：[-, 6, 5, 2, 4]

5. 插入 $1$：

   • 置於索引 $5$。
   • 父節點為索引 $\lfloor 5/2 \rfloor = 2$（數值 $5$）。因 $1 \le 5$，無需調整。
   • 陣列狀態：[-, 6, 5, 2, 4, 1]

核心觀念
本題考驗二元搜尋樹（Binary Search Tree, BST）（或二元樹結構）的建構、節點指標鏈結關係以及樹的尋訪能力。
在二元搜尋樹中，對於任意節點 $u$：

1. 若其左子樹存在，則左子樹中所有節點的鍵值（Key）皆嚴格小於節點 $u$ 的鍵值，即 $\text{key}(\text{left\_child}(u)) < \text{key}(u)$。
2. 若其右子樹存在，則右子樹中所有節點的鍵值皆嚴格大於節點 $u$ 的鍵值，即 $\text{key}(\text{right\_child}(u)) > \text{key}(u)$。

解題方法
本題依存前題（第 7 題）之樹狀結構建構條件，在欠缺前題完整條件下，依據研究所考試常見之經典二元搜尋樹建構序列，假設前題為「將數值序列 $\langle 8, 3, 10, 1, 6, 14, 4, 7, 13 \rangle$ 依序插入一棵初始為空的二元搜尋樹（BST）」。

具體建構與尋訪步驟如下：

1. 依序插入元素建構 BST：
   • 插入 $8$：作為根節點（Root）。
   • 插入 $3$：因 $3 < 8$，進入 $8$ 的左分支，成為 $8$ 的左子節點。
   • 插入 $10$：因 $10 > 8$，進入 $8$ 的右分支，成為 $8$ 的右子節點。
   • 插入 $1$：因 $1 < 8$ 且 $1 < 3$，成為 $3$ 的左子節點。
   • 插入 $6$：因 $6 < 8$ 且 $6 > 3$，成為 $3$ 的右子節點。
   • 插入 $14$：因 $14 > 8$ 且 $14 > 10$，成為 $10$ 的右子節點。
   • 插入 $4$：因 $4 < 8$、$4 > 3$ 且 $4 < 6$，成為 $6$ 的左子節點。

核心觀念

本題考查**快速排序法（Quicksort）中分區（Partitioning）**步驟後樞紐元素（Pivot）的構造特性。

在快速排序法中，經過一次分區與 Pivot 定位後，作為 Pivot 的元素 $A[k]$ 必定已被放置於其最終排序後的正確位置，且必須嚴格滿足以下分區充要條件（Partition Property）：

1. 左側約束：Pivot 左側的所有元素，數值皆必須小於或等於 Pivot。即：
   $\max_{0 \le j \le k-1} A[j] \le A[k]$
2. 右側約束：Pivot 右側的所有元素，數值皆必須大於或等於 Pivot。即：
   $\min_{k+1 \le j \le n-1} A[j] \ge A[k]$

因此，一個元素 $A[i]$ 能成為第一次分區 Pivot 的條件，等價於該位置的**前綴最大值（Prefix Max）與後綴最小值（Suffix Min）**皆等於 $A[i]$ 本身：
$\text{PrefixMax}[i] = A[i] = \text{SuffixMin}[i]$

解題方法

本題題目文字因複製重複瑕疵導致原本 8 個元素的陣列僅完整顯示前 6 個數值 $[7, 11, 10, 17, 18, 30]$。在標準考試情境下，若將陣列補齊為合理的 8 元素序列（假設後續 2 個元素維持遞增且不小於 30，例如 $[7, 11, 10, 17, 18, 30, 35, 40]$），可透過雙向掃描法建立前綴最大值陣列與後綴最小值陣列進行判定。

步驟 1：建立前綴最大值與後綴最小值陣列

以包含補齊元素之陣列 $A = [7, 11, 10, 17, 18, 30, 35, 40]$ 為例：

• 原陣列 $A$：$[7, 11, 10, 17, 18, 30, 35, 40]$
• 前綴最大值 $\text{PrefixMax}$（由左至右累加最大值）：
  $\text{PrefixMax} = [7, 11, 11, 17, 18, 30, 35, 40]$
• 後綴最小值 $\text{SuffixMin}$（由右至左累加最小值）：
  $\text{SuffixMin} = [7, 10, 10, 17, 18, 30, 35, 40]$

步驟 2：比對條件 $\text{PrefixMax}[i] = A[i] = \text{SuffixMin}[i]$

比對每個位置是否同時滿足「左側無更大值」與「右側無更小值」。

選項分析

針對陣列中的每一個元素位置進行逐一檢驗與說明：

• 元素 $A[0] = 7$（正確 Pivot 候選）：

  • 左側無任何元素（預設滿足左側約束）。
  • 右側所有元素 $\{11, 10, 17, 18, 30, \dots\}$ 的最小值為 $10 \ge 7$。
  • 結論：滿足條件，7 可為 Pivot。

• 元素 $A[1] = 11$（錯誤，不可為 Pivot）：

  • 左側元素 $\{7\}$ 的最大值為 $7 \le 11$（滿足左側）。
  • 右側存在元素 $A[2] = 10$，因為 $10 < 11$，違反右側約束（右側存在比 11 更小的元素）。
  • 結論：不滿足條件，11 不可為 Pivot。

• 元素 $A[2] = 10$（錯誤，不可為 Pivot）：

  • 左側存在元素 $A[1] = 11$，因為 $11 > 10$，違反左側約束（左側存在比 10 更大的元素）。

核心觀念

本題旨在考驗**演算法正確性證明（Correctness of Algorithms）**中的核心技術：迴圈不變性（Loop Invariant）。

根據 C.A.R. Hoare 的邏輯框架與 CLRS 教科書規範，驗證一個迴圈不變式必須證明以下三個性質：

1. 初始化（Initialization）：在迴圈第一次迭代開始前，不變式成立。
2. 維持（Maintenance）：若在某次迭代開始前不變式成立，則在該次迭代結束（即下一次迭代開始前），不變式依然成立。
3. 終止（Termination）：當迴圈終止時，不變式能提供強大且有用的性質，以證明演算法結果的正確性。

題目給定長度為 $n$ 的整數陣列 $A[1 \dots n]$，其中前 $p$ 個元素為負數（即 $A[1 \dots p] < 0$，且 $A[p+1 \dots n] \ge 0$，其中 $p \in \{0, 1, \dots, n\}$）。雙指標 left 與 right 分別從陣列兩端向中間移動，藉此計算出負數個數 $p$。

解題方法與推導

1. 演算法執行流程追蹤

演算法的核心邏輯可分為兩個階段（Phase）：

• 階段一（left 右移階段）：

  • 當 $1 \le left \le p$ 時，$A[left] < 0$ 恆成立。
  • 條件判斷成立，執行 left = left + 1，指標 left 逐步向右推進。
  • 此階段 right 保持為初始值 $n$ 不變。
  • 當 left 遞增至 $p + 1$ 時，此時 $A[p+1] \ge 0$，階段一結束。

• 階段二（right 左移階段）：

  • 當 $left = p + 1$ 時，$A[left] \ge 0$。
  • 條件判斷不成立，進入 else 區塊執行 right = right - 1。
  • 此階段 left 鎖定在 $p + 1$ 不再移動。
  • 指標 right 從 $n$ 逐步遞減至 $p$。

• 迴圈終止與回傳：

  • 當 right 減至 $p$ 時，條件 left <= right（即 $p + 1 \le p$）不成立，迴圈結束。
  • 演算法回傳 left - 1 = (p + 1) - 1 = p，成功求得負數總數 $p$。

2. 迴圈不變式（Loop Invariant）的建立與推導

在 while 迴圈每次迭代開始前（包含進行 left <= right 測試時），變數 left 與 right 恆維持以下幾項邏輯關係：

$\mathcal{I}(left, right) \equiv (1 \le left \le p + 1) \land (p \le right \le n) \land (\forall 1 \le k < left, A[k] < 0) \land (\forall right < k \le n, A[k] \ge 0)$

中文敘述即為：

「在 while 迴圈每次迭代開始時，索引小於 left 的所有元素均為負數（$A[1 \dots left-1] < 0$），且索引大於 right 的所有元素均為非負數（$A[right+1 \dots n] \ge 0$）；同時滿足 $1 \le left \le p + 1$ 與 $p \le right \le n$。」

3. 三步驟嚴謹證明

• 初始化（Initialization）：
  在進入迴圈前，left = 1，right = n。

  • 小於 left 的索引集合為空集合 $\{1 \dots 0\} = \emptyset$，故「$A[1 \dots left-1] < 0$」真空成立（Vacuously True）。
  • 大於 right 的索引集合為空集合 $\{n+1 \dots n\} = \emptyset$，故「$A[right+1 \dots n] \ge 0$」真空成立。
  • $left = 1 \le p + 1$ 與 $right = n \ge p$ 均成立。不變式於初始狀態成立。

• 維持（Maintenance）：
  假設某次迭代前 $\mathcal{I}(left, right)$ 成立且 $left \le right$。

  • 若 $A[left] < 0$：說明 $left \le p$。執行 left = left + 1 後，新邊界前的所有元素 $A[1 \dots left]$ 皆為負數，且 right 未改變。下一次迭代前不變式依然成立。
  • 若 $A[left] \ge 0$：說明 $left = p + 1$。

考慮字串

$s = \text{``cbaabcba''},\qquad n = |s| = 8$

其反轉為

$\text{rev}(s)=\text{``abcbaabc''}$

列出 $s$ 的所有前綴與 $\text{rev}(s)$ 的所有後綴：

核心觀念

本題考查計算複雜度理論（Complexity Theory）中 NP 與 NP-Complete (NPC) 的正規數學定義、多項式時間歸約（Polynomial-time Reduction, $\le_P$）的方向性與自反性，以及近似演算法（Approximation Algorithm）與 $\text{P vs NP}$ 問題之間的關係。

關鍵定義如下：

1. $\text{NP}$（Nondeterministic Polynomial-time）：可以在多項式時間內被非確定型圖靈機求解，或在確定型圖靈機上於多項式時間內驗證證人（Certificate）的決定性問題集合。已知 $\text{P} \subseteq \text{NP}$。
2. $\text{NP-Complete (NPC)}$：語言 $L \subseteq \{0,1\}^*$ 稱為 NP-Complete，若且唯若滿足以下兩條件：
   • $L \in \text{NP}$。
   • 對於任意 $L' \in \text{NP}$，均滿足 $L' \le_P L$（即所有 $\text{NP}$ 問題皆可在多項式時間內歸約至 $L$）。
3. 歸約的自反性（Reflexivity of Reduction）：對於任何語言 $L$，定義恆等映射函數 $f(x) = x$，即可在 $O(|x|)$ 時間內完成歸約，故 $L \le_P L$ 永遠成立。

解題方法

本題切入點為依據複雜度類別的嚴格定義，逐一核對各選項的邏輯正確性：

1. 利用 $\text{P} \subseteq \text{NP}$ 之關係驗證 (A)。
2. 依據歸約符號 $L_1 \le_P L_2$ 的定義方向（代表 $L_1$ 的難度小於或等於 $L_2$）與自反性檢驗 (B) 與 (C)。
3. 舉出已知具備常數比例近似演算法的 NPC 最適化問題實例（如頂點覆蓋問題 Vertex Cover 的 2-近似演算法）反駁 (D)。

選項分析

• (A) 錯誤。
  原文：An NP problem of size n takes more than poly(n) time to solve.
  分析：$\text{P}$ 為 $\text{NP}$ 的子集（$\text{P} \subseteq \text{NP}$）。屬於 $\text{P}$ 的問題在確定型圖靈機上即可於多項式時間 $\text{poly}(n)$ 內求解。因此，「大小為 $n$ 的 NP 問題皆需要超過多項式時間求解」的敘述不成立。

• (B) 錯誤。
  原文：Any NP-complete problem is polynomial-reducible to any other NP problem.
  分析：根據 NP-Complete 的定義，是「所有 $\text{NP}$ 問題皆可歸約至 NPC 問題」（$L' \le_P L$），而非「NPC 問題可歸約至任意 $\text{NP}$ 問題」。

核心觀念

1. 雜湊表（Hash Table）與載重因子（Load Factor）
   設雜湊表中的元素個數為 $n$，槽位（Entries / Buckets）數量為 $m = f(n)$，則載重因子定義為：
   $\alpha = \frac{n}{m} = \frac{n}{f(n)}$

2. 簡單均勻雜湊假設（Simple Uniform Hashing Assumption）
   題目給定雜湊函數能均勻分配元素（Uniformly Dispatch Items），在該前提下（不論採用鏈結法 Chaining 或開放定址法 Open Addressing），成功搜尋（Successful Search）所需的期望時間為：
   $T(n) = \Theta(1 + \alpha)$

3. 常數時間 $O(1)$ 搜尋的充要條件
   若要保證成功搜尋的時間複雜度為 $O(1)$，載重因子 $\alpha$ 必須為常數上界，即 $\alpha = O(1)$：
   $\alpha = \frac{n}{f(n)} \le C \quad (C > 0 \text{ 為常數}) \implies f(n) \ge \frac{1}{C} n \implies f(n) = \Omega(n)$
   這表示雜湊表的槽位數量 $f(n)$ 的下界必須達到 $\Omega(n)$，才能保證載重因子不隨 $n$ 成長。

4. 漸進記號（Asymptotic Notation）的陷阱

   • $f(n) = O(n)$ 代表 $f(n)$ 的上界為 $n$ 的常數倍（$f(n) \le c \cdot n$），這包含 $f(n) = 1$ 或 $f(n) = \sqrt{n}$ 等極小函數。
   • $f(n) = \Omega(n)$ 代表 $f(n)$ 的下界為 $n$ 的常數倍（$f(n) \ge c \cdot n$），這才能確保槽位數量足夠。

解題方法

1. 列出平均搜尋時間公式
   在 Simple Uniform Hashing 下，每個槽位平均分配到的元素數量為 $\alpha = \frac{n}{f(n)}$。
   成功搜尋的期望時間為：
   $T(n) = \Theta\left(1 + \frac{n}{f(n)}\right)$

2. 推導 $f(n)$ 需滿足的漸進階數
   若要滿足 $T(n) = O(1)$，則必須滿足：
   $\frac{n}{f(n)} = O(1) \iff f(n) = \Omega(n)$

核心觀念

本題考查**紅黑樹（Red-Black Tree, RBT）**的定義、性質以及結構限制。主要涉及以下重要觀念：

1. 紅黑樹的基本性質：

   • 性質 1：每個節點非紅即黑（Red or Black）。
   • 性質 2：根節點（Root）必須為黑色。
   • 性質 3：所有葉節點（NIL 節點）皆為黑色。
   • 性質 4：若一個節點為紅色，則其子節點必須為黑色（不允許連續兩個紅節點）。
   • 性質 5：從任一節點到其所有後代 NIL 節點的簡單路徑上，包含相同數量的黑色節點（黑高度 Black-height 一致）。

2. 內部節點（Internal Node）與子節點（Child Node）：

   • 儲存 Key 的非 NIL 節點稱為內部節點，本題總共有 $n$ 個內部節點。
   • 在 $n$ 個內部節點中，除了根節點之外，其餘 $n - 1$ 個內部節點皆為某個節點的「子節點」。

3. 滿二元樹（Perfect Binary Tree）與奇偶性：

   • 若一棵紅黑樹的所有內部節點皆為黑色，則根據黑高度一致性，所有 NIL 葉節點必須位於同一深度，該樹必定為一棵高度為 $h$ 的滿二元樹。
   • 滿二元樹的內部節點總數公式為：
     $n = 2^h - 1$
   • 對於任意整數 $h \ge 1$，$2^h - 1$ 恆為奇數（Odd）（例如 $1, 3, 7, 15, \dots$）。

解題方法

1. 計算內部子節點的總數：
   樹中共有 $n$ 個內部節點，其中只有 1 個根節點沒有雙親，因此屬於「子節點」的內部節點共有 $n - 1$ 個。

2. 分析全黑內部節點的可行性：

   • 若要讓黑色子節點數量達到理論最大值 $n - 1$，代表這 $n - 1$ 個子節點必須全為黑色。
   • 加上根節點強制為黑色，這意味著整棵樹的 $n$ 個內部節點必須全為黑色（即紅色內部節點數量為 0）。
   • 若所有內部節點皆為黑色，該紅黑樹必須是一棵滿二元樹，其內部節點數必須滿足 $n = 2^h - 1$（必為奇數）。
   • 然而，題目給定 $n$ 為偶數（Even），因此 $n \neq 2^h - 1$。
   • 由此可證：當 $n$ 為偶數時，不可能所有內部節點皆為黑色，樹中至少必須存在 1 個紅色內部節點。

3. 推導黑色子節點的上限：

   • 由於根節點必須為黑色，該紅色內部節點必為 $n - 1$ 個子節點之一。
   • 在 $n - 1$ 個內部子節點中，至少有 1 個是紅色子節點，因此黑色子節點的最大數量為：

核心觀念

本題考驗**紅黑樹（Red-Black Tree, RBT）**的樹高上限（Maximum Height）推導與極端結構性質。

紅黑樹是一種自我平衡的二元搜尋樹（Self-Balancing Binary Search Tree），必須嚴格滿足以下 5 大基本性質：

1. 每個節點不是紅色就是黑色。
2. 根節點（Root）必須是黑色。
3. 每個葉節點（NIL / 外部節點）都是黑色。
4. 若一節點為紅色，則其兩個子節點必為黑色（即不可有連續兩個紅色節點）。
5. 對於任意節點，從該節點至其所有後代葉節點的簡單路徑上，包含相同數量的黑色節點，此數量稱為該節點的黑高度（Black-Height），記作 $bh(x)$。

依題意定義，單一節點之樹高為 $1$（即樹高 $h$ 代表從根節點到葉節點路徑上的節點總數）。設紅黑樹含有 $n$ 個內部節點（Internal Nodes），則其樹高 $h$ 與內部節點數 $n$ 之間存在經典上限定理：
$h \le 2 \lg(n + 1)$

解題方法

1. 黑高度與內部節點數之關係推導：
利用數學歸納法可證得：以節點 $x$ 為根的子樹，至少包含 $2^{bh(x)} - 1$ 個內部節點。
對整棵紅黑樹（根節點為 $root$）而言，總內部節點數 $n$ 滿足：
$n \ge 2^{bh(root)} - 1$

2. 樹高 $h$ 與黑高度 $bh(root)$ 之關係：
根據性質 4（不可有連續紅節點），在從根節點到葉節點的最長路徑上，紅色節點的數量最多不會超過黑色節點的數量。
因此，在一條包含 $h$ 個內部節點的路徑中，至少有一半的節點是黑色的（即黑色節點數至少為 $h / 2$）。
故根節點的黑高度滿足：
$bh(root) \ge \frac{h}{2}$

3. 推導樹高上限：
將 $bh(root) \ge \frac{h}{2}$ 代入內部節點數不等式：
$n \ge 2^{\frac{h}{2}} - 1$

兩邊同時加 1 並取以 2 為底的對數（$\lg = \log_2$）：
$n + 1 \ge 2^{\frac{h}{2}}$

**依原頁影像作答：**第 16 題實際詢問的是 $m[2,5]$，也就是計算 $A_2A_3A_4A_5$ 的最少純量乘法次數。影像中的矩陣維度依序為 $A_2:35\times15$、$A_3:15\times5$、$A_4:5\times10$、$A_5:10\times20$。

核心觀念

矩陣鏈乘法的矩陣順序固定，但括號位置不同，所需的純量乘法次數可能不同。令維度序列為 $p=[35,15,5,10,20]$，則動態規劃遞迴式為：

其中，$k$ 表示將矩陣鏈切成左右兩段的位置；$p_{i-1}p_kp_j$ 是將左右兩段結果相乘的成本。

解題方法

先算較短矩陣鏈的最小成本：

計算 $A_2A_3A_4$：

計算 $A_3A_4A_5$：

核心觀念

本題考查**矩陣鏈乘法（Matrix Chain Multiplication, MCM）問題，屬於經典的動態規劃（Dynamic Programming, DP）**應用範疇。

對於 $n$ 個矩陣連乘 $A_1 A_2 \cdots A_n$，由於矩陣乘法滿足結合律，不同的加括號方式（Parenthesization）會導致總純量乘法（Scalar Multiplication）次數大不相同。動態規劃解法透過將問題拆解為重疊的子問題（Overlapping Subproblems），利用最優子結構（Optimal Substructure）性質來計算出最少所需的純量乘法總次數。

解題方法

1. 狀態定義與動態規劃轉移方程

假設矩陣 $A_i$ 的維度為 $p_{i-1} \times p_i$（其中 $1 \le i \le n$）。
定義 DP 狀態表格 $m[i, j]$ 為計算矩陣序列 $A_i A_{i+1} \cdots A_j$（其中 $1 \le i \le j \le n$）所需的最小純量乘法次數。

• 基底條件（Base Case）：
  當矩陣鏈長度為 1 時，無需進行任何乘法：
  $m[i, i] = 0 \quad (\forall 1 \le i \le n)$

• 遞迴關係式（Recurrence Relation）：
  對於長度大於 1 的矩陣鏈（即 $i < j$），枚舉所有可能的分割點 $k$（$i \le k < j$）：
  $m[i, j] = \min_{i \le k < j} \left\{ m[i, k] + m[k+1, j] + p_{i-1} \cdot p_k \cdot p_j \right\}$

2. 時間複雜度推導

• 狀態總數（DP 表格大小）：
  狀態由區間起點 $i$ 與終點 $j$ 決定，滿足 $1 \le i \le j \le n$。DP 表格中需填入的有效子問題數量為：
  $\frac{n(n-1)}{2} = O(n^2)$

• 單一狀態計算成本：
  計算每一個狀態 $m[i, j]$ 時，分割點 $k$ 的可能取值有 $j - i$ 個。在最壞情況下（當區間長度接近 $n$ 時），遍歷 $k$ 需要花費 $O(n)$ 次操作。

核心觀念

Dijkstra 演算法用來求非負邊權圖中，單一起點到各頂點的最短路徑。它每次選出目前暫定距離最小的頂點並固定其距離，因此屬於貪婪演算法。使用最小優先佇列時，時間複雜度取決於佇列的實作方式。

解題方法

圖中第 18 題問「哪個敘述錯誤」；選項 A 說搜尋原則是廣度優先，選項 D 說稠密圖搭配二元最小堆積可在 $O(V^2)$ 執行。依標準 Dijkstra 定義與最壞情況時間複雜度，這兩項都不正確。

使用二元最小堆積時，取出最小距離頂點與更新佇列的操作各需 $O(\log V)$，標準總複雜度為

稠密圖有 $E=\Theta(V^2)$，代入可得

所以 D 的 $O(V^2)$ 不符合標準二元堆積實作的最壞情況界限。

選項分析

• (A) 錯誤。 Dijkstra 不等同廣度優先搜尋。廣度優先搜尋依層次探索，適用於邊權相同的情況；Dijkstra 則依目前的暫定距離選取下一個頂點。

核心觀念

最小生成樹（MST）會以最小總權重連通所有頂點，且不含環。判斷邊是否屬於 MST，可使用 割性質：若某條邊是跨越某個割的最輕邊，則它可納入 MST。也可使用 環性質：若在一個環中，某條邊的權重嚴格最大，該邊不會屬於 MST。

解題方法

圖中的邊與權重為：$(V_1,V_4)=1$、$(V_2,V_7)=2$、$(V_1,V_3)=3$、$(V_1,V_2)=8$、$(V_2,V_3)=14$、$(V_6,V_7)=15$、$(V_1,V_7)=16$、$(V_3,V_4)=20$、$(V_4,V_5)=21$、$(V_1,V_6)=25$、$(V_5,V_6)=28$、$(V_1,V_5)=36$。

依權重由小到大套用 Kruskal 演算法：先選權重 $1,2,3,8$ 的邊；權重 $14$ 的 $(V_2,V_3)$ 會形成環，因此略過；接著選權重 $15$ 的 $(V_6,V_7)$。權重 $16$ 的 $(V_1,V_7)$ 也會形成環，略過。最後，為了連上 $V_5$，選擇與它相連且權重最小的 $(V_4,V_5)$，權重為 $21$。

因此原 MST 為

選項分析

核心觀念

空間複雜度計算的是演算法執行時需要的記憶體空間，不是執行步數。Floyd–Warshall 演算法使用距離矩陣 $D$ 儲存各頂點對之間的最短距離；矩陣有 $n$ 列、$n$ 欄，因此需要 $\Theta(n^2)$ 空間。

解題方法

原卷圖中給定的 $W$ 是 $n\times n$ 矩陣，演算法先令 $D=W$，再以三層迴圈依序更新每個 $d_{ij}$。三層迴圈會影響執行時間，但迴圈變數只有 $k,i,j$，不會因此額外存下三維資料。

距離矩陣 $D$ 含有 $n^2$ 個元素；即使把輸入矩陣 $W$ 和複製後的 $D$ 分開計算，總空間仍是 $\Theta(n^2)$。因此：

• 時間複雜度：$\Theta(n^3)$
• 空間複雜度：$\Theta(n^2)$

選項分析

核心觀念

Edmonds–Karp 演算法是 Ford–Fulkerson 最大流方法的一種實作：每次在殘餘網路中尋找增廣路徑，並沿著該路徑增加流量。它使用廣度優先搜尋（BFS），因此每次找到的增廣路徑都是邊數最少的路徑。

若 $V$ 是頂點數、$E$ 是邊數，Edmonds–Karp 的標準時間複雜度為

這個複雜度不依賴最大流的數值 $|f^*|$，適用於容量為實數的情況。

解題方法

先辨認 Edmonds–Karp 的搜尋方式，再套用其標準複雜度：

1. 每次以 BFS 在殘餘網路中尋找最短增廣路徑。一次 BFS 的時間為 $O(E)$。
2. Edmonds–Karp 的增廣次數上界為 $O(VE)$。
3. 因此總時間為

據此比對選項，題目中的複雜度選項沒有列出 $O(VE^2)$，所以應選「以上皆非」。

選項分析