114 年 國立中山大學資訊工程學系資訊安全碩士班《離散數學與演算法》

這題考的是整數分割（Integer Partition）的概念，但題目特別強調「順序是相關的」，這意味著我們實際上是在計算一個正整數的「組合數」（Composition）。

一個正整數 $n$ 的組合數是指將 $n$ 寫成一連串正整數之和的方法數量，其中這些正整數的順序是被考慮的。例如，數字 3 的組合數有：
3
2+1
1+2
1+1+1
總共有 4 種。

這個問題可以用「星星與棒子」（Stars and Bars）的方法來解決。想像我們有 13 個星星（代表數字 13）：
*************

我們要將這 13 個星星分成若干堆，每一堆至少有一個星星，且順序是相關的。這相當於在 13 個星星之間插入「棒子」來分隔它們。
在 13 個星星之間，總共有 $13 - 1 = 12$ 個可能的「縫隙」可以插入棒子。
* | * | * | * | * | * | * | * | * | * | * | *

每一個縫隙，我們可以選擇插入一個棒子，或者不插入。
例如：

• 不插入任何棒子：************* (代表 13)
• 在第一個縫隙插入棒子：* | *********** (代表 1 + 12)

核心觀念

本題旨在考查數論的基本性質與集合論中的**良序原理（Well-Ordering Principle）**之應用。關鍵概念與定義如下：

1. 合數（Composite Number）定義：若正整數 $n > 1$ 不是質數，則稱為合數。即存在正整數 $d$ 使得 $d \mid n$ 且 $1 < d < n$。
2. 良序原理（Well-Ordering Principle, WOP）：正整數集合 $\mathbb{Z}^+$ 的任意非空子集，都必定包含一個最小元素（Least Element）。亦即若 $S \subseteq \mathbb{Z}^+$ 且 $S \neq \emptyset$，則存在 $m \in S$ 使得對所有 $x \in S$，均滿足 $m \le x$。
3. 整除的遞移律（Transitivity of Divisibility）：設 $a, b, c \in \mathbb{Z}^+$，若 $a \mid b$ 且 $b \mid c$，則 $a \mid c$。
4. 質數（Prime Number）定義：大於 1 的正整數 $p$，若其正因數僅有 1 與 $p$ 本身，則 $p$ 稱為質數。

---

解題方法

本題要求的證明切入點為：定義一個由 $n$ 的真因數所構成的集合，透過良序原理確保該集合存在最小元素，再利用反證法證明此最小元素必然為質數。

關鍵證明步驟與推導過程如下：

證明：

步驟一：構造集合 $S$
定義集合 $S$ 為 $n$ 所有大於 1 且小於 $n$ 的正因數所組成的集合：
$S = \{ x \in \mathbb{Z}^+ \mid x \mid n \text{ 且 } 1 < x < n \}$

步驟二：驗證集合 $S$ 非空且為正整數子集
已知 $n \in \mathbb{Z}^+$ 且 $n$ 為合數，根據合數的定義，存在至少一個正整數 $d$ 滿足 $d \mid n$ 且 $1 < d < n$。
因此 $d \in S$，可得 $S \neq \emptyset$（$S$ 為非空集合）。又由定義可知 $S \subseteq \mathbb{Z}^+$。

步驟三：套用良序原理
因為 $S$ 是正整數集合 $\mathbb{Z}^+$ 的非空子集，根據良序原理，$S$ 必定包含一個最小元素，設此最小元素為 $p$。
即 $p \in S$，且對所有 $x \in S$，皆滿足 $p \le x$。

核心觀念

1. 算術基本定理（Fundamental Theorem of Arithmetic）與乘法原理

   • 任何大於 $1$ 的自然數，均可唯一分解為質因數的乘積。若 $p, q$ 為互異質數，則每一個有序對 $(m, n)$ 所對應的整數 $p^m q^n$ 皆為唯一相異。
   • 依據計數原理中的乘法原理，有限集合中相異元素個數等於各獨立選項目數的乘積。

2. 代數結構：二元運算與單位元（Identity Element）

   • 設 $A$ 為一集合，$f: A \times A \to A$ 為定義在 $A$ 上的封閉二元運算。若存在一元素 $e \in A$，使得對所有 $x \in A$，皆滿足：
     $f(x, e) = f(e, x) = x$
     則稱 $e$ 為運算 $f$ 在集合 $A$ 中的單位元。
   • 於本題中，$f(a, b) = \gcd(a, b)$，故 $e$ 為單位元意指對所有 $x \in A$，均有 $\gcd(x, e) = x$。

