109 年 國立臺灣大學電信工程學研究所丙組《資料結構與演算法》

核心觀念

本題考查廣度優先搜尋（Breadth-First Search, BFS）的分層性質：

• BFS 從來源頂點 $s$ 開始，第 $0$ 層為 $s$。
• 第 $k$ 層的頂點，其到 $s$ 的最短距離為 $k$。
• 因此，若頂點 $v$ 在第 $k$ 層被拜訪，則：

$$\operatorname{dist}(s,v)=k$$

這表示存在一條長度為 $k$ 的路徑從 $s$ 到 $v$，且不存在長度小於 $k$ 的路徑。

解題方法

題目敘述為：

若頂點 $v$ 在從 $s$ 開始的 BFS 第 $k$ 層被拜訪，則從 $s$ 到 $v$ 的每一條路徑長度至多為 $k$。

BFS 的正確性質是：

$$\text{每一條從 }s\text{ 到 }v\text{ 的路徑長度} \ge k$$

因為若存在某條路徑長度小於 $k$，BFS 應該會在更早的層數發現 $v$。

但題目說的是「每一條路徑長度至多為 $k$」，也就是要求：

核心觀念

深度優先搜尋（Depth-First Search, DFS）的時間複雜度取決於圖的表示方式。

• 使用 adjacency list：DFS 時間複雜度為 $O(V+E)$。
• 使用 adjacency matrix：為了找出某一頂點的所有鄰接頂點，必須掃描該頂點對應的整列矩陣，共 $V$ 個位置。

雖然圖中實際邊數為 $E$，adjacency matrix 仍會逐一檢查所有可能的邊，因此其時間複雜度通常為 $O(V^2)$。

解題方法

DFS 對每個頂點至多拜訪一次。若圖以 adjacency matrix $A$ 表示，當 DFS 拜訪頂點 $u$ 時，必須檢查：

$$A[u][1], A[u][2], \ldots, A[u][V]$$

以判斷 $u$ 是否與其他頂點相鄰。因此，處理一個頂點需要 $O(V)$ 時間。

最多有 $V$ 個頂點被拜訪，總時間為：

$$V \times O(V)=O(V^2)$$

若圖不連通，完整 DFS 通常會以迴圈檢查所有頂點是否已拜訪；這部分需要 $O(V)$，仍被 $O(V^2)$ 主導。

此外，adjacency matrix 本身需要儲存 $V \times V$ 個位置，因此空間複雜度為：

$$O(V^2)$$

選項分析

題目只有一個是非敘述：

核心觀念

廣度優先搜尋（BFS）依照「邊數」由少到多探索頂點，因此能保證的是：

• 在無權圖，或每條邊權重皆相同的圖中，找到從起點 $s$ 到各頂點的最短路徑。
• BFS 的時間複雜度為 $O(|V|+|E|)$。

但加權圖的最短路徑是依據總權重判定，而非邊數。從 $s$ 到頂點 $v$ 的路徑權重為：

$$w(P)=\sum_{e\in P}w(e)$$

BFS 只會選擇邊數較少的路徑，無法處理不同邊權重造成的差異。

解題方法

判斷此敘述是否正確，必須檢查 BFS 的最短路徑性質是否適用於「weighted undirected graph」。

取一個無向加權圖：

• 邊 $(s,a)$ 的權重為 $10$
• 邊 $(s,b)$ 的權重為 $1$
• 邊 $(b,a)$ 的權重為 $1$

從 $s$ 到 $a$ 有兩條路徑：

1. 直接路徑 $s\to a$：

$$w(s,a)=10$$

2. 間接路徑 $s\to b\to a$：

$$w(s,b)+w(b,a)=1+1=2$$

因此真正的加權最短路徑是：

$$s\to b\to a$$

然而 BFS 依照邊數探索：

核心觀念

本題考查「樹的唯一路徑性質」與「廣度優先搜尋（BFS）的時間複雜度」。

對任意樹 $G=(V,E)$：

• 樹是連通圖。
• 樹不含環。
• 任意兩個頂點之間恰有一條簡單路徑。
• 因此，從起點 $s$ 到任意頂點 $v$ 的路徑是唯一的。

若邊具有權重，路徑長度定義為該路徑上所有邊權重的總和：

$$\operatorname{dist}(s,v)=\sum_{e\in P(s,v)}w(e)$$

在標準假設下，邊權重為非負數。由於樹中不存在另一條路徑可供比較，這條唯一路徑自然就是從 $s$ 到 $v$ 的最短路徑。

---

解題方法

BFS 從 $s$ 開始走訪圖形，當頂點 $v$ 第一次被發現時，記錄其父節點 $\operatorname{parent}[v]$。

