108 年 國立中正大學會計與資訊科技學系碩士班會計組《資料結構》

核心觀念

串列是「有順序、可重複」的有限資料集合，可用函數表示：

• $s_1$：索引集合。
• $s_2$：元素值的集合。
• $f:s_1\to s_2$：將每個索引對應到一個元素值。

函數不必為一對一，因此不同索引可以對應到相同的值。

1. 以集合與函數定義串列

採用數學上常見的 $1$ 起始索引：

$$s_1=\{1,2,3,4\}$$ $$s_2=\{2,3,4\}$$

定義函數：

$$f:s_1\to s_2$$

並令：

$$f(1)=3,\qquad f(2)=3,\qquad f(3)=2,\qquad f(4)=4$$

因此：

$$[f(1),f(2),f(3),f(4)] =[3,3,2,4]$$

注意，$s_2$ 不可寫成 $\{3,3,2,4\}$，因為集合中的重複元素只保留一份；重複出現的資訊是由函數 $f$ 保留的。

2. 使用 Java ArrayList 實作

Java 的 ArrayList 採用 $0$ 起始索引：

ArrayList<Integer> list = new ArrayList<>();

list.add(3);
list.add(3);
list.add(2);
list.add(4);

其邏輯草圖如下：

索引 index       0       1       2       3
              ┌───────┬───────┬───────┬───────┐
元素 element  │   3   │   3   │   2   │   4   │
              └───────┴───────┴───────┴───────┘
                         size = 4

ArrayList 以連續陣列儲存元素。兩個相同的 3 仍分別位於索引 $0$ 與 $1$，代表兩個不同的位置。

3. 使用 Java LinkedList 實作

LinkedList<Integer> list = new LinkedList<>();

list.addLast(3);
list.addLast(3);
list.addLast(2);
list.addLast(4);

LinkedList 可視為由節點組成的雙向鏈結串列，每個節點概念上包含：

$$[\text{prev}\mid \text{data}\mid \text{next}]$$

核心觀念

本題考查內部排序演算法（Internal Sorting Algorithms）之基礎特性分析，為資管所、會資所與資工所歷年必考的核心送分題。主要評量重點包含：

1. 時間複雜度（Time Complexity）：演算法在最佳狀況（Best Case）、平均狀況（Average Case）與最差狀況（Worst Case）下的漸近時間表現（大 $O$ 符號）。
2. 空間複雜度（Space Complexity / Auxiliary Space）：演算法運作時，除了儲存原始資料外，額外配置之輔助記憶體空間（是否為就地排序 In-Place Sort）。
3. 穩定性（Stability）：當待排序序列中存在鍵值（Key）相同的兩筆資料時，排序完成後其「相對先後順序」是否與排序前保持一致。若能保證相對順序不變，則為穩定排序（Stable Sort）；否則為不穩定排序（Unstable Sort）。

---

解題方法：演算法特性逐項深度剖析

1. 快速排序法（Quicksort）

• 時間複雜度：
  • 最佳狀況：每次分割選取的基準點（Pivot）皆能精確切分出兩等份子數列，遞迴關係式為 $T(n) = 2T(n/2) + O(n)$，由主定理（Master Theorem）解得 $O(n \log n)$。
  • 平均狀況：基準點隨機切分，平均分割比率能大致均衡，時間複雜度仍為 $O(n \log n)$。
  • 最壞狀況：輸入資料已是由小到大排序或由大到小排序，且基準點總是選到極端值（最小或最大值），導致每次分割僅切出大小為 $0$ 與 $n-1$ 的子數列，遞迴式為 $T(n) = T(n-1) + O(n)$，時間退化為 $O(n^2)$。
• 所需額外空間：
  • 實作上屬於就地排序（In-place），無須額外的暫存陣列；但遞迴呼叫需佔用系統堆疊（Call Stack）。平均遞迴深度為 $O(\log n)$，最壞遞迴深度為 $O(n)$。在傳統表格填寫中，標準答案通常記為 $O(\log n)$（平均堆疊空間）或標註 $O(\log n) \sim O(n)$。若以輔助資料陣列來看為 $O(1)$。標準學術解以系統堆疊空間為主，填 $O(\log n)$ 或 $O(1) \sim O(\log n)$（最嚴謹寫法：平均 $O(\log n)$，最壞 $O(n)$）。
• 穩定性：不是（Unstable）。
  • 在資料交換（Partitioning Swap）的過程中，跨越 Pivot 的遠距離交換極易破壞相同鍵值元素的相對順序。例如數列 $[5_A, 5_B, 2]$，以 $2$ 為基準點交換後，$5_A$ 與 $2$ 交換會跳過 $5_B$，導致相對順序顛倒。

2. 泡沫排序法（Bubble Sort）

