109 年 國立政治大學資訊科學系碩士班《資料結構與演算法》

核心觀念

本題考查四種經典演算法的「最壞情況時間複雜度」：

• Binary search：每次比較都將搜尋範圍縮小為原來的一半。
• Binary heap 建構：使用 bottom-up heap construction 時，不是對每個元素個別插入。
• Randomized quicksort：隨機化只能改善平均情況，無法排除最壞情況。
• Kruskal algorithm：總時間主要由邊排序與 disjoint-set 操作決定。

---

1.1 排序陣列上的 Binary search

解題方法

Binary search 每次選取中間元素與目標值比較：

• 若目標值等於中間元素，搜尋結束。
• 若目標值較小，只搜尋左半部。
• 若目標值較大，只搜尋右半部。

每次搜尋後，候選範圍約縮小為一半，因此可建立遞迴式：

$$T(n)=T\left(\frac{n}{2}\right)+\Theta(1)$$

展開 $k$ 次後，問題規模變為：

$$\frac{n}{2^k}$$

當範圍縮小至 $1$ 時：

$$\frac{n}{2^k}=1 \quad\Longrightarrow\quad k=\log_2 n$$

每層只進行常數次比較，因此：

$$T(n)=\Theta(\log n)$$

最壞情況發生在目標值不存在，或目標值位於最後一次才被找到的位置。

---

1.2 從未排序陣列建構 Binary heap

核心觀念

若使用 bottom-up heap construction，也稱為 Floyd’s heap construction，會從最後一個非葉節點開始，依序向前執行 sift-down。

高度為 $h$ 的節點，其 sift-down 最多需要 $\Theta(h)$ 時間。雖然根節點可能需要 $\Theta(\log n)$ 時間，但高高度節點數量很少。

解題方法

將所有節點依高度分類：

• 高度為 $0$ 的節點約有 $\frac{n}{2}$ 個，每個成本為 $\Theta(1)$。
• 高度為 $1$ 的節點約有 $\frac{n}{4}$ 個，每個成本為 $\Theta(1)$。
• 高度為 $2$ 的節點約有 $\frac{n}{8}$ 個，每個成本為 $\Theta(2)$。
• 依此類推。

總成本可表示為：

$$T(n) = \Theta\left( n\sum_{h=0}^{\log n}\frac{h}{2^h} \right)$$

由於級數

$$\sum_{h=0}^{\infty}\frac{h}{2^h}$$

收斂為常數，因此：

$$T(n)=\Theta(n)$$

所以，從未排序陣列以 bottom-up 方法建構 binary heap 的最壞情況時間複雜度為：

$$\boxed{\Theta(n)}$$

常見陷阱

若逐一將 $n$ 個元素插入空 heap，每次插入成本最壞為 $\Theta(\log n)$，總成本為：

$$\Theta(n\log n)$$

但題目問的是「從未排序陣列建構 heap」，通常採用 bottom-up 方法，因此答案是 $\Theta(n)$。

---

1.3 Randomized quicksort

核心觀念

Randomized quicksort 隨機選擇 pivot。隨機化能使平均分割較平衡，因此期望時間複雜度為：

$$\Theta(n\log n)$$

但最壞情況仍可能發生。隨機選出的 pivot 可能在每一層都是目前陣列中的最小值或最大值，使分割結果為：

$$0 \quad\text{與}\quad n-1$$

解題方法

在最壞情況下，遞迴式為：

$$T(n)=T(n-1)+\Theta(n)$$

其中 $\Theta(n)$ 是 partition 的成本。

展開：

核心觀念

動態陣列使用一段連續記憶體儲存元素，維護兩個欄位：

• size：目前元素數量。
• capacity：目前已配置的儲存容量。

陣列元素存放於 data[0] 到 data[size - 1]。

當陣列已滿時，配置一段容量加倍的新陣列，複製原有元素後再插入新元素。雖然單次擴充需要 $O(n)$ 時間，但連續執行 $n$ 次插入時，總複製次數為

$$1+2+4+\cdots+2^{\lfloor \log_2 n \rfloor}<2n$$

因此插入的攤銷時間為 $O(1)$。

---

解題方法