由於原圖本身就是樹：

1. $s$ 到 $v$ 的路徑唯一。
2. BFS 所記錄的 parent pointers 會形成一棵以 $s$ 為根的樹。
3. 從 $v$ 沿著 parent pointers 回溯至 $s$，所得路徑必定是原樹中唯一的 $s$–$v$ 路徑。
4. 該路徑因此就是 $s$ 到 $v$ 的最短路徑。

加權距離可在 BFS 發現新頂點時一併計算：

$$d[s]=0$$

若 $v$ 是由 $u$ 發現，則設定：

$$d[v]=d[u]+w(u,v)$$

因為 $u$ 到 $v$ 的唯一路徑就是「$s$ 到 $u$ 的唯一路徑」接上邊 $(u,v)$，所以此遞迴式所得的 $d[v]$ 正確。

---

時間複雜度分析

核心觀念

本題考查樹的結構與單源最短路徑（Single-Source Shortest Paths, SSSP）：

• 樹是連通且無環的無向圖。
• 任意兩個頂點之間恰好存在唯一一條簡單路徑。
• 因此，從起點 $s$ 到任意頂點 $v$ 的唯一路徑，必然也是最短路徑；不需要比較其他路徑。
• DFS 的 parent pointers 會記錄從 $s$ 出發搜尋時所形成的樹狀父子關係。在原圖本身就是樹的情況下，$v$ 往上追溯 parent pointers，正好得到 $s$ 到 $v$ 的唯一路徑。

邊權重不影響上述結論。即使邊權為負數，樹中仍然沒有環，因此不會產生負權環；唯一的 $s$–$v$ 路徑仍然是唯一可行路徑。

---

解題方法

從頂點 $s$ 執行 DFS，對每個被首次拜訪的頂點 $v$ 設定其父節點：

$$\operatorname{parent}[v]=u$$

其中 $u$ 是 DFS 從 $s$ 到達 $v$ 時的前一個頂點。

由於 $G$ 是樹，$s$ 到 $v$ 只有唯一一條路徑：

$$s \leadsto v$$

DFS 所建立的 parent chain 也必然是這條唯一路徑。因此，從 $v$ 反覆追蹤 parent pointers 回到 $s$，即可得到 $s$ 到 $v$ 的最短路徑。

若要同時計算距離，可在 DFS 遍歷邊 $(u,v)$ 時設定：

$$d[v]=d[u]+w(u,v)$$

初始條件為：

$$d[s]=0$$

由於每個頂點到 $s$ 的路徑唯一，這個距離就是最短距離：

$$d[v]=\delta(s,v)$$

觀念解析與推導

Dijkstra 演算法適用於非負權重圖（graphs with non-negative edge weights）。在標準 Dijkstra 演算法執行過程中：

核心觀念
此題在測驗你對 Bellman‑Ford 演算法 與 負權回路 (negative‑weight cycle) 之關係的理解。關鍵在於判斷：只要圖中存在負權回路，演算法就一定會在某個頂點的最短路徑估計 $d(s,v)$ 上出錯，還是只有在負權回路 可從源點 $s$ 到達 時才會產生錯誤。

---

解題步驟與說明

1. 回顧 Bellman‑Ford 的基本性質

   • 演算法在 $|V|-1$ 次鬆弛 (relax) 後，若沒有負權回路，所有 $d(s,v)$ 都等於從 $s$ 到 $v$ 的最短路徑長度。
   • 第 $|V|$ 次鬆弛若仍能改變某條邊的距離，則圖中必存在 負權回路，且該回路必 可從 $s$ 到達（因為只有可達的回路才會影響 $d(s,\cdot)$）。

2. 負權回路不一定可達的情況

   • 若負權回路位於圖的某個「孤立」子圖，且 沒有任何路徑從 $s$ 指向該子圖，則在鬆弛過程中這些頂點的距離永遠不會被更新（仍是 $\infty$），因此不會影響任何 $d(s,v)$ 的正確性。
   • 演算法仍會在第 $|V|$ 次鬆弛時偵測到負權回路，然而它只會報告「存在負權回路」而不會改變已正確計算出的 $d(s,v)$。

3. 構造反例證明敘述錯誤

   考慮有向圖 $G=(V,E,w)$，其中

   • $V=\{s,a,b,c\}$

核心觀念

本題考查：

• Bellman-Ford 演算法原本求的是單源最短路徑。
• 最長路徑問題可透過「邊權重取負」轉換為最短路徑問題。
• 負環會使最短路徑不存在；相對地，原圖中的正環會使最長路徑不存在。
• 題目保證圖中沒有零權重環與正權重環，因此所有環的總權重皆為負。