---

解題方法

(a) 計算集合 $A$ 的元素個數 $|A|$

• 集合 $A$ 的元素型態為 $x = p^m q^n$，其中 $m \in \{0, 1, 2, \dots, 29\}$，$n \in \{0, 1, 2, \dots, 41\}$。
• 因為 $p, q$ 為互異質數，根據算術基本定理，不同的指數組合 $(m, n)$ 定會產生不同的整數值 $x$。
• 指數 $m$ 的可選取個數為 $29 - 0 + 1 = 30$ 種。
• 指數 $n$ 的可選取個數為 $41 - 0 + 1 = 42$ 種。
• 由乘法原理，集合 $A$ 的元素總數為：
  $|A| = 30 \times 42 = 1260$

(b) 判斷 $f(a, b) = \gcd(a, b)$ 是否存在單位元

• 若存在單位元 $e \in A$，根據單位元定義，必須對所有 $x \in A$ 均滿足 $\gcd(x, e) = x$。
• 由數論性質可知：$\gcd(x, e) = x \iff x \mid e$（即 $x$ 能整除 $e$）。
• 這代表單位元 $e$ 必須是集合 $A$ 中所有元素的倍數。
• 設 $e = p^{m_e} q^{n_e} \in A$，其中 $0 \le m_e \le 29$ 且 $0 \le n_e \le 41$。
• 取集合 $A$ 中的極大元素 $x = p^{29} q^{41} \in A$，若要使 $x \mid e$，則 $e$ 的質因數指數必須滿足 $m_e \ge 29$ 且 $n_e \ge 41$。

核心觀念

1. 克萊尼星號集 (Kleene Star)：
   對於字母集 $\Sigma = \{0, 1\}$ 上的語言 $A = \{01, 1\}$，其克萊尼星號集 $A^*$ 定義為由 $A$ 中元素經由有限次連接（concatenation）所構成的所有字串集合，即：
   $A^* = \bigcup_{k=0}^{\infty} A^k$

2. 唯一分解性 (Unique Factorization Property)：
   在進行計數前，需確認 $A$ 中字串的連接是否具備唯一可拆解性。由於 $A = \{01, 1\}$ 中 $01$ 長度為 2 且以 0 開頭，$1$ 長度為 1 且以 1 開頭：

   • 任意字串 $w \in A^*$ 由左至右掃描時，只要遇到 0，其後方必須緊接一個 1 以組成積木 01；
   • 遇到的單獨 1 則必定為積木 1。

   因此 $A^*$ 中每一個字串均對應到唯一的積木組合序列，不存在歧義（Ambiguity）。

3. 分割數與費氏數列 (Compositions & Fibonacci Sequence)：
   將總長度 $n$ 拆解為若干個長度為 1（積木 $1$）與長度為 2（積木 $01$）的組合問題，可等價於鋪磚問題（Tiling Problem），其計數遞迴式正好對應費氏數列。

---

解題方法

本題求解 $A^*$ 中長度為 6 的字串個數，提供 組合計數法 與 遞迴關係式法 兩種標準解法：

方法一：組合計數法（按積木數量討論）

設形成長度為 6 的字串中，使用積木 $01$（長度 2）的數量為 $x$，使用積木 $1$（長度 1）的數量為 $y$。
長度限制條件為：
$2x + y = 6 \quad (x, y \in \mathbb{Z}_{\ge 0})$

對非負整數解 $(x, y)$ 進行分類討論並計算其相異排列數：

1. 當 $x = 0$ 時：
   $y = 6$，即由 6 個積木 $1$ 組成。
   排列數為 $\binom{6}{0} = 1$ 種。
   字串：111111

2. 當 $x = 1$ 時：
   $y = 4$，即由 1 個積木 $01$ 與 4 個積木 $1$ 組成（共 5 個積木）。
   排列數為 $\binom{5}{1} = 5$ 種。
   字串：011111, 101111, 110111, 111011, 111101

3. 當 $x = 2$ 時：
   $y = 2$，即由 2 個積木 $01$ 與 2 個積木 $1$ 組成（共 4 個積木）。
   排列數為 $\binom{4}{2} = 6$ 種。
   字串：010111, 011011, 011101, 101011, 101101, 110101

各變數的生成函數為

$$\begin{aligned} c_1&:\frac{x^{-2}}{1-x},& c_2&:\frac{x^{-4}}{1-x},\\ c_3&:x^{-3}(1+x+\cdots+x^9),& c_4&:\frac1{1-x}. \end{aligned}$$

