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

核心觀念

• 時間複雜度 (Time Complexity)：描述演算法隨著輸入規模增長，其執行時間的漸近上界。常用的大 O 表示法只關心最壞情況的上界。
• 排序演算法的下界：在比較模型 (comparison‑based model) 中，任意能正確排序的比較排序必須至少比較 $\Omega(n\log n)$ 次（資訊理論下界）。
• 非比較排序：對特定資料型別（例如整數、字元）可利用基數排序、計數排序或桶排序等，這些演算法的時間複雜度可達 $O(n)$，但它們依賴於資料的鍵值範圍或位元長度，而非純粹的比較操作。

解題方法

1. 判斷敘述的範圍：題目未限定「比較排序」或「任意排序」的類型。
2. 若以比較模型為前提：
   • 根據比較排序的資訊理論下界，任何正確的比較排序在最壞情況下必須執行至少 $\Omega(n\log n)$ 次比較。
   • 因此其時間複雜度的下界是 $\Omega(n\log n)$，而 $O(n^2)$ 只是一個較寬鬆的上界。雖然 $O(n^2)$ 仍然「成立」於所有比較排序（因為 $n\log n \in O(n^2)$），但此敘述無法提供嚴格的界限，且在嚴格的「等價」意義上是不正確的。
3. 若允許非比較排序：
   • 計數排序、基數排序、桶排序在合適的輸入限制下可達 $O(n)$。這些演算法的時間複雜度明顯低於 $O(n^2)$。
   • 因此，存在排序演算法的時間複雜度 不 為 $O(n^2)$（例如 $O(n)$），敘述必然為 假。

核心觀念

• Insertion Sort：對於長度為 $n$ 的輸入陣列 $A[1..n]$，外層迴圈從第 $2$ 個元素開始，將其插入已排序好的前 $i-1$ 個元素之中。
• 時間複雜度的定義：
  • 最佳情況 (best‑case) 指所有可能的輸入中，使演算法執行時間最小的那一類輸入。
  • $\Theta$ 表示上下界相同的漸進量級，即存在常數 $c_1,c_2>0$ 使 $c_1f(n)\le T(n)\le c_2f(n)$ 成立於充分大的 $n$。

解題方法

1. 分析最佳情況的輸入
   • 當陣列已經 完全排序（遞增）時，插入排序的內層 while 迴圈在每一次外層迭代只檢查一次 $A[j] \le A[j+1]$ 即可停止。
2. 計算比較與搬移次數
   • 第 $i$ 次外層迭代（$i=2,\dots,n$）只做 一次比較，且不需要搬移元素。
   • 總比較次數 $C_{\text{best}} = \sum_{i=2}^{n} 1 = n-1 = \Theta(n)$。
   • 總搬移次數 $M_{\text{best}} = 0$（已排序陣列不需要搬移）。
3. 求得時間複雜度

核心觀念

• NP：可在多項式時間內由非確定式圖靈機驗證的問題集合。
• NP‑hard：對所有 $L\in\text{NP}$，都有 $L\le_{p} H$（多項式時間可還原），即 $H$ 至少和 NP 中最難的問題一樣難。
• NP‑complete：同時屬於 NP 與 NP‑hard。

解題方法
判斷敘述的正確性，只需檢視「NP‑hard 是否必然落在 NP」的定義關係。

• 若「NP‑hard ⊆ NP」成立，則所有 NP‑hard 問題皆為 NP，等價於「所有 NP‑hard 問題皆為可在多項式時間驗證」；
• 事實上，NP‑hard 包含許多已知不屬於 NP 的問題（例如 HALTING、TQBF、最優化問題的近似版本），只要找出一個反例即可斷定敘述為 False。

核心觀念

• NP（Non‑deterministic Polynomial time）：一類決策問題，若答案為 YES，存在多項式長度的驗證證明，使得在多項式時間內可以驗證。
• NP‑Complete：屬於 NP，且所有 NP 問題皆可在多項式時間內「多項式歸約」到此問題。換言之，NP‑Complete 是 NP 中「最難」的一群問題。
• P ≠ NP（題目假設）：表示至少存在至少一個屬於 NP 而不屬於 P 的問題。

解題方法

1. 判斷敘述的邏輯結構：