若一條路徑包含負權重環，移除該環後，路徑總權重反而會增加。因此最大權重路徑必定不需要包含任何環，可視為一條簡單路徑。

解題方法

將原圖 $G=(V,E,w)$ 中每條邊的權重改為：

$$w'(u,v)=-w(u,v)$$

對任意一條從 $s$ 到 $t$ 的路徑 $P$，其新權重為：

$$w'(P)=\sum_{(u,v)\in P}w'(u,v) =\sum_{(u,v)\in P}[-w(u,v)] =-w(P)$$

因此：

$$\max w(P)=-\min w'(P)$$

也就是說，原圖中的最大權重路徑，等價於負權重轉換後圖中的最短路徑。

接著檢查環的性質。原圖任一環 $C$ 滿足：

$$w(C)<0$$

取負後得到：

$$w'(C)=-w(C)>0$$

所以轉換後的圖不存在負權重環。Bellman-Ford 正好能在含負邊、但不含負環的圖中，求出單源最短路徑。

求得轉換後的最短距離 $d'(t)$ 後，原圖中的最大路徑權重為：

$$d_{\max}(s,t)=-d'(t)$$

前提是 $t$ 從 $s$ 可達；若不可達，則不存在從 $s$ 到 $t$ 的路徑。

選項分析

題目只有一個是非敘述：

核心觀念
本題在測驗「負權環 (negative‑weight cycle)」對 Bellman‑Ford 演算法的影響。

• 若圖中存在可由起點 $s$ 到達的負權環，則從 $s$ 到任意可被該環觸及的終點 $t$ 的最短路徑權重會趨向 $-\infty$（可無限次迴圈降低路徑長度）。
• Bellman‑Ford 在第 $|V|-1$ 轮鬆弛後，只能保證找出 沒有負權環 的圖的最短路徑；若存在負權環，演算法只能偵測到它，而無法給出有限的最短路徑。

---

解題過程

1. 回顧 Bellman‑Ford 的保證

   • 在沒有負權迴路的情況下，經過 $|V|-1$ 次鬆弛，所有最短路徑（必為簡單路徑，亦即不含重複頂點的無環路徑）會被正確求得。
   • 再做第 $|V|$ 次鬆弛，如果仍有距離可被縮短，表示圖中存在 負權迴路，且該迴路可從 $s$ 到達。

2. 負權迴路的影響

   • 設有負權迴路 $C$，其總權重 $w(C) < 0$。如果 $C$ 可從 $s$ 走到且再走到 $t$，則可以在 $s \rightarrow \dots \rightarrow t$ 的路徑中任意次數重複 $C$，使路徑權重趨向 $-\infty$。
   • 因此，不存在 有限且唯一的「最短」路徑；最短路徑的概念在此情況下退化為「無下界」。

3. Bellman‑Ford 是否會回傳「最短無環路徑」？

   • 演算法在第 $|V|-1$ 輪鬆弛後，所得到的距離值僅是 某一條不含環的路徑 的權重上界。若存在負權迴路，該上界不一定是最小的，甚至可能比真實的「最短」(即 $-\infty$) 大。
   • 在第 $|V|$ 輪檢測到負權迴路後，標準的 Bellman‑Ford 會報告 “負權迴路存在”，而不會返回任何最短路徑。

核心觀念

本題考查「所有邊權重同乘正數後，最短路徑是否保持不變」。

一條路徑 $q$ 的總權重定義為其所經過所有邊權重的總和：

$$w(q)=\sum_{e\in q}w(e)$$

題目將每條邊的權重加倍，因此對所有邊 $e\in E$：

$$w'(e)=2w(e)$$

因此任一路徑 $q$ 在新圖 $G'$ 中的權重為：

$$w'(q)=\sum_{e\in q}w'(e) =\sum_{e\in q}2w(e) =2\sum_{e\in q}w(e) =2w(q)$$

也就是說，所有路徑的總權重都同時乘上 $2$。

---

解題方法

已知 $p$ 是原圖 $G$ 中從 $s$ 到 $t$ 的最短路徑，因此對任意其他從 $s$ 到 $t$ 的路徑 $q$，皆有：

$$w(p)\leq w(q)$$

因為 $2>0$，將不等式兩邊同乘 $2$，不等號方向不變：

$$2w(p)\leq 2w(q)$$

又由前述關係：

$$w'(p)=2w(p),\qquad w'(q)=2w(q)$$

所以：

$$w'(p)\leq w'(q)$$

核心觀念

二元堆（binary heap）是一棵具備完全二元樹形狀的樹，並滿足堆序性：

• Max-heap：父節點值不小於子節點。
• Min-heap：父節點值不大於子節點。