故總生成函數為

令第 $i$ 次點數為 $X_i$，設 $Y_i=X_i-1$，則 $0\le Y_i\le5$，且

$$\sum_{i=1}^{15}Y_i=43-15=28.$$

利用容斥原理，符合條件的序列數為

$$\sum_{j=0}^{4}(-1)^j\binom{15}{j}\binom{28-6j+14}{14} = \binom{42}{14} -15\binom{36}{14} +105\binom{30}{14} -455\binom{24}{14} +1365\binom{18}{14}.$$

核心觀念

本題考查**二階常係數非齊次線性遞迴關係式（Second-Order Linear Non-Homogeneous Recurrence Relation with Constant Coefficients）**的求解。

主要涵蓋以下關鍵定義與公式：

1. 通解結構（General Solution Structure）：
   非齊次遞迴關係式的通解 $A_n$ 可拆解為齊次解 $A_n^{(h)}$ 與特解 $A_n^{(p)}$ 之和：
   $A_n = A_n^{(h)} + A_n^{(p)}$
2. 特徵方程式與齊次解（Characteristic Equation & Homogeneous Solution）：
   對應的齊次遞迴關係式為 $A_{n+2} - 5A_{n+1} + 6A_n = 0$，其特徵方程式為：
   $r^2 - 5r + 6 = 0$
   解得相異實根 $r_1, r_2$ 後，齊次解形式為 $A_n^{(h)} = c_1 r_1^n + c_2 r_2^n$。
3. 未定係數法求特解（Method of Undetermined Coefficients）：
   非齊次項為 $F(n) = 5^n$。當底數 $5$ 不是特徵根時，可假設特解形式為 $A_n^{(p)} = P \cdot 5^n$，代回原遞迴關係式求解未定係數 $P$。
4. 初始條件代入（Initial Conditions）：
   將通解帶入初始條件 $A_0 = 0, A_1 = 1$，建立二元一次聯立方程組求解未定常數 $c_1, c_2$。

---

解題方法

步驟一：求解齊次解 $A_n^{(h)}$

將原遞迴關係式之非齊次項置零，得到齊次關係式：
$A_{n+2} - 5A_{n+1} + 6A_n = 0$

寫出其特徵方程式並進行因式分解：
$r^2 - 5r + 6 = 0 \implies (r - 2)(r - 3) = 0$
求得特徵根為 $r_1 = 2, r_2 = 3$。

因此，齊次解形式為：
$A_n^{(h)} = c_1 \cdot 2^n + c_2 \cdot 3^n \quad (c_1, c_2 \text{ 為待定常數})$

步驟二：求解特解 $A_n^{(p)}$

非齊次項為 $F(n) = 5^n$。
比較非齊次項底數 $5$ 與特徵根 $r_1=2, r_2=3$，可知 $5$ 並非特徵根。

因此，假設特解形式為：
$A_n^{(p)} = P \cdot 5^n$

將 $A_n^{(p)}$ 代回原遞迴關係式 $A_{n+2} - 5A_{n+1} + 6A_n = 5^n$：
$P \cdot 5^{n+2} - 5 \cdot (P \cdot 5^{n+1}) + 6 \cdot (P \cdot 5^n) = 5^n$

等式兩邊同除以 $5^n$ 展開：
$25P - 25P + 6P = 1 \implies 6P = 1 \implies P = \frac{1}{6}$

故特解為：
$A_n^{(p)} = \frac{1}{6} \cdot 5^n$

步驟三：組合通解並套用初始條件

通解 $A_n$ 為齊次解與特解之和：
$A_n = c_1 \cdot 2^n + c_2 \cdot 3^n + \frac{1}{6} \cdot 5^n$

帶入初始條件 $A_0 = 0$ 與 $A_1 = 1$：

1. 當 $n = 0$ 時：
   $A_0 = c_1 \cdot 2^0 + c_2 \cdot 3^0 + \frac{1}{6} \cdot 5^0 = 0 \implies c_1 + c_2 + \frac{1}{6} = 0 \implies c_1 + c_2 = -\frac{1}{6}$
2. 當 $n = 1$ 時：

核心觀念

本題考查**堆積排序（Heap Sort）**的演算法流程與時間複雜度之數學推導。主要涵蓋以下核心觀念與定義：