• 時間複雜度：
  • 最佳狀況：若設有旗標（Flag）檢測某一回合是否發生資料交換，當輸入數列已完成排序時，僅需跑完第一回合掃描 $n-1$ 次比較即可提前結束，故最佳為 $O(n)$。（若未加 Flag 最佳情況為 $O(n^2)$，但在標準演算法考題中皆預設具備旗標機制優化）。
  • 平均狀況：平均比較與交換次數約為 $\frac{n(n-1)}{4}$，時間複雜度為 $O(n^2)$。
  • 最壞狀況：輸入數列呈現完全反序（Reverse Order），每對相鄰元素皆需比較與交換，比較次數為 $\frac{n(n-1)}{2}$，時間複雜度為 $O(n^2)$。
• 所需額外空間：$O(1)$。
  • 僅需一個常數空間的暫存變數以供相鄰元素互換（In-place）。
• 穩定性：是（Stable）。
  • 僅在相鄰兩元素滿足嚴格大於（$A[j] > A[j+1]$）時才進行交換；若兩元素值相等則不交換，因此絕對保留原本的前後相對順序。

3. 插入排序法（Insertion Sort）

• 時間複雜度：
  • 最佳狀況：輸入數列已由小到大排序，每個新元素只需與已排序子陣列的最右側元素比較一次即確認位置，無須移動資料，共比較 $n-1$ 次，時間複雜度為 $O(n)$。
  • 平均狀況：每個新元素平均需向左搜尋並移動已排序子陣列中一半的元素，總時間複雜度為 $O(n^2)$。

8. 分類決策樹的分割節點選擇策略

核心觀念

決策樹在節點資料集合 $D$ 中，選擇一個屬性或切割條件，將資料分成 $D_1,D_2,\ldots,D_m$。選擇分割方式的目標，是讓分割後的子集合更加純粹。

分割後的不純度為：

$$I_{\text{split}}=\sum_{j=1}^{m}\frac{|D_j|}{|D|}I(D_j)$$

權重必須按照子集合的資料筆數計算，不能直接平均各子集合的不純度。

策略一：最大資訊增益（Information Gain）

先以熵衡量資料的不確定性：

$$H(D)=-\sum_{c=1}^{K}p_c\log_2p_c$$

其中 $p_c$ 是類別 $c$ 在資料集合 $D$ 中所占的比例。

某個分割方式 $s$ 的資訊增益為：

$$IG(D,s)=H(D)-\sum_{j=1}^{m}\frac{|D_j|}{|D|}H(D_j)$$

選擇使 $IG(D,s)$ 最大的分割方式。

優點：

• 具有清楚的資訊理論意義，表示分割後不確定性減少的程度。
• 適用於多分類問題。
• 若子節點全部屬於同一類別，則熵為 $0$，容易判斷分割效果。
• 對分類結果的解釋性良好。

缺點：

• 偏好具有許多不同取值的屬性。例如學號幾乎每筆資料都不同，以學號切割後各子集合可能只剩一筆資料，資訊增益卻很高，容易造成過度配適。
• 需要計算對數，運算量比 Gini 不純度稍高。
• 連續屬性必須搜尋多個切割門檻，可能產生較深的樹。
• 實務上常用 C4.5 的 Gain Ratio 修正多值屬性的偏好。

策略二：最小 Gini 不純度（Gini Index）

Gini 不純度定義為：

$$Gini(D)=1-\sum_{c=1}^{K}p_c^2$$

也可寫成：

$$Gini(D)=\sum_{c=1}^{K}p_c(1-p_c)$$

分割後的加權 Gini 不純度為：

$$Gini_{\text{split}}= \sum_{j=1}^{m}\frac{|D_j|}{|D|}Gini(D_j)$$

選擇使 $Gini_{\text{split}}$ 最小的分割方式。

優點：

• 不需計算對數，公式簡單，運算速度快。
• 適合 CART 決策樹的二元分割。
• 可處理多分類問題，也能自然處理連續屬性的切割門檻。
• Gini 值為 $0$ 表示該節點完全純粹，判斷直觀。

缺點：

• 只根據類別比例衡量純度，與資訊增益所選出的最佳分割不一定相同。
• 對類別屬性進行二元切割時，類別數很多會增加候選切割方式。
• 若沒有設定樹深度、最小樣本數或剪枝，仍然會產生過度配適。

解題技巧

• 資訊增益選「最大值」；Gini 不純度選「最小值」。
• 子節點的評估必須使用資料筆數加權。
• 熵與 Gini 都在節點完全純粹時達到 $0$。
• 具有大量不同取值的欄位，例如識別碼，通常不適合作為第一優先的分割屬性。

【答案】

可採用下列兩種策略：

1. 最大資訊增益法：選擇使資訊增益 $IG$ 最大的屬性或切割條件。優點是資訊意義清楚、適合多分類；缺點是偏好多值屬性，且容易過度配適。
2. 最小 Gini 不純度法：選擇使加權 Gini 不純度最小的屬性或切割條件。優點是計算簡單、速度快、適合 CART；缺點是與資訊增益的選擇可能不同，且仍須搭配剪枝避免過度配適。

---

9. 無人工廠工作排程的 Greedy 演算法

核心觀念

令工作 $J_i$ 的執行時間為：

$$p_i=T(J_i)$$

機器人 $M_k$ 所分配工作的總執行時間稱為負載：

$$L_k=\sum_{J_i\text{ 分配給 }M_k}p_i$$