插入元素時，通常分成兩個步驟：

1. 將新元素放在陣列末端，以維持完全二元樹的形狀。
2. 若違反堆序性，便與父節點交換，持續向上調整，稱為 sift-up 或 bubble-up。

二元堆的高度為：

$$h=\lfloor \log_2 n \rfloor=\Theta(\log n)$$

解題方法

新元素最壞情況下可能具有極大值（max-heap）或極小值（min-heap），因此必須一路從葉節點交換到根節點。

每次向上移動一層只需 $O(1)$ 時間，而最多移動堆的高度：

$$T(n)=O(h)=O(\log n)$$

此外，確實存在某些插入情況需要移動 $\Theta(\log n)$ 層，因此最壞情況的緊確複雜度為：

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

題目要求選擇最緊確的上界，因此選擇 $O(\log n)$。

選項分析

• (A) $O(1)$：錯誤。
  插入後可能需要將元素一路向上調整至根節點，最多交換 $\Theta(\log n)$ 次，不是固定時間。

核心觀念

二元堆（binary heap）是一棵完全二元樹，並滿足堆序性。若題目執行 find-min，通常指的是最小堆（min-heap）：

• 每個父節點的鍵值都小於或等於其子節點。
• 因此，全體元素中的最小值必定位於根節點。
• 根節點的位置固定，通常以陣列索引 $1$ 儲存。

所以，find-min 只需要直接讀取根節點，不必搜尋其他節點。

解題方法

在最小堆中：

$$\operatorname{min}(H)=H[1]$$

取得陣列第一個元素只需一次索引存取，因此執行時間為

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

最壞情況與最好情況都相同，因為無論堆的內容如何排列，最小值都固定在根節點。

因此答案為：

$$\boxed{O(1)}$$

選項分析

• (A) $O(1)$：正確。
  最小堆的最小值位於根節點，直接讀取根節點即可完成 find-min。

• (B) $O(\log^* n)$：錯誤。
  $\log^* n$ 是反覆取對數的次數，常見於某些特殊演算法；

核心觀念

Binary heap 是一棵具有完整二元樹結構的 heap。大小為 $n$ 時，其高度為

$$h=\lfloor \log_2 n \rfloor=O(\log n)$$

以 min-heap 為例，decrease-key 將某個節點的鍵值減小後，可能違反「父節點鍵值不大於子節點」的 heap-order property，因此必須將該節點向上移動，直到恢復 heap 性質。

解題方法

decrease-key 的處理流程如下：

1. 將指定節點的鍵值減小。
2. 比較該節點與父節點的鍵值。
3. 若該節點小於父節點，便交換兩者。
4. 持續向上比較，直到到達根節點或不再違反 heap 性質。

每次比較或交換所需時間為 $O(1)$。最壞情況下，該節點位於葉節點，且新鍵值小到必須一路上移至根節點，最多經過 heap 高度 $h$ 層：

$$T(n)=O(h)=O(\log n)$$

因此，decrease-key 的 worst-case time complexity 為 $O(\log n)$。

選項分析

• (A) $O(1)$：錯誤。
  若鍵值減小後仍大於等於父節點，確實只需常數時間即可完成；但這是 best case，不是 worst case。最壞情況可能一路上移至根節點。

核心觀念

二項堆（Binomial Heap）由數個二項樹組成，具有以下性質：

• 一個大小為 $2^k$ 的二項樹，其高度為 $k$。
• 大小為 $n$ 的二項堆最多包含 $O(\log n)$ 棵二項樹。
• 標準實作中，insert 通常透過「建立一棵單一節點的二項樹，再與原二項堆合併」完成。
• 合併過程需掃描及整理最多 $O(\log n)$ 棵二項樹，因此單次插入的最壞時間複雜度為

$$T_{\text{insert}}(n)=O(\log n)$$

解題方法

題目要求連續執行 $O(\log n)$ 次 insert。

設插入次數為

$$k=O(\log n)$$

每次插入的最壞成本為 $O(\log n)$，因此總最壞時間為

$$T(k)=k\cdot O(\log n)$$

代入 $k=O(\log n)$：

$$T(k)=O(\log n)\cdot O(\log n) =O(\log^2 n)$$

所以正確答案為：

$$\boxed{O(\log^2 n)}$$

這裡問的是「最壞情況」，不能直接採用偶爾插入只需常數時間的情況。某次插入可能產生連續的合併（linking），而標準二項堆的插入上界仍為 $O(\log n)$。

選項分析

核心觀念

Binomial heap（雙項堆）由若干棵 binomial tree 組成，並且每棵樹都符合最小堆性質。

對於含有 $n$ 個元素的 binomial heap：