1. 最大堆積（Max-Heap）：一種結構上符合完全二元樹（Complete Binary Tree），且滿足**最大堆積屬性（Max-Heap Property）**的資料結構。亦即對任意非根節點 $i$，其父節點之鍵值恆不小於該節點鍵值：
   $A[\text{Parent}(i)] \ge A[i]$
2. 陣列儲存表示法（Array Representation）：使用一維陣列 $A[1 \dots n]$ 儲存二元樹，對於索引為 $i$ 的節點：
   • 父節點索引：$\text{Parent}(i) = \lfloor i/2 \rfloor$
   • 左子節點索引：$\text{Left}(i) = 2i$
   • 右子節點索引：$\text{Right}(i) = 2i + 1$
3. 關鍵操作：
   • Max-Heapify：下沉調整單一節點，維護最大堆積屬性。
   • Build-Max-Heap：將無序陣列由下而上建立為最大堆積。
   • Heap-Sort：利用最大堆積持續提取最大值進行排序。

---

解題方法

一、 演算法詳細描述 (Algorithm Description)

堆積排序主要由三個核心步驟/程序組成：

1. 維護堆積屬性 (Max-Heapify(A, i))：

   • 假設以 $\text{Left}(i)$ 與 $\text{Right}(i)$ 為根的子樹皆已滿足最大堆積屬性，但 $A[i]$ 可能小於其子節點。
   • 比較 $A[i]$、$A[\text{Left}(i)]$ 與 $A[\text{Right}(i)]$ 的數值，找出最大值所在索引 $\text{largest}$。
   • 若 $\text{largest} \neq i$，則將 $A[i]$ 與 $A[\text{largest}]$ 交換，並對索引 $\text{largest}$ 遞迴呼叫 Max-Heapify，使換下去的元素持續下沉至正確位置。

2. 建立最大堆積 (Build-Max-Heap(A))：

   • 對於長度為 $n$ 的陣列，所有索引在 $\lfloor n/2 \rfloor + 1 \dots n$ 的節點皆為葉節點（Leaf Nodes），單獨的葉節點自然滿足最大堆積屬性。
   • 從最後一個非葉節點 $i = \lfloor n/2 \rfloor$ 開始倒數至 $i = 1$，對每個節點依序呼叫 Max-Heapify(A, i)，採用由下而上（Bottom-up）方式構建出完整的最大堆積。

3. 執行排序 (Heap-Sort(A))：

   • 首先呼叫 Build-Max-Heap(A) 將輸入陣列構造成最大堆積，此時根節點 $A[1]$ 即為全陣列最大值。
   • 執行 $n-1$ 次迴圈：
     • 將根節點 $A[1]$ 與當前堆積最後一個元素 $A[i]$ 對調，此時最大值已被放置於陣列最終正確位置。
     • 將堆積大小減 $1$（heap_size = heap_size - 1），以排除已排序好的末端元素。
     • 對新的根節點呼叫 Max-Heapify(A, 1) 重新恢復最大堆積屬性。

---

二、 關鍵虛擬碼 (Pseudocode)

Max-Heapify(A, i):
    l = Left(i)
    r = Right(i)
    if l <= heap_size and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size and A[r] > A[largest]:
        largest = r
    if largest != i:
        swap A[i] with A[largest]
        Max-Heapify(A, largest)

Build-Max-Heap(A):
    heap_size = A.length
    for i = floor(A.length / 2) down to 1:
        Max-Heapify(A, i)

Heap-Sort(A):
    Build-Max-Heap(A)
    for i = A.length down to 2:
        swap A[1] with A[i]
        heap_size = heap_size - 1
        Max-Heapify(A, 1)

---

三、 時間複雜度詳細推導 (Time Complexity Analysis)

1. Max-Heapify 之時間複雜度

對於一個包含 $n$ 個節點的堆積，以節點 $i$ 為根的子樹大小最大不會超過 $2n/3$（發生在最底層剛好填滿一半的情況）。
其執行時間遞迴關係式為：
$T(n) \le T(2n/3) + \Theta(1)$
由主定理（Master Theorem）可得其最壞時間複雜度為 $O(\log n)$。若以節點高度 $h$ 表示，下沉最多走 $h$ 層，時間複雜度為 $O(h)$。

2. Build-Max-Heap 之時間複雜度（關鍵精準推導）

粗略估算為 $\lfloor n/2 \rfloor \times O(\log n) = O(n \log n)$，但此估算過於鬆散。經精準計算：

• 一個包含 $n$ 個節點的完全二元樹，高度為 $h$ 的節點數量最多為 $\left\lceil \frac{n}{2^{h+1}} \right\rceil$。
• 樹的高度 $H = \lfloor \log_2 n \rfloor$。