$\text{「若 }x\in \text{NP，則 }x\in \text{NP‑Complete」}$

這是充分條件的說法，等價於「NP ⊆ NP‑Complete」。
2. 依據定義，NP‑Complete ⊆ NP（即每個 NP‑Complete 必然屬於 NP），但反向包含 不成立，因為 NP 中還包含許多「較易」的問題（如 SAT 的子問題、圖的連通性、最短路徑決策問題等）。
3. 用反例直接證偽：只要找出一個屬於 NP 但不是 NP‑Complete 的問題，即可證明敘述為假。

核心觀念

1. Dijkstra 演算法的本質（Greedy Approach）：
   Dijkstra 演算法是一種貪婪演算法（Greedy Algorithm）。其演算法的核心不變性（Invariant）建立在**邊權重皆為非負（Non-negative Edge Weights）**的假設上：
   • 當一個頂點 $u$ 被從未拜訪集合（Unvisited Set）中挑選出並標記為「已確定最短路徑」（Visited / Finalized）時，演算法假設：往後透過其他未走訪的頂點，其累加路徑長度只會增加或維持不變，不可能透過後續路徑使得到達 $u$ 的距離變得更短。
   • 每個節點一旦出隊（Pop / Finalize）並完成鬆弛（Relaxation），便不再被更新。
2. 負權重邊（Negative Edge Weights）破壞貪婪選擇性：
   若圖中存在負權重邊（即使沒有負權重環 Negative Cycle），一條「節點數較多或看似總權重較大的路徑」，可能會因為中途或後段包含大幅度的負權重邊，導致其真實路徑總長反而小於已提早被標記為 Finalized 的路徑。由於經典 Dijkstra 演算法不會重新走訪已確定節點，因而會計算出錯誤的最短路徑。

解題方法

題目要求建構一個包含**起點（Source）與終點（Destination）**的反例圖（Counterexample Graph），並逐步展示 Dijkstra 演算法在此圖上為何會失敗。

1. 反例圖建構

給定有向圖 $G = (V, E)$，其中頂點集合 $V = \{S, A, B\}$：

• 起點（Source）：$S$
• 終點（Destination）：$B$
• 中間節點：$A$

邊與權重集合 $E$ 定義如下：

1. $(S, B)$，權重為 $5$
2. $(S, A)$，權重為 $2$
3. $(A, B)$，權重為 $-4$

       [ 2 ]           ( -4 )
 (S) ---------> (A) ------------> [B]
  |                                ^
  |             [ 5 ]              |
  +--------------------------------+

* 起點 (Source)       : S
* 終點 (Destination)  : B

2. Dijkstra 演算法執行過程

設 $d[v]$ 表示從起點 $S$ 到頂點 $v$ 的最短估計距離，$S_{visited}$ 為已確定（Finalized）的頂點集合。

• 初始化（Initialization）：
  $d[S] = 0,\quad d[A] = \infty,\quad d[B] = \infty$
  $S_{visited} = \emptyset$

• 第 1 步（訪問起點 $S$）：

  • 從未造訪集合中挑選 $d$ 值最小的頂點：選取 $S$（因為 $d[S] = 0$）。
  • 將 $S$ 加入已確定集合：$S_{visited} = \{S\}$。
  • 對 $S$ 的外向邊進行鬆弛（Relaxation）：
    • 鬆弛邊 $(S, A)$：$d[A] = \min(\infty, d[S] + 2) = 2$
    • 鬆弛邊 $(S, B)$：$d[B] = \min(\infty, d[S] + 5) = 5$

• 第 2 步（貪婪選擇 $A$）：

  • 未造訪節點為 $\{A, B\}$，目前 $d[A] = 2$、$d[B] = 5$。
  • 挑選最小者：選取 $A$。
  • 將 $A$ 加入已確定集合：$S_{visited} = \{S, A\}$。
  • 對 $A$ 的外向邊進行鬆弛：

核心觀念
紅黑樹 (Red‑Black Tree) 與雜湊表 (Hash Table) 均屬於動態資料結構，用於維持資料的插入、刪除與搜尋。