• 最大樹階為 $O(\log n)$。
• 根串列中的樹數量最多為 $O(\log n)$。
• 一棵階數為 $k$ 的 binomial tree，其根節點刪除後會留下 $k$ 棵子樹，階數分別為 $0,1,\ldots,k-1$。

因此，delete-min 的主要工作量與最大樹階及根串列長度有關，皆為 $O(\log n)$。

---

解題方法

delete-min 的處理步驟如下：

1. 在根串列中找出最小根節點。
2. 移除該最小根節點。
3. 將其子樹加入 heap 的根串列。
4. 重新合併相同階數的 binomial tree，使每個階數最多只保留一棵樹。

若最小根節點所屬的 binomial tree 階數為 $k$，則：

$$2^k \leq n$$

所以：

$$k \leq \lfloor \log_2 n \rfloor = O(\log n)$$

刪除根節點後，最多產生 $k$ 棵子樹；同時，原本根串列中最多也只有 $O(\log n)$ 棵樹。重新整理與合併的成本因此為：

$$T_{\text{delete-min}}(n)=O(\log n)$$

此上界可以達到，例如最小元素位於高階 binomial tree 的根節點，刪除後需要處理 $\Theta(\log n)$ 棵子樹，因此最壞情況為：

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

選項以 Big-O 表示時，應選 $O(\log n)$。

---

核心觀念

二項堆由多棵二項樹組成，同一個堆中每種階數至多有一棵。階數為 $k$ 的二項樹有 $2^k$ 個節點，因此總節點數為 $n$ 時，最大階數不超過 $\lfloor\log_2 n\rfloor$，根串列中樹的數量也至多為 $O(\log n)$。

兩個二項堆的 union（合併）會先合併根串列，再將階數相同的二項樹連結，維持每種階數至多一棵。

解題方法

設兩堆總節點數為 $n$。兩堆根串列各自依階數遞增排列，串列長度皆為 $O(\log n)$。合併這兩個已排序串列需 $O(\log n)$ 時間。

接著掃描合併後的根串列，遇到階數相同的二項樹便將其中一棵掛到另一棵之下。一次連結只需 $O(1)$ 時間；掃描與連結所處理的樹數量受根串列長度限制，總成本仍為 $O(\log n)$。

因此，一次 union 的最壞時間複雜度為 $O(\log n)$，答案是 (C)。

選項分析

核心觀念

二項堆由多棵二項樹組成。二項樹 $B_k$ 有 $2^k$ 個節點，且高度為 $k$；因此，大小為 $n$ 的二項堆中，任一節點到根的路徑長度至多為 $\lfloor \log_2 n \rfloor$。

在最小二項堆中，decrease-key 將指定節點的鍵值減小。若新鍵值小於父節點的鍵值，就沿父子鏈向上交換，直到恢復堆序性，或到達根節點。

解題方法

假設 decrease-key 已取得指定節點的指標，先更新鍵值，再逐層向上檢查父節點。每次交換及比較都耗時 $O(1)$，最多向上移動一個樹高，也就是 $O(\log n)$ 層。因此：

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

在最壞情況下，節點原本位於深度 $\Theta(\log n)$，減小鍵值後一路上升至根，故最壞情況時間複雜度為 $\Theta(\log n)$。

選項分析

核心觀念

斐波那契堆（Fibonacci heap）會維護一個指向目前最小鍵值節點的指標，通常記為 min。因此，find-min 只需讀取並回傳這個指標所指向的節點，不必走訪堆中的其他節點。

解題方法

堆的最小值指標會在操作過程中適時更新：插入節點時比較新節點與目前最小節點；執行合併時比較兩個堆的最小節點；刪除最小節點後，則在後續整理根串列時找出新的最小節點。

更新指標的工作已由其他操作負責。單獨執行一次 find-min 時，只需存取並回傳指標，所需時間為常數，因此其最壞時間複雜度是 $O(1)$。

選項分析

• (A) $O(1)$：正確。 直接透過最小值指標取得最小節點，操作時間與堆的大小無關。
• **(B) $O(\log^* n)$：錯誤。

核心觀念

Fibonacci heap 的 delete-min 會刪除最小根節點，將該節點的子節點提升為根，再合併具有相同度數的根節點。合併後，根節點的度數最多為 $O(\log n)$；但刪除前的根節點數量不一定是 $O(\log n)$，可能達到 $O(n)$。

因此，必須區分：

• 單次操作的最壞情況時間：$O(n)$。
• 攤銷時間：$O(\log n)$。

解題方法