假設元素型別為 int，初始容量設定為 $1`。陣列採用「容量不足時加倍」的策略。

2.1 Initializing an empty array

typedef struct {
    int *data;
    int size;
    int capacity;
} DynamicArray;

DynamicArray *initArray() {
    DynamicArray *a = malloc(sizeof(DynamicArray));

    a->capacity = 1;
    a->size = 0;
    a->data = malloc(a->capacity * sizeof(int));

    return a;
}

初始化後：

$$size=0,\qquad capacity=1$$

只配置固定大小的初始空間，因此時間複雜度為：

$$O(1)$$

空間複雜度為：

$$O(1)$$

---

2.2 Inserting a new element at the end

void pushBack(DynamicArray *a, int value) {
    if (a->size == a->capacity) {
        int newCapacity = 2 * a->capacity;
        int *newData = malloc(newCapacity * sizeof(int));

        for (int i = 0; i < a->size; i++) {
            newData[i] = a->data[i];
        }

        free(a->data);
        a->data = newData;
        a->capacity = newCapacity;
    }

    a->data[a->size] = value;
    a->size++;
}

當陣列尚未滿時，只需將元素放在 data[size]：

$$T(n)=O(1)$$

當陣列已滿時，需複製 $n$ 個元素：

$$T(n)=O(n)$$

但容量每次加倍，因此執行 $n$ 次插入所需的總複製成本為：

$$1+2+4+\cdots+2^{\lfloor\log_2 n\rfloor}=O(n)$$

再加上每次插入本身的 $O(1)$ 成本，總時間為 $O(n)$，所以單次插入的攤銷時間為：

$$\frac{O(n)}{n}=O(1)$$

最壞單次時間為 $O(n)$，攤銷時間為 $O(1)

核心觀念

兩棵二元樹「完全相同」必須同時滿足：

1. 對應位置的節點結構相同。
2. 對應位置的節點值相同。

對任意兩個對應節點 tree1 與 tree2，可依下列遞迴定義判斷：

• 兩者皆為 NULL：代表此位置結構相同。
• 僅有一者為 NULL：代表結構不同。
• 兩者皆存在但 value 不同：代表內容不同。
• 兩者皆存在且值相同：必須繼續比較左子樹與右子樹。

因此，兩棵樹相同的條件為：

$$equal(T_1,T_2) = (T_1.value=T_2.value) \land equal(T_{1.left},T_{2.left}) \land equal(T_{1.right},T_{2.right})$$

此定義的前提是兩個根節點都存在。

解題方法

採用遞迴搭配前序走訪的方式，從根節點開始同步比較兩棵樹。

每次呼叫 equal(tree1, tree2) 時，依序處理：

1. 若 tree1 與 tree2 都是 NULL，回傳 true。
2. 若只有一個是 NULL，回傳 false。
3. 若兩個節點的值不同，回傳 false。
4. 遞迴比較兩個左子樹及兩個右子樹，兩者都相同才回傳 true。

C 程式碼

核心觀念

本題要求在 $m \times n$ 矩陣中，找出一個「連續矩形子矩陣」，使其中所有元素總和最大。子矩陣必須由連續的列與連續的欄所構成。

核心技巧是將二維問題降成多次一維最大子陣列問題：

1. 固定子矩陣的上界與下界。
2. 將上下界之間每一欄的元素加總，形成一維陣列。
3. 在此一維陣列中找最大連續子陣列，即可決定子矩陣的左界與右界。

一維最大連續子陣列問題可用 Kadane’s algorithm 在 $O(n)$ 時間內完成。

---

解題方法

1. 固定上界與下界

假設子矩陣的上界為第 $top$ 列，下界為第 $bottom$ 列，其中

$$0 \le top \le bottom < m$$

對每一欄 $j$，計算第 $top$ 列到第 $bottom$ 列的總和：

$$colSum[j] = \sum_{i=top}^{bottom} M[i][j]$$

此時，若選擇連續欄位 $left$ 到 $right$，其對應子矩陣的總和為：

$$\sum_{j=left}^{right} colSum[j]$$

因此，固定 $top$ 與 $bottom$ 後，原問題就轉化為：

在一維陣列 colSum 中，尋找總和最大的連續區段。

這正是一維最大子陣列問題。

---

2. 使用 Kadane’s algorithm 找最佳欄範圍

對於一維陣列 colSum，定義：

• currentSum：以目前欄位作為右端點時，仍值得延伸的最佳連續區段總和。
• bestSum：目前看過的所有連續區段中的最大總和。

遞迴關係為：

$$currentSum = \max(colSum[j],\ currentSum + colSum[j])$$

意義如下：

• 若前一段的 currentSum 加上 colSum[j] 更好，就延續前一段。
• 若直接從第 $j$ 欄重新開始更好，就捨棄前面的區段。

為了處理矩陣中所有元素皆為負數的情況，不能將初始答案固定為 $0$，必須將答案初始化為負無限大，並允許選取只包含一個元素的子矩陣。

---

演算法流程

對每一個可能的上界 top：

1. 將 colSum[0..n-1] 全部設為 $0$。
2. 逐步增加下界 bottom。
3. 將第 bottom 列加入 colSum： $$colSum[j] \leftarrow colSum[j] + M[bottom][j]$$
4. 對目前的 colSum 執行 Kadane’s algorithm。
5. 若得到更大的總和，更新最佳子矩陣的上下左右界。

---

關鍵偽程式碼

解法概述
利用動態規劃判斷前 $i$ 個字元是否可由字典 $D$ 完全組成。設

$$dp[i]=\begin{cases} \text{true} & \text{若 }s[0..i-1]\text{ 可被分割成字典中的單詞}\\ \text{false}&\text{否} \end{cases}$$

初始化 $dp[0]=\text{true}$，其餘 $dp[i]=\text{false}$。對每個位置 $i$（$1\le i\le n$），檢查所有字典單詞 $w\in D$，若 $|w|\le i$ 且 $dp[i-|w|]=\text{true}$ 且 $s[i-|w|..i-1]=w$，則設 $dp[i]=\text{true}$，並可提前跳出內層迴圈。

最後答案為 $dp[n]$。

---

偽代碼