核心觀念

1. 0-1 背包問題（0-1 Knapsack Problem）：
   本題為典型的 0-1 背包問題。在總重量不超過背包最大容量 $Q$ 的限制下，從 $n$ 個物品中選擇一組物品組合，使總效益價值（Benefit Value）最大化。每個物品只有「選（1）」或「不選（0）」兩種選擇，不可分割亦不可重複選取。
2. 動態規劃（Dynamic Programming, DP）：
   解決此問題需滿足動態規劃的兩大核心特性：
   • 最佳子結構（Optimal Substructure）：原問題的最佳解可由規模較小的子問題最佳解組合而成。考慮前 $i$ 個物品在容量限制 $j$ 下的最大效益，取決於前 $i-1$ 個物品在容量 $j$ 或 $j - w_i$ 下的最佳解。
   • 重疊子問題（Overlapping Subproblems）：求解過程中會重複調用相同的子狀態。利用表格（DP Table）記錄已計算過的子問題解答，可避免重複計算。

---

解題方法

1. 狀態定義（State Definition）

定義二維陣列 $DP[i][j]$：
從前 $i$ 個物品（物品 $1$ 至 $i$）中進行選擇，且背包容量上限為 $j$ 時，所能獲得的最大總效益價值。
其中索引範圍為：

• $i \in \{0, 1, 2, \dots, n\}$
• $j \in \{0, 1, 2, \dots, Q\}$

目標求解值即為 $DP[n][Q]$。

2. 狀態轉移方程式（Recurrence Relation）推導

針對第 $i$ 個物品（重量為 $w_i$，效益價值為 $a_i$），依據當前背包容量 $j$ 分為兩種情況：

• 情況一：容量不足以裝下第 $i$ 個物品（即 $j < w_i$）
  無法選擇第 $i$ 個物品，故最大效益等於前 $i-1$ 個物品在容量 $j$ 下的最佳解：
  $DP[i][j] = DP[i-1][j]$

• 情況二：容量足夠裝下第 $i$ 個物品（即 $j \ge w_i$）
  此時決策分為「不選」與「選擇」第 $i$ 個物品，取兩者之最大值：

  • 不選擇第 $i$ 個物品：效益為 $DP[i-1][j]$。
  • 選擇第 $i$ 個物品：獲得第 $i$ 個物品的效益 $a_i$，再加上前 $i-1$ 個物品在剩餘容量 $j - w_i$ 下的最大效益，即 $DP[i-1][j - w_i] + a_i$。