delete-min 的主要工作包括掃描根串列，並依根節點的度數合併根節點。若刪除前根串列有 $t$ 個節點，掃描及合併所需時間可寫成 $O(t + D(n))$，其中 $D(n)$ 是最大度數，且 $D(n)=O(\log n)$。

Fibonacci heap 可以藉由連續插入節點，形成含有 $\Theta(n)$ 個根節點的根串列。此時執行一次 delete-min，就需要處理這些根節點，耗時可達 $\Theta(n)$。所以單次操作的最壞情況為 $O(n)$，對應 (D)。

選項分析

核心觀念

這題考 Fibonacci heap 的 合併（union，也稱 meld） 操作時間複雜度。標準 Fibonacci heap 以循環雙向鏈結串列維護根串列，並以一個指標記錄目前的最小根。

解題方法

合併兩個 Fibonacci heaps 時，將兩個根串列接在一起即可。循環雙向鏈結串列的串接只需調整固定數量的指標，因此耗時為常數。

接著比較兩個堆的最小根，將較小者設為合併後的最小根，只需一次鍵值比較與常數次指標更新。若兩堆大小分別為 $n_1$ 與 $n_2$，合併後大小為 $n=n_1+n_2$；整個過程不需要逐一走訪節點。

因此，最壞情況時間複雜度為 $O(1)$。

選項分析

核心觀念

左偏堆（leftist heap）同時維持兩項性質：

• 堆序性質：父節點的鍵值不大於子節點，因此最小值位於根節點。
• 左偏性質：每個節點的左子樹空路徑長度（null path length，簡稱 NPL）不小於右子樹的 NPL。

左偏性質使得從根沿右子節點往下的路徑長度為 $O(\log n)$。左偏堆的合併操作會沿著這類右側路徑進行，因此合併兩個堆的時間為 $O(\log n)$。

解題方法

執行 delete-min 時，先移除根節點；根節點的兩棵子堆各自仍是左偏堆，接著將它們合併：

$$\operatorname{delete\text{-}min}(H) = \operatorname{merge}(H_{\text{left}},H_{\text{right}})$$

刪除根節點本身只需 $O(1)$，主要成本來自合併兩棵子堆。合併沿右側路徑遞迴處理，路徑長度為 $O(\log n)$，所以一次 delete-min 的最壞時間複雜度為：

$$O(\log n)$$

選項分析

核心觀念

左偏堆（leftist heap）同時維持兩項性質：

• 堆序性質：父節點的鍵值不大於子節點，或不小於子節點，依題目採用的最小堆或最大堆定義而定。
• 左偏性質：每個節點左子樹的零路徑長度（null path length, NPL）不小於右子樹的零路徑長度。

合併兩個左偏堆時，沿著右子樹遞迴合併；遞迴返回後，若左子樹的 NPL 小於右子樹，就交換左右子樹。因此，合併所需的主要時間取決於右側路徑的長度。

解題方法

令 $s(x)$ 表示節點 $x$ 的 NPL，並令空節點的 NPL 為 $0$。左偏性質保證：

$$s(x)=1+s(\text{right}(x))$$

也就是說，從根沿右子節點往下走，每經過一層，NPL 至少減少 $1$。因此右側路徑長度為 $O(s(\text{root}))$。

另一方面，NPL 為 $r$ 的左偏堆至少有 $2^r-1$ 個節點：根的左右子樹 NPL 都至少為 $r-1$，故有遞迴下界 $M(r)\ge 1+2M(r-1)$，且 $M(0)=0$。解得 $M(r)\ge 2^r-1$。若整個堆有 $m$ 個節點，則：

$$r\le \log_2(m+1)=O(\log m)$$

核心觀念

二元樹的高度若以「邊數」計算，根節點高度為 $0$。高度為 $h$ 的二元樹最多有

$$1+2+4+\cdots+2^h=2^{h+1}-1$$

個節點。因此，節點數越多，樹高就不能低於這個容量限制所要求的高度。

AVL 樹是高度平衡的二元搜尋樹；完全二元樹也符合 AVL 的平衡條件，因為每個節點的左右子樹高度差至多為 $1$。

解題方法

先檢查高度 $5$ 的二元樹最多能容納多少個節點：

$$2^{5+1}-1=63$$

$100>63$，所以 100 個節點的二元樹高度至少為 $6$。

這個下界可以達到：100 個節點依序填入完全二元樹的各層，樹高為 $6$（邊數），且仍是 AVL 樹。因此最低可能高度正是 $6$。

選項分析

核心觀念

2-3-4 樹的每個內部節點最多有 $4$ 個子節點。樹高 $h$ 定義為根節點到最深葉節點的邊數，因此高度為 $h$ 的樹最多有

$$1+4+4^2+\cdots+4^h=\frac{4^{h+1}-1}{3}$$