• 紅黑樹是一種自平衡二元搜尋樹，保證在最壞情況下的高度為 $2\log_2 (n+1)$，因此所有基本操作的時間複雜度皆為 $O(\log n)$。
• 雜湊表透過雜湊函式將鍵映射至陣列索引，平均情況下操作為 $O(1)$，但最壞情況下可能退化為 $O(n)$（全部碰撞於同一桶）且需要重新雜湊 (rehashing) 來維持負載因子。

解題方法
題目要求列舉兩項紅黑樹相較於雜湊表的優勢。

1. 有序性 (Ordered Traversal)

   • 紅黑樹保留鍵值的全序關係，任意時間皆可透過中序走訪得到遞增序列，或在 $O(\log n)$ 時間內執行範圍查詢 (range query)。
   • 雜湊表的鍵值分佈是隨機的，無法直接支援有序走訪或範圍查詢，若需此功能必須額外維護排序結構或將鍵先收集再排序，導致額外 $O(n\log n)$ 開銷。

2. 最壞情況保證 (Worst‑case Guarantees)

   • 紅黑樹的自平衡性保證 所有操作的時間上界都是 $O(\log n)$，且此上界在任何資料分佈下都成立。
   • 雜湊表在雜湊函式不佳、負載因子過高或大量碰撞時，最壞情況會退化為線性搜尋 $O(n)$，且重新雜湊的時間成本不可忽視。

核心觀念

• 獨立集 (Independent Set)：圖 $G=(V,E)$ 中任意兩個頂點 $u,v\in I$ 都不相鄰，即 $(u,v)\notin E$。
• 樹 (Tree)：連通且無環的無向圖。樹的結構允許以「根」為基礎做自底向上的 DP，因為子樹之間僅透過父子邊相連。
• 動態規劃 (Dynamic Programming) on Tree：對每個節點 $x$ 記錄兩種狀態
  1. 包含 $x$（$dp[x][1]$）
  2. 不包含 $x$（$dp[x][0]$）
     兩種狀態之遞迴關係僅與子節點的 $dp$ 值有關，故可在一次 DFS 走訪中完成。

解題方法

1. 選擇根節點
   任意將樹視為有根樹 (如選 $1$ 為根)。之後以 DFS（或遞迴）自下而上計算 $dp$。

2. 狀態定義

   • $dp[u][1]$：以 $u$ 為根的子樹中，必須選取 $u$ 的最大獨立集大小。
   • $dp[u][0]$：以 $u$ 為根的子樹中，不選取 $u$ 的最大獨立集大小。

3. 遞迴關係

   • 若選取 $u$，則所有子節點 $v$ 必須 不選（否則會與 $u$ 相鄰）：
     $dp[u][1] = 1 + \sum_{v\in \text{child}(u)} dp[v][0]$
   • 若不選取 $u$，子節點 $v$ 可以自行決定選或不選，採較大者：
     $dp[u][0] = \sum_{v\in \text{child}(u)} \max\big(dp[v][0],\,dp[v][1]\big)$

4. 演算流程

核心觀念

• 單向鏈結串列 (singly linked list)：每個節點僅保存指向下一個節點的指標，無法直接跳至任意位置。
• 排序性 (sorted)：串列內的資料依遞增順序排列，但排序本身不提供隨機存取的能力。
• 二分搜尋的條件：二分搜尋要求能在 $O(1)$ 時間取得「中間」元素的地址，以便遞迴或迭代切割搜尋範圍。
• 資訊理論下的搜尋下界：在只能順序訪問的資料結構中，搜尋任何目標的最壞情況時間下界為 $\Theta(n)$，即使資料已排序。

解題方法

1. 分析可行的操作

   • 從頭節點 $head$ 開始，只能使用「指向下一個」的 next 指標前進。
   • 任意一次操作只能檢查當前節點的值並移至下一節點。

2. 嘗試二分搜尋的思路

   • 二分搜尋需要在 $O(1)$ 時間定位 $L$ 中間的節點。
   • 由於單向鏈結串列缺乏「指向任意位置」的指標，取得中間節點必須從頭逐一走過 $n/2$ 個節點，耗時 $O(n)$。