綜合以上，得到完整轉移方程式：
$DP[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ DP[i-1][j] & \text{if } j < w_i \\ \max\left(DP[i-1][j],\, DP[i-1][j - w_i] + a_i\right) & \text{if } j \ge w_i \end{cases}$

3. 初始條件（Base Cases）

• $DP[0][j] = 0$（對所有 $0 \le j \le Q$）：沒有物品可選時，總效益為 $0$。
• $DP[i][0] = 0$（對所有 $0 \le i \le n$）：背包容量為 $0$ 時，無法裝入任何物品，總效益為 $0$。

4. 演算法虛擬碼（Pseudocode）

核心觀念

本題考驗圖形理論（Graph Theory）與演算法設計中「最小生成樹（Minimum Spanning Tree, MST）」的經典演算法及其時間複雜度分析。

1. 最小生成樹（MST）定義：
   給定一個連通且帶權重的無向圖 $G = (V, E)$，其中 $V$ 為頂點集合，$E$ 為邊集合，邊權重函數為 $w: E \to \mathbb{R}$。$G$ 的生成樹（Spanning Tree）為包含 $V$ 中所有頂點且無環的連通子圖 $T = (V, E')$，其中 $E' \subseteq E$ 且 $|E'| = |V| - 1$。當 $T$ 的總邊權重 $w(T) = \sum_{e \in E'} w(e)$ 達最小時，稱 $T$ 為圖 $G$ 的最小生成樹（MST）。

2. 貪婪選擇理論基礎：
   MST 演算法的核心立基於割定理（Cut Property）：

   • 割定理（Cut Property）：設 $S \subset V$ 為頂點集的一個真子集，劃分 $(S, V \setminus S)$ 稱為圖 $G$ 的一個割（Cut）。若邊 $e = (u, v) \in E$ 橫跨該割（即 $u \in S, v \in V \setminus S$），且 $e$ 為所有橫跨該割的邊中權重最小者（Light Edge），則邊 $e$ 必定屬於某棵最小生成樹。
   • 環定理（Cycle Property）：對於圖 $G$ 中的任意簡單環路 $C$，環路中權重最大的邊必定不屬於任何最小生成樹（在邊權重嚴格相異的前提下）。

---

解題方法

求解最小生成樹最著名的兩大經典貪婪演算法分別為 Kruskal 演算法與 Prim 演算法。以下分別詳細說明其運作機制與時間複雜度推導。

---

一、 Kruskal 演算法 (Kruskal's Algorithm)

1. 演算法步驟說明

Kruskal 演算法採用「以邊為中心（Edge-based）」的貪婪策略：

1. 將圖中所有邊 $E$ 依權重由小到大排序：$w(e_1) \le w(e_2) \le \dots \le w(e_{|E|})$。
2. 初始化生成樹邊集合 $A = \emptyset$。
3. 為每個頂點 $v \in V$ 建立獨立的不相交集合（Disjoint Set）。
4. 依序檢查排序後的每條邊 $e = (u, v)$：
   • 使用 Find-Set(u) 與 Find-Set(v) 檢查 $u$ 與 $v$ 是否屬於同一個連通分量。
   • 若屬於不同分量（不會形成環），則將 $e$ 加入 $A$，並執行 Union(u, v) 合併兩集合。
   • 若屬於相同分量（加入會形成環），則捨棄邊 $e$。
5. 當 $|A| = |V| - 1$ 時演算法結束，回傳 $A$。

2. 關鍵虛擬碼 (Pseudo-code)

MST-KRUSKAL(G, w)
    A = empty_set()
    for each vertex v in G.V:
        MAKE-SET(v)
    sort the edges of G.E into nondecreasing order by weight w
    for each edge (u, v) in G.E, taken in nondecreasing order:
        if FIND-SET(u) != FIND-SET(v):
            A = A union {(u, v)}
            UNION(u, v)
    return A

3. 詳細時間複雜度推導

• 初始化集合：執行 $|V|$ 次 Make-Set，時間複雜度為 $O(|V|)$。
• 邊的排序：對 $|E|$ 條邊進行排序，使用高效比較排序（如 Quick Sort / Merge Sort），時間複雜度為 $O(|E| \log |E|)$。
• Disjoint-Set 操作：
  • 迴圈最多遍歷 $|E|$ 條邊，共執行最多 $2|E|$ 次 Find-Set 與 $|V| - 1$ 次 Union。
  • 使用「路徑壓縮（Path Compression）」與「按秩合併（Union by Rank）」優化的 Disjoint-Set，單次操作的均攤時間為 $O(\alpha(|V|))$，其中 $\alpha$ 為反阿克曼函數（Inverse Ackermann Function），實務上 $\alpha(|V|) \le 4$。
  • 此階段總時間複雜度為 $O(|E| \cdot \alpha(|V|))$。
• 總時間複雜度：
  $T(|V|, |E|) = O(|V|) + O(|E| \log |E|) + O(|E| \alpha(|V|)) = O(|E| \log |E|)$
  由於在簡單圖中 $|E| \le |V|^2$，可得 $\log |E| \le \log(|V|^2) = 2 \log |V| = O(\log |V|)$。
  因此，Kruskal 演算法的時間複雜度寫為 $O(|E| \log |V|)$。

---

二、 Prim 演算法 (Prim's Algorithm)

1. 演算法步驟說明

Prim 演算法採用「以頂點為中心（Vertex-based）」的貪婪策略：

1. 任選一頂點 $r \in V$ 作為樹的根節點。
2. 維護頂點集合 $S$（已納入 MST 的頂點）與優先佇列 $Q$（未納入 MST 的頂點 $V \setminus S$）。
3. 每個頂點 $v$ 記錄 key[v]（$v$ 到當前 MST 集合 $S$ 的最短距離）與 $\pi[v]$（$v$ 在 MST 中的父節點）。初值設 key[r] = 0，其餘頂點為 $\infty$。
4. 當 $Q$ 不為空時：
   • 從 $Q$ 中取出 key 值最小的頂點 $u$（Extract-Min），將其加入 $S$。
   • 對於 $u$ 的每一個相鄰頂點 $v \in Q$：若邊權重 $w(u, v) < \text{key}[v]$，則更新 $\text{key}[v] = w(u, v)$ 並設定 $\pi[v] = u$（執行 Decrease-Key 操作）。