個節點。要找出含 $255$ 個節點的樹「至少」多高，就比較高度較低時所能容納的最大節點數。

解題方法

若高度為 $3$，最多能有

$$1+4+16+64=85$$

個節點，少於題目給的 $255$ 個。因此高度不可能是 $3$ 或更低，至少需要 $4$。

再看高度 $4$ 的容量：

$$1+4+16+64+256=341$$

所以 $255$ 個節點可以落在高度 $4$ 的容量範圍內；高度 $4$ 也確實可達，例如各層節點數為 $1,4,16,64,170$，總數正好為 $255$，且最後一層的每個節點都

核心觀念

二項堆由多棵不同階數的二項樹組成。階數為 $k$ 的二項樹記為 $B_k$，其中恰有 $2^k$ 個節點。

二項堆中每種階數至多有一棵二項樹，因此若堆中有 $n$ 個項目，便將 $n$ 寫成二進位；二進位表示中每個值為 $1$ 的位元，對應一棵二項樹。故二項樹的棵數等於 $n$ 的二進位表示中 $1$ 的個數。

解題方法

將 $2020$ 分解為不同的 $2$ 的次方：

$$2020 = 1024 + 512 + 256 + 128 + 64 + 32 + 4$$

也就是：

$$2020 = 2^{10} + 2^9 + 2^8 + 2^7 + 2^6 + 2^5 + 2^2$$

因此，二項堆包含 $B_{10}, B_9, B_8, B_7, B_6, B_5, B_2$，共 $7$ 棵二項樹。

選項分析

核心觀念

二項樹 $B_k$ 的階數為 $k$，由兩棵階數為 $k-1$ 的二項樹合併而成；$B_0$ 是一個節點。因此，若 $n_k$ 表示 $B_k$ 的節點數，則

$$n_0=1,\qquad n_k=2n_{k-1}.$$

由此可得，階數為 $k$ 的二項樹有 $2^k$ 個節點。

解題方法

題目給定階數 $4$，代入節點數公式：

$$n_4=2^4=16.$$

因此，階數為 $4$ 的二項樹共有 $16$ 個項目。

選項分析

核心觀念

本題考漸近成長率的比較，以及 $O$ 記號的定義與傳遞性。對非負函數 $f(n)$、$g(n)$，若存在常數 $c>0$ 與 $n_0$，使得所有 $n\ge n_0$ 都滿足

$$f(n)\le c\,g(n),$$

就稱 $f(n)=O(g(n))$。直觀上，這表示 $f$ 的成長速度至多與 $g$ 同階。

比較兩個函數時，也可觀察比值：若 $f(n)/g(n)$ 隨 $n$ 增大而無界，則 $f(n)\ne O(g(n))$；若比值有固定上界，則 $f(n)=O(g(n))$。

解題方法

逐一檢查各選項：漸近比較題以比值檢驗成長率；涉及 $O$ 記號的敘述則直接套用定義，或用反例檢查是否成立。

選項分析

(A) $\frac{n^2}{\log n}=O(n^{1.5})$：錯誤。

比較兩邊的比值：

$$\frac{n^2/\log n}{n^{1.5}} =\frac{\sqrt n}{\log n}.$$

當 $n\to\infty$ 時，$\sqrt n$ 的成長速度快於 $\log n$，因此此比值趨近無限大，沒有固定常數能讓 $\frac{n^2}{\log n}\le c n^{1.5}$ 對所有充分大的 $n$ 成立。故此選項錯誤。

(B) $2^{2n}=\Theta(2^n)$：錯誤。

因為 $2^{2n}=4^n$，比較兩者比值：

$$\frac{2^{2n}}{2^n}=2^n.$$

此比值隨 $n$ 增大而無界，因此 $2^{2n}$ 不受任何常數倍的 $2^n$ 上界限制，兩者不是 $\Theta$ 關係。

核心觀念

這題考遞迴式的變數轉換與遞迴樹分析。遇到子問題規模由 $n$ 變成 $\sqrt n$，可令 $m=\log_2 n$，因為

$$\log_2 \sqrt n=\frac{1}{2}\log_2 n.$$

如此便能把平方根縮小轉成規模減半，再套用遞迴樹分析。

解題方法

令 $S(m)=T(2^m)$，則 $n=2^m$、$\sqrt n=2^{m/2}$，遞迴式改寫為

$$S(m)=2S\left(\frac{m}{2}\right)+m.$$

其中每個子問題的規模是原來的一半，且每個節點的額外成本為該節點規模。

以遞迴樹計算：第 $j$ 層有 $2^j$ 個節點，每個節點的規模為 $m/2^j$，因此該層總成本為