3. 建立下界證明

   • 假設存在一個 $O(\log n)$ 的演算法 $A$，僅使用 $head$ 的地址與比較操作。
   • 為了找出目標 $k$，$A$ 必須在每一步決定「向左」或「向右」子區間。
   • 但「向左」子區間的左端必須是目前已知的最左節點，唯一可取得的下一個節點仍是 next，無法直接跳至子區間的中點。

核心觀念

• 圖的週期 (cycle)：在無向圖中，若存在一組不同的頂點 $v_1,\dots,v_k$ 使得相鄰兩點皆有邊相連且 $v_1=v_k$，則稱為長度為 $k$ 的週期。
• 最短週期 (girth)：圖中所有週期的最小長度。判斷是否有長度 $\le n/2$ 的週期，只要找到圖的最短週期，與 $n/2$ 比較即可。
• Breadth‑First Search (BFS)：在無向圖中，以一個起點 $s$ 為根的 BFS 樹可同時得到從 $s$ 到其他每個頂點的最短距離。當在 BFS 過程中發現一條「非樹」邊 $(u,v)$ 時，會形成一個以 $s$ 為端點的週期，長度為
  $\text{len}(u,v)=\operatorname{dist}(s,u)+\operatorname{dist}(s,v)+1.$
  這個長度即是包含 $s$ 的 最短 週期之一。

解題方法

1. 遍歷所有起點：對每一個頂點 $s\in V(G)$，執行一次 BFS，同時記錄從 $s$ 到每個頂點的距離 $\operatorname{dist}_s(\cdot)$。
2. 偵測非樹邊：在 BFS 探索過程中，若從當前頂點 $u$ 探索到已被拜訪的鄰點 $v$，且 $v$ 不是 $u$ 的父節點，則此邊為「非樹」邊。此時計算
   $c = \operatorname{dist}_s(u)+\operatorname{dist}_s(v)+1,$
   並把 $c$ 與全局最小值 $\text{best}$ 更新（初始設為 $\infty$）。
3. 判斷結果：在所有 $n$ 次 BFS 完成後，若 $\text{best}\le \frac{n}{2}$，輸出 Yes；否則輸出 No。

算法偽碼

核心觀念

• 二元堆（binary heap）之陣列表示：

  • 若使用 1‑索引（最常見的教科書寫法），則
    • 父節點索引 = $\left\lfloor\dfrac{i}{2}\right\rfloor$
    • 左子節點索引 = $2i$，右子節點索引 = $2i+1$
  • 若使用 0‑索引（某些程式語言的實作），則
    • 父節點索引 = $\left\lfloor\dfrac{i-1}{2}\right\rfloor$
    • 子節點索引 = $2i+1$（左）與 $2i+2$（右）

• 題目條件：二元堆共有 500 個節點，子節點 $u$ 的鍵值儲存在 Arr[305]，求其父節點 $p$ 的鍵值所在的陣列位置。

解題方法

1. 確定索引制式

   • 本題僅給出「binary heap」與「array representation」的描述，未明示是 1‑索引或 0‑索引。
   • 兩種制式在本題 皆得到相同的父索引，因此無須另行判斷，只要使用下列公式即可。

2. 套用父節點索引公式

   • 以 1‑索引為例：父節點 $p$ 的索引
     $\text{parentIdx}= \left\lfloor \frac{305}{2} \right\rfloor = 152$
   • 若採 0‑索引：父節點索引
     $\text{parentIdx}= \left\lfloor \frac{305-1}{2} \right\rfloor = 152$

   因此 父節點 $p$ 的鍵值儲存在 Arr[152]。

核心觀念

• 二元堆 (binary heap) 的陣列表示：若節點的索引為 $i$，則
  • 左子節點的索引為 $2i$
  • 右子節點的索引為 $2i+1$
  • 父節點的索引為 $\left\lfloor i/2\right\rfloor$
• 存在性判斷：在一個含有 $n$ 個節點的二元堆中，只有當子節點的索引 $\le n$ 時，該子節點才真的存在於堆內。

解題方法

1. 已知 $u$ 的鍵值儲存在 $Arr[305]$，因此 $u$ 在陣列中的索引為 $i_u = 305$。
2. 計算 $u$ 的左子節點索引：
   $i_{\text{left}} = 2 \times i_u = 2 \times 305 = 610$
3. 檢查左子節點索引是否在堆的範圍內。