109 年 國立高雄大學資訊工程學系碩士班《資料結構》

Insertion sort 的時間複雜度在最壞情況下是 $\Theta(n^2)$。

核心觀念： 插入排序法 (Insertion Sort) 的時間複雜度分析。

解題過程：
插入排序法的基本思想是逐步建立一個已排序的陣列。對於輸入的陣列，它一次處理一個元素，並將該元素插入到前面已排序的子陣列中的正確位置。

考慮一個包含 $n$ 個整數的向量。在最壞的情況下，輸入陣列是完全逆序的。例如，對於陣列 $[5, 4, 3, 2, 1]$，當我們處理每一個元素時，都需要將它與前面所有已排序的元素進行比較和移動，才能找到其正確的位置。

具體來說，對於第 $i$ 個元素（從 1 開始計數），在最壞情況下，它需要與前面 $i-1$ 個元素進行比較，並可能移動 $i-1$ 次。

• 當處理第二個元素時，最多需要 1 次比較和 1 次移動。
• 當處理第三個元素時，最多需要 2 次比較和 2 次移動。
• ...

插入排序法 (Insertion Sort) 在最佳情況下的時間複雜度是 $\Theta(n)$。

核心觀念： 插入排序法 (Insertion Sort) 的最佳情況時間複雜度分析。

解題過程：
插入排序法的最佳情況發生在輸入的陣列已經是排序好的情況下。例如，對於陣列 $[1, 2, 3, 4, 5]$。

當我們處理第 $i$ 個元素時，它需要與前面已排序的子陣列進行比較，以找到其正確的位置。

• 在最佳情況下，第 $i$ 個元素總是比前面所有元素都大（或者剛好排在最後）。
• 因此，對於第 $i$ 個元素，只需要與已排序子陣列的最後一個元素進行一次比較，就可以確定它的位置（即插入到最後）。
• 不需要進行任何元素的移動。

對於一個包含 $n$ 個元素的陣列，我們需要處理 $n$ 個元素。

• 對於第二個元素，進行 1 次比較。
• 對於第三個元素，進行 1 次比較。
• ...
• 對於第 $n$ 個元素，進行 1 次比較。

核心觀念

本題考查 Big-O 的定義。

對非負函數 $f(n)$ 與 $g(n)$，若存在常數 $c>0$ 與正整數 $n_0$，使得對所有 $n\ge n_0$，

則稱

本題需證明存在固定常數 $c$，使 $n!$ 被 $c n^n$ 上界住，且不可使用極限。

解題方法

將階乘展開：

當 $1\le k\le n$ 時，每一個因子皆滿足

因此，$n!$ 的 $n$ 個因子都不大於 $n$，相乘可得

核心觀念
堆疊（Stack）具備後進先出（LIFO）之特性。將字串字元依序推入（Push）堆疊後，依序彈出（Pop）所獲得的序列即為原字串的反轉序列。若原字串與反轉序列完全一致，則該字串即為迴文（Palindrome）。

演算法虛擬碼（Pseudocode）

核心觀念

Max-heap 必須同時符合：

1. 完全二元樹：新增節點放在最後一個空位置。
2. 最大堆積性：每個父節點值皆不小於其子節點。

新增元素使用「向上調整」；刪除最大值使用「最後節點補到根，再向下調整」。

解題方法

初始 max-heap 以陣列表示為：

其樹狀結構為：

          90
       /      \
     52        81
   /   \      /  \
 25    18    45   73
/ \    /
12 13 71

一、加入 65

將 $65$ 放入最後空位，成為 $18$ 的右子節點：

          90
       /      \
     52        81
   /   \      /  \
 25    18    45   73
/ \    / \
12 13 71 65

因為 $65>18$，交換：

此時 $65$ 的父節點為 $52$，且 $65>52$，再次交換：

加入 $65$ 後的 max-heap 為：

(a) 建立二元搜尋樹（Binary Search Tree, BST）

建構規則：依序讀入資料，若新數值小於目前節點走左子樹，大於走右子樹。

插入步驟：

1. 插入 $5$：建立根節點 $5$。
2. 插入 $9$：$9 > 5$，位於 $5$ 的右子節點。
3. 插入 $3$：$3 < 5$，位於 $5$ 的左子節點。
4. 插入 $15$：$15 > 5 \rightarrow 15 > 9$，位於 $9$ 的右子節點。
5. 插入 $2$：$2 < 5 \rightarrow 2 < 3$，位於 $3$ 的左子節點。
6. 插入 $17$：$17 > 5 \rightarrow 17 > 9 \rightarrow 17 > 15$，位於 $15$ 的右子節點。

二元搜尋樹結構：

       5
     /   \
    3     9
   /       \
  2        15
             \
             17

【答案】二元搜尋樹結構如上圖所示。

(b) 尋找最接近 8 的整數

距離採用絕對值距離 $d(x, 8) = |x - 8|$。自根節點向下搜尋，同時維護最小距離 $d_{\min}$ 與對應的最近節點。

搜尋步驟：

1. 訪問根節點 $5$：
   • 計算距離：$d(5, 8) = |5 - 8| = 3$。
   • 目前最近節點設為 $5$，$d_{\min} = 3$。
   • 因 $8 > 5$，向右子樹搜尋。
2. 訪問節點 $9$：
   • 計算距離：$d(9, 8) = |9 - 8| = 1$。
   • 因 $1 < 3$，更新最近節點為 $9$，$d_{\min} = 1$。
   • 因 $8 < 9$，向左子樹搜尋。
3. 到達 NULL（空節點）：
   • 搜尋終止。

【答案】最接近 8 的整數為 9（距離為 1）。

(c) 建立 2-d Tree ($k=2$)

建構規則：

• 依深度 $d$ 輪流交替切分軸（從 $d=0$ 開始）。
• 偶數層（$d=0, 2, \dots$）：依 $X$ 座標比較。
• 奇數層（$d=1, 3, \dots$）：依 $Y$ 座標比較。

依序插入步驟：

1. 插入 $(5, 7)$（深度 0，依 $X$）：建立根節點 $(5, 7)$。
2. 插入 $(9, 4)$（深度 0，依 $X$）：$9 > 5$，作為 $(5, 7)$ 之右子節點。
3. 插入 $(3, 6)$（深度 0，依 $X$）：$3 < 5$，作為 $(5, 7)$ 之左子節點。
4. 插入 $(15, 2)$：
   • 深度 0（依 $X$）：$15 > 5 \rightarrow$ 走右至 $(9, 4)$。
   • 深度 1（依 $Y$）：$2 < 4 \rightarrow$ 作為 $(9, 4)$ 之左子節點。
5. 插入 $(2, 5)$：
   • 深度 0（依 $X$）：$2 < 5 \rightarrow$ 走左至 $(3, 6)$。
   • 深度 1（依 $Y$）：$5 < 6 \rightarrow$ 作為 $(3, 6)$ 之左子節點。
6. 插入 $(17, 8)$：