$$2^j\cdot\frac{m}{2^j}=m.$$

遞迴深度約為 $\log_2 m$。葉節點對應 $T(2)=0$，不產生額外成本，所以

$$S(m)=m\log_2 m.$$

代回 $m=\log_2 n$，得到

核心觀念

比較式排序會透過比較元素大小來決定輸出順序。分析這類演算法的下界時，可將演算法表示為一棵決策樹：每個內部節點代表一次比較，每條根到葉的路徑代表一種比較結果序列，每個葉節點代表演算法判定的一種排序結果。

要排序 $n$ 個互異元素，輸入共有 $n!$ 種排列。演算法必須能區分這 $n!$ 種排列，因此決策樹至少要有 $n!$ 個葉節點。若樹高為 $h$，二元決策樹最多有 $2^h$ 個葉節點，所以：

$$2^h \ge n!$$

取以 $2$ 為底的對數，得到：

$$h \ge \log_2(n!)$$

由 Stirling 近似公式可知：

$$\log_2(n!) = \Theta(n\log n)$$

因此，任何比較式排序演算法在最壞情況下都需要 $\Omega(n\log n)$ 次比較。

解題方法

本題問的是所有比較式排序演算法都必須滿足的緊密下界，使用決策樹下界即可。上述推導給出 $\Omega(n\log n)$ 的必要比較次數；此外，合併排序等演算法能在最壞情況下以 $O(n\log n)$ 次比較完成排序。因此，這個下界可由演算法達成，漸近上是緊密的。

選項分析

核心觀念

本題比較三種排序法在「輸入已完全排序」時的時間複雜度。關鍵在於各演算法如何選擇樞紐、比較元素，以及是否仍執行完整的排序流程。

以下依一般教科書的基本實作判斷：快速排序固定選取子陣列的第一個或最後一個元素作為樞紐；合併排序照常遞迴分割並合併，沒有額外的「已排序」檢查。

解題方法

快速排序：$O(n^2)$

輸入已排序，若固定選取第一個或最後一個元素為樞紐，每次分割都會得到大小為 $0$ 與 $n-1$ 的兩個部分。每層分割需花費 $\Theta(n)$，因此遞迴式為：

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

展開後：

$$T(n)=\Theta(n)+\Theta(n-1)+\cdots+\Theta(1)=\Theta(n^2)$$

插入排序：$O(n)$

每次處理下一個元素時，它已經位於正確位置。總共進行約 $n-1$ 次比較，且不需搬移已排序部分的元素，因此：

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

合併排序：$O(n\log n)$

合併排序仍將資料分成兩半，遞迴排序後再合併。即使輸入原本已排序，基本合併程序仍會逐層處理所有元素。其遞迴式為：

核心觀念

本題比較的是「查詢前先排序」與「直接搜尋」的總成本。時間複雜度須計入整個策略的每一步，不能只看最後的二分搜尋。

解題方法

假設只需查詢一次，且原始串列尚未排序。

• 線性搜尋：依序檢查元素。若目標在串列中且位置平均分布，平均約需檢查 $n/2$ 個元素；即使目標不在串列中，最多檢查 $n$ 個元素。因此平均時間複雜度為 $O(n)$。
• 合併排序後再二分搜尋：合併排序需 $O(n\log n)$；排序完成後，二分搜尋需 $O(\log n)$。總時間為 $$O(n\log n)+O(\log n)=O(n\log n).$$

因此，單次查詢時，直接線性搜尋較快，答案為 (A)。

選項分析

核心觀念

本題考「活動選擇問題」：每個活動有開始時間 $s_i$ 與結束時間 $t_i$，要選出最多個彼此不重疊的活動。若前一個活動在 $t_i$ 結束，下一個活動須滿足 $s_j \ge t_i$。

活動依結束時間由早到晚排序，並每次選擇最早結束且與已選活動相容的活動，可得到最多活動數。這是活動選擇問題的貪婪法。

解題方法

圖中表格列出 9 個活動：活動 1 至 9 的開始時間依序為 $2,3,1,10,14,6,13,7,19$，結束時間依序為 $5,9,12,16,17,15,18,11,20$。

依結束時間排序如下：

$$1(2,5),\ 2(3,9),\ 8(7,11),\ 3(1,12),\ 6(6,15),\ 4(10,16),\ 5(14,17),\ 7(13,18),\ 9(19,20)$$

括號內依序是開始時間與結束時間。從最早結束的活動開始挑選：

1. 選活動 1，時間為 $[2,5]$。
2. 活動 2 的開始時間 $3<5$，與活動 1 重疊，跳過；活動 8 的開始時間 $7\ge5$，選活動 8，時間為 $[7,11]$。