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

核心觀念

本題考查：

• 比較式排序的下界；
• 非比較式排序，例如 Counting Sort；
• 小寫入值域下，線性時間排序的可能性；
• 小記號 $o(\cdot)$ 的定義。

若只使用元素間比較，排序一般需要

時間。但題目中的出生日期範圍固定在西元 0 年至 2003 年，可能的日期數量是有限常數，因此不必受比較式排序下界限制。

解題方法

將每個人的出生日期轉換成一個可排序的整數鍵值。例如，可將日期依時間順序編號：

西元 0 年至 2003 年之間的所有可能出生日期數量至多為

其中 $K$ 是固定常數，與 $n$ 無關。

接著使用 Counting Sort：

1. 建立長度為 $K$ 的計數陣列；
2. 掃描 $n$ 個人的出生日期，統計各日期出現人數；
3. 依日期順序輸出所有人。

時間複雜度為

由於 $K$ 是常數，因此

接著驗證是否符合 $o(n\lg n)$：

因此

核心觀念

題目給出的陣列為：

陣列表示 binary heap 時，通常採用 0-based indexing：

• 節點 $i$ 的左子節點：$2i+1$
• 節點 $i$ 的右子節點：$2i+2$
• 節點 $i$ 的父節點：$\left\lfloor \dfrac{i-1}{2}\right\rfloor$

Min-heap 必須同時滿足：

1. 結構上是 complete binary tree。
2. 每個父節點的值小於或等於其子節點：

Min-heap 只保證父子之間的大小關係，不要求同一層由左至右排序。

解題方法

將陣列畫成 complete binary tree：

             2
          /     \
         5       9
       /  \     / \
      8   10   13  12
     / \
    22 50

逐一檢查每個具有子節點的父節點。

根節點 $2$

觀念解析

依據漸進記號（Asymptotic Notation）定義：

• $f(n) \in \Omega(g(n)) \iff \exists c_1 > 0, n_1 > 0, \forall n \ge n_1: f(n) \ge c_1 \cdot g(n)$
• $g(n) \in O(f(n)) \iff \exists c_2 > 0, n_2 > 0, \forall n \ge n_2: g(n) \le c_2 \cdot f(n)$

上述兩條件邏輯上完全等價，均僅說明 $g(n)$ 為 $f(n)$ 的漸進下界（Lower Bound）。

核心觀念

動態規劃（Dynamic Programming, DP）利用：

1. 重疊子問題：相同子問題會被重複使用。
2. 最佳子結構：原問題的最佳解可由子問題的最佳解組成。

若共有 $m$ 個不同子問題：

• **Memoization（自頂向下）**通常會為每個子問題保存答案，因此空間複雜度常為 $O(m)$。
• **Tabulation（自底向上）**則可依照狀態轉移式，只保留未來仍會用到的部分狀態，空間不一定需要保存全部 $m$ 個子問題。

因此，「不同子問題的數量」是某些 DP 實作的記憶體需求上界或常見需求，但不是所有 DP 解法的必要空間下界。

解題方法

判斷「always」這類敘述時，只要找出一個反例即可證明錯誤。

以 Fibonacci 數列為例：

從 $F(0)$ 到 $F(n)$ 共有 $O(n)$ 個不同子問題。若使用完整的 DP 陣列，確實需要：

此時空間複雜度為 $O(n)$。

但計算 $F(i)$ 時只需要前兩項，因此可使用滾動變數：

prev2 = F(0)
prev1 = F(1)

for i = 2 to n:
    current = prev1 + prev2
    prev2 = prev1
    prev1 = current

核心觀念

Dijkstra 演算法解決單一起點最短路徑問題時，必要條件是所有邊權重皆滿足

原因是：Dijkstra 每次選出目前暫定距離最小且尚未確定的頂點，並將其距離視為最終答案。這個判定依賴「後續經過其他邊不會使距離下降」；若存在負權重邊，此性質便不成立。

題目只說邊權重為實數，實數包含負數，因此不保證所有邊權重非負。

解題方法

可用反例證明題目敘述不成立。

考慮一個有向無環圖：

• $s\to a$，權重為 $2$
• $s\to b$，權重為 $5$
• $b\to a$，權重為 $-10$

此圖沒有有向環，符合 DAG 條件。

從起點 $s$ 執行 Dijkstra：

1. 初始距離為

   $$d(s)=0,\qquad d(a)=2,\qquad d(b)=5$$

2. Dijkstra 先選出暫定距離較小的 $a$，將 $d(a)=2$ 確定。

3. 接著處理 $b$，經由 $b\to a$ 可得到

核心觀念

本題考查無權重圖中的最短路徑，以及廣度優先搜尋（Breadth-First Search, BFS）的性質。

在無向圖 $G=(V,E)$ 中，若每條邊的成本皆為 $1$，則兩頂點間的最短路徑長度，就是從起點出發所需經過的最少邊數。BFS 具有以下定理：

從起點 $u$ 執行 BFS 時，頂點第一次被拜訪的層數，等於 $u$ 到該頂點的最短距離。

令 $\operatorname{dist}(u,x)$ 表示 $u$ 到 $x$ 的最短距離，則 BFS 完成後：

• 若 $v$ 被拜訪，則 $\operatorname{dist}(u,v)$ 即為 $u$ 到 $v$ 的最短路徑長度。
• 若 $v$ 未被拜訪，則 $u$ 與 $v$ 不在同一個連通分量中，因此不存在從 $u$ 到 $v$ 的路徑。

解題方法

從頂點 $u$ 開始，將 $u$ 放入佇列，並設定：

BFS 每次從佇列取出一個頂點 $x$，檢查其所有鄰接頂點 $y$。若 $y$ 尚未拜訪，便設定：

再將 $y$ 放入佇列。

BFS 的搜尋順序具有分層特性：

• 第 $0$ 層：$u$
• 第 $1$ 層：與 $u$ 相鄰的頂點
• 第 $2$ 層：距離 $u$ 為 $2$ 的頂點
• 第 $k$ 層：距離 $u$ 為 $k$ 的頂點

由於 BFS 會先處理較小層數的頂點，任何頂點 $v$ 第一次被拜訪時，所得到的距離必定是最短距離。若在搜尋過程中記錄每個頂點的前驅頂點 parent，即可由 $v$ 沿著前驅回溯至 $u$，重建完整最短路徑。

關鍵流程如下：

BFS(G, u):
    for each vertex x:
        visited[x] = false
        parent[x] = NIL
        dist[x] = ∞

    visited[u] = true
    dist[u] = 0
    enqueue(u)

    while queue is not empty:
        x = dequeue()

        for each neighbor y of x:
            if visited[y] == false:
                visited[y] = true
                parent[y] = x
                dist[y] = dist[x] + 1
                enqueue(y)

完成後：

核心觀念

本題考查最大流問題的「整數流定理」：

若流網路中每條邊的容量皆為整數，則至少存在一個最大流，使得每條邊上的流量皆為整數。

流函數 $f$ 必須滿足：

1. 容量限制
   $0 \le f(u,v) \le c(u,v)$

2. 流量守恆
   對除來源點 $s$ 與匯點 $t$ 外的每個頂點 $v$：
   $\sum_{u} f(u,v)=\sum_{w} f(v,w)$

3. 反對稱性
   $f(u,v)=-f(v,u)$

其中 $c(u,v)$ 為邊 $(u,v)$ 的容量。

解題方法

採用 Ford–Fulkerson 演算法證明。

初始流量設為零流：

$f(u,v)=0$

因此所有流量都是整數。

在每次迭代中，Ford–Fulkerson 演算法會在殘餘網路中尋找一條由 $s$ 到 $t$ 的增廣路徑 $P$，並令增廣量為該路徑上的最小殘餘容量：

$\Delta=\min_{(u,v)\in P} c_f(u,v)$

因為原始容量皆為整數，且初始流量為整數，所以每條殘餘容量

$c_f(u,v)=c(u,v)-f(u,v)$

或反向邊的殘餘容量

$c_f(v,u)=f(u,v)$

也都是整數。因此 $\Delta$ 必為整數。

增廣後：

• 路徑上的正向邊流量增加 $\Delta$；
• 路徑上的反向邊流量減少 $\Delta$；
• 其他邊流量不變。

觀念分析

在僅支援 INCREMENT 的 $k$-bit 二進位計數器中，高位元翻轉頻率呈指數遞減，$n$ 次操作的總成本上限為 $O(n)$，單次攤還成本（Amortized Cost）為 $O(1)$。

然而，若計數器同時支援 INCREMENT 與 DECREMENT，最壞情況下可構造出連續觸發多個位元翻轉的操作序列，使攤還分析的優勢消失。

推導與證明

1. 總成本上限（Upper Bound）：
   $k$-bit 二進位計數器共有 $k$ 個位元，單次 INCREMENT 或 DECREMENT 最多翻轉 $k$ 個位元。因此，$n$ 次操作的總位元翻轉次數上界為：
   $T(n) \le n \cdot k = O(nk)$

2. 最壞情況序列（Lower Bound）：
   設定計數器初始值為 $2^{k-1} - 1$（二進位表示為 $011\dots1_2$）：

核心觀念

本題考查複雜度類別 $P$、$NP$ 與 $NPC$ 的包含關係：

• $P$：可在多項式時間內解決的問題。
• $NP$：給定候選解後，可在多項式時間內驗證其正確性的問題。
• $NPC$（NP-Complete）：同時屬於 $NP$，且是 $NP$-Hard 的問題。

重要包含關係為：

此外，線性時間 $O(n)$ 屬於多項式時間，因為：

因此，能在線性時間解決的問題，一定也能在多項式時間解決。

解題方法

題目敘述：

If any problem in NP can be solved in linear time, then all problems in NPC can be solved in polynomial time.

將「any problem in NP」理解為「$NP$ 中的任意問題皆可在線性時間解決」。

由於所有 $NPC$ 問題都是 $NP$ 問題：

所以任取一個問題 $L\in NPC$，必然有 $L\in NP$。根據題目前提，$L$ 可以在線性時間內解決：

核心觀念

本題考查複雜度類別與 NP-complete（NPC，NP 完全）問題的關係：

• $P$：可在多項式時間內解決的問題。
• $NP$：給定候選解後，可在多項式時間內驗證的問題。
• $NPC$：同時滿足下列條件的問題：
  1. 屬於 $NP$；
  2. 是 $NP$-hard，也就是所有 $NP$ 問題都能在多項式時間內歸約至它。

已知關係為：

若某一個 NP 完全問題 $L$ 能在線性時間 $O(n)$ 內解決，因為線性時間必定屬於多項式時間，所以：

這會導致 $P=NP$。

解題方法

設 $L$ 是任意一個可在線性時間內解決的 NP 完全問題。

對任意問題 $A\in NP$，由於 $L$ 是 NP-hard，存在一個多項式時間歸約：

先花多項式時間將 $A$ 的輸入轉換成 $L$ 的輸入，再用線性時間演算法解決 $L$。整體時間仍為多項式時間，因此：

所以：

配合原本的：

得到：

因此，「任一個 NP 完全問題若能在多項式時間內解決，則 $P=NP$」是正確的；題目使用的「線性時間」更是多項式時間的特殊情況。

命題分析

題目主張：

其中 $P=NP$ 的部分正確，但 $NP=NPC$ 的部分不正確。

本題考點：主定理（Master Theorem）與遞迴關係式複雜度分析

已知遞迴關係式為：
$T(n) = 25 T\left(\frac{n}{5}\right) + n^{\log_5 n}$

其中 $a = 25$，$b = 5$，$f(n) = n^{\log_5 n}$。

1. 計算臨界函數（Critical Function）：
$n^{\log_b a} = n^{\log_5 25} = n^2$

2. 比較 $f(n)$ 與 $n^{\log_b a}$ 的成長速度：
取 $\epsilon = 1 > 0$，當 $n \ge 125$（即 $\log_5 n \ge 3$）時：
$f(n) = n^{\log_5 n} \ge n^3 = \Omega(n^{2+1})$
可知 $f(n)$ 的成長速度呈多項式地快於 $n^{\log_b a} = n^2$。

觀念與推導

給定遞迴關係式：
$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n$

1. 遞迴樹法 (Recursion Tree Method) 分析

• 每層工作量：
  • 第 0 層：$n$
  • 第 1 層：$\frac{n}{3} + \frac{2n}{3} = n$
  • 第 2 層：$\left(\frac{n}{9} + \frac{2n}{9}\right) + \left(\frac{2n}{9} + \frac{4n}{9}\right) = n$

核心觀念

本題考查遞迴式的漸進分析，核心工具是遞迴樹與調和級數：

其中每層共有 $2^i$ 個子問題，每個子問題的規模為 $n/2^i$。

解題方法：遞迴樹分析

第 $i$ 層的單一子問題非遞迴成本為：

該層共有 $2^i$ 個子問題，因此第 $i$ 層總成本為：

遞迴深度約為 $\lg n$，所以所有非葉節點成本總和為：

其中

為調和級數，因此：

最底層共有 $2^{\lg n}=n$ 個葉節點，葉節點總成本為 $\Theta(n)$。由於

葉節點成本不會主導整體複雜度，故：

選項分析

核心觀念

本題主要測驗利用**主定理（Master Theorem）求解分治演算法之遞迴關係式（Recurrence Relation）的時間複雜度，以及對漸近符號（Asymptotic Notations）**數學定義之掌握。

對於遞迴關係式：
$T(n) = a T(n/b) + f(n)$
其中 $a \ge 1, b > 1$。主定理透過比較非遞迴成本 $f(n)$ 與分治樹葉節點總成本 $n^{\log_b a}$ 來決定時間複雜度：

• Case 1：若存在 $\epsilon > 0$ 使 $f(n) = O(n^{\log_b a - \epsilon})$，則 $T(n) = \Theta(n^{\log_b a})$。
• Case 2：若存在 $k \ge 0$ 使 $f(n) = \Theta(n^{\log_b a} \lg^k n)$，則 $T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$。
• Case 3：若存在 $\epsilon > 0$ 使 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且滿足正規性條件（Regularity condition），則 $T(n) = \Theta(f(n))$。

此外，依據漸近符號定義，若 $T(n) = \Theta(g(n))$，則必成立 $T(n) = O(g(n))$。

解題方法

1. 參數辨識：
   給定遞迴式為 $T(n) = 4 T(n/3) + n^{\log_3 4}$，比對標準式 $T(n) = a T(n/b) + f(n)$：

   • $a = 4$
   • $b = 3$
   • $f(n) = n^{\log_3 4}$

2. 計算分治樹葉節點複雜度：
   $n^{\log_b a} = n^{\log_3 4}$

3. 比較 $f(n)$ 與 $n^{\log_b a}$：
   $f(n) = n^{\log_3 4} = \Theta(n^{\log_3 4}) = \Theta(n^{\log_b a} \lg^0 n)$
   符合主定理 Case 2（其中 $k = 0$ 之情形）。

4. 代入公式求解：
   $T(n) = \Theta(n^{\log_b a} \lg^{0+1} n) = \Theta(n^{\log_3 4} \lg n)$

核心觀念

Quick sort 每次執行 partition 時，需要掃描目前子陣列，因此單層 partition 的總成本為 $O(n)$。

其時間複雜度取決於 pivot 將資料切分後的形狀：

• 最佳情況：每次近乎平均切分，為 $\Theta(n\lg n)$。
• 最壞情況：每次切成 $0$ 與 $n-1$，為 $\Theta(n^2)$。
• 平均情況：雖然切分不一定完全平均，但期望遞迴深度為 $O(\lg n)$，因此為 $\Theta(n\lg n)$。

平均情況可用遞迴式表示為：

整理後可得：

因此平均情況的 tightest bound 是 $O(n\lg n)$，更精確地說是 $\Theta(n\lg n)$。

解題方法

快速判斷方式是區分「平均情況」與「最壞情況」：

1. 每一層 partition 的總工作量約為 $n$。
2. 平均情況下，資料經過隨機或合理的 pivot 選擇後，遞迴樹的期望高度為 $O(\lg n)$。
3. 總時間為：

選項分析

觀念解析
堆疊（Stack）為後進先出（LIFO）之資料結構。無論採用單向鏈結串列（Singly Linked List）或是預先配置空間之陣列（Array）實作，push 與 pop 操作皆僅需於堆疊頂端（top）更新指標並執行單一元素的存取

核心觀念

本題考查雜湊表（hash table）的二次探測（quadratic probing）。

雜湊表共有 $11$ 個槽位，索引為 $0$ 至 $10$。探測函數為

其中通常以 $i=0$ 作為第一次探測；若該位置已被占用，再依序使用 $i=1,2,3,\ldots$ 探測。

每個鍵值先以 $k\pmod{11}$ 求出初始位置，再依插入順序處理碰撞。

解題方法

依序插入各鍵值，記錄已占用的槽位。

1. 插入 $82$

槽位 $5$ 為空，故 $82$ 放在 $5$。

2. 插入 $90$

槽位 $2$ 為空，故 $90$ 放在 $2$。

3. 插入 $30$

槽位 $8$ 為空，故 $30$ 放在 $8$。

4. 插入 $89$

槽位 $1$ 為空，故 $89$ 放在 $1$。

5. 插入 $61$

槽位 $6$ 為空，故 $61$ 放在 $6$。

6. 插入 $44$

槽位 $0$ 為空，故 $44$ 放在 $0$。

7. 插入 $28$

槽位 $6$ 已有 $61$，發生碰撞，因此進行二次探測：

槽位 $7$ 為空，故 $28$ 放在 $7$。

此時已占用槽位為

8. 插入 $51$

初始位置為

槽位 $7$ 已有 $28$，繼續二次探測：

槽位 $8$ 已有 $30$。

核心觀念

AVL 樹是一棵高度平衡的二元搜尋樹，對每個節點皆滿足：

在節點數固定時，若要使 AVL 樹的高度最大，就必須讓每一層的節點數盡量少。因此，考慮「高度為 $h$ 的 AVL 樹所需的最少節點數」。

令 $N(h)$ 表示高度為 $h$ 的 AVL 樹的最少節點數。題目給定單一節點高度為 $0$，因此：

高度為 $1$ 時，根節點只需有一個子節點：

解題方法

高度為 $h$ 的最小 AVL 樹，其左右子樹高度必須分別為 $h-1$ 與 $h-2$，才能符合 AVL 的高度平衡限制。因此遞迴式為：

其中最後的 $1$ 代表根節點。

逐步計算：

題目有 $108$ 個節點：

因題目未提供原始圖形 Figure 1，依選項與典型 AVL 樹題型，合理假設原樹根節點為 73，左子樹包含 42（右子節點為 66），右子樹包含 94（左子節點為 87）。

步驟推導

1. 二元搜尋樹（BST）插入 key 60
   依據 BST 性質比對大小：$60 < 73 \to 60 > 42 \to 60 < 66$， key 60 插入至節點 66 的左子節點位置。

2. 計算平衡係數（Balance Factor, BF）

   • 節點 66：左子樹高度 1，右子樹高度 0，$\text{BF} = 1 - 0 = +1$。
   • 節點 42：左子樹高度 0，右子樹高度 2（路徑 $66 \to 60$），$\text{BF} = 0 - 2 = -2$，引發不平衡。

本題未附原始圖一（Figure 1）圖像，依據題幹與選項數字（12, 42, 54, 66, 73, 87, 94），合理假設初始 AVL 樹為包含該 7 個鍵值之滿二元搜尋樹結構。

1. 初始 AVL 樹結構分析

• 根節點（Root）：$66$
• 左子樹：根節點為 $42$，左子節點為 $12$，右子節點為 $54$
• 右子樹：根節點為 $87$，左子節點為 $73$，右子節點為 $94$

各節點之平衡因子（Balance Factor, $BF = h_{left} - h_{right}$）皆為 $0$，符合 AVL 樹定義。

核心觀念

根據伸展樹（Splay Tree）的攤還分析定理（Splay Theorem，由 Sleator 與 Tarjan 提出）：
對包含 $n$ 個項目的 Splay Tree 執行 $m$ 次 splay 操作，最壞情況下的累積總時間複雜度為 $O((m + n) \log n)$。

核心觀念

Splay tree（伸展樹）是一種自我調整的二元搜尋樹。每次搜尋、插入或刪除後，會將相關節點透過旋轉伸展至根節點。

其重要性質是：

• 單一操作的最壞情況時間複雜度：$O(n)$
• 一連串 $m$ 次操作的攤銷時間複雜度：$O(m\log n)$
• 因此，單一操作不能直接套用攤銷界限 $O(\log n)$。

本題特別問的是「one delete operation 的 worst-case time complexity」，也就是單次刪除的最壞情況，而不是連續操作的平均攤銷成本。

解題方法

刪除 Splay tree 中的某個節點時，通常分成以下步驟：

1. 先在樹中搜尋目標節點。
2. 將目標節點伸展至根節點。
3. 刪除根節點。
4. 將根節點的左、右子樹合併。

若目標節點到根節點的路徑長度為 $h$，搜尋與伸展的成本為 $O(h)$。合併左右子樹也需要沿著樹高進行操作，因此總成本為：

一般二元搜尋樹的高度最多為 $n-1$，Splay tree 雖然能改善長期操作的攤銷成本，但不保證每次操作的樹高都是 $O(\log n)$。因此最壞情況下：

所以單次刪除的最壞情況時間複雜度為：

核心觀念

紅黑樹必須符合以下性質：

1. 根節點必須是黑色。
2. 紅色節點的子節點必須是黑色，因此任意路徑上不能出現相鄰的紅色節點。
3. 每個節點到其後代 NIL 葉節點的所有路徑，黑色節點數量相同。
4. NIL 葉節點視為黑色，但通常題目計算「樹中的節點」時，不將 NIL 葉節點列入一般節點數量。

題目給定某條路徑上有 $3$ 個紅色節點，要求至少需要多少個黑色節點。

解題方法

由於紅色節點不能相鄰，$3$ 個紅色節點之間至少各要插入 $1$ 個黑色節點：

此外，紅黑樹的根節點必須為黑色；在最少情況下，這個根節點位於第一個紅色節點之前。最後一個紅色節點之後，為了連接至 NIL 黑色葉節點，至少還需要一個黑色節點。

因此，最少的根到葉路徑可表示為：

其中黑色節點數量為：

NIL 葉節點雖然也視為黑色，但不計入一般樹節點數量；即使將 NIL 納入黑高度計算，也不會改變選項中的答案判斷。

選項分析

核心觀念

本題考查 Binomial Tree（雙項樹） 的節點數量性質。

雙項樹 $B_k$ 的定義如下：

• $B_0$ 只有 $1$ 個節點。
• $B_k$ 由兩棵 $B_{k-1}$ 合併而成。

因此，若以 $N_k$ 表示雙項樹 $B_k$ 的節點數，則有遞迴式：

且

由此可得：

另外，雙項樹 $B_k$ 的根節點 degree 正好為 $k$，所以根的 degree 為 $8$ 時，該樹為 $B_8$。

解題方法

根節點 degree 為 $8$，表示這是一棵 $B_8$ 雙項樹。

其節點總數為：

因此正確選項為 E。

選項分析

核心觀念

Binomial heap 由多棵 binomial tree 組成，且每種階數至多有一棵。$B_k$ 樹包含 $2^k$ 個節點，根節點的子樹依序為 $B_{k-1},B_{k-2},\ldots,B_0$。

合併兩棵同階的 binomial tree 時，只需比較兩個根的鍵值，將鍵值較大的根接到較小根下方，時間為 $O(1)$。

解題方法

將陣列中的 $n$ 個元素各自視為一棵階數為 $0$ 的單節點樹，接著依照二進位進位方式合併同階樹：

• 若目前沒有階數 $k$ 的樹，放入該位置。
• 若已有一棵階數 $k$ 的樹，便將兩棵 $B_k$ 合併成一棵 $B_{k+1}$，如同二進位加法進位。
• 持續處理直到沒有同階樹重複。

每次合併只需 $O(1)$ 時間。初始有 $n$ 棵樹，最後剩下的樹數量等於 $n$ 的二進位表示中 $1$ 的個數，最多為 $\lfloor\log_2 n\rfloor+1$。因此合併次數為

總合併時間為 $O(n)$。最後掃描根串列找最小根，最多只有 $O(\log n)$ 棵樹，仍不超過 $O(n)$。

此外，讀取 $n$ 個輸入元素本身需要 $\Omega(n)$ 時間，因此建構時間為

所以其最緊確界為 $O(n)$。

選項分析

核心觀念

1. 二項堆疊（Binomial Heap）結構
   大小為 $N$ 的二項堆疊，其包含的二項樹（Binomial Tree）$B_k$ 對應於 $N$ 的二進位表示法中位數為 $1$ 的項：
   $2019 = 1024 + 512 + 256 + 128 + 64 + 32 + 2 + 1 = (11111100011)_2$
   故該堆疊包含二項樹：$B_{10}, B_9, B_8, B_7, B_6, B_5, B_1, B_0$。

2. 二項樹 $B_k$ 的分支度（Degree）分佈
   在一棵二項樹 $B_k$ 中，分支度為 $d$ 的節點數量 $N(k, d)$ 如下：

   • 若 $d = k$：$N(k, d) = 1$ （根節點）

核心觀念

Fibonacci heap 中，根節點的 degree 是其子節點數量。由 Fibonacci heap 的結構性質可知，若某節點的 degree 為 $d$，則以它為根的子樹至少包含

個節點，其中 $F_k$ 為 Fibonacci 數列：

因此，含有 $n$ 個節點的 Fibonacci heap，其任一節點的最大 degree $D(n)$ 滿足：

利用 Fibonacci 數列的漸近關係，也常寫成：

其中

為黃金比例。

解題方法

本題有 $n=256$ 個節點，直接尋找最大的 $d$，使得：

列出相關 Fibonacci 數：

當 $d=11$ 時：

當 $d=12$ 時：

所以最大可能 degree 為：

亦可用對數快速估算：

核心觀念

本題考查 Fibonacci heap 中 decrease-key 的時間複雜度，必須區分：

• 攤銷時間複雜度：decrease-key 為 $O(1)$。
• 單次最壞時間複雜度：可能觸發連鎖切割，為 $O(\log n)$。

Fibonacci heap 中每個節點的最大階數為 $O(\log n)$，因此一次 decrease-key 最多進行 $O(\log n)$ 次連鎖切割。

解題方法

題目問的是 $n$ 次 decrease-key 操作的最壞情況。

單次操作的最壞成本為：

因此，$n$ 次操作的最壞總時間為：

所以最緊的上界是：

需注意，若題目問的是「攤銷總時間」，則答案會是：

但本題明確詢問 worst-case time complexity，故採用單次最壞成本 $O(\log n)$。

選項分析

A. $O(n)$

錯誤。

$O(n)$ 是 $n$ 次 decrease-key 的攤銷時間上界，不是最壞情況總時間上界。最壞情況下，每次操作都可能觸發最多 $O(\log n)$ 層的連鎖切割。

核心觀念

Fibonacci heap 的 decrease-key 會降低節點鍵值。若降低後造成該節點小於其父節點，便違反最小堆序性，因此必須：

1. 將該節點從原父節點切下，加入根串列。
2. 若父節點已經被標記，則繼續將父節點切下，形成 cascading cut（級聯切割）。
3. 此過程可能沿著祖先鏈一路向上進行。

每一次切割與移動節點本身是 $O(1)$，因此總時間取決於級聯切割的次數。

需要區分兩種複雜度：

• 攤銷時間：$O(1)$
• 最壞情況時間：$O(n)$

Fibonacci heap 的「最大度數」是 $O(\log n)$，但這不代表樹的高度也是 $O(\log n)$。級聯切割可能沿著高度很大的父子鏈進行。

解題方法

一次 decrease-key 的最壞情況如下：

• 降低某個深層節點的鍵值；
• 該節點違反堆序，因此被切下；
• 其父節點已標記，也被切下；
• 再往上的祖先同樣已標記，持續被切下。

若父鏈長度為 $k$，便需要執行 $k$ 次切割。每次切割為 $O(1)$，所以：

Fibonacci heap 的樹高在最壞情況下可達 $O(n)$，因此：

而且確實存在需要切割線性數量節點的情況，所以最壞情況的緊確界為：

因此本題要求的最壞情況緊確上界是 $O(n)$。

選項分析

A. $O(1)$

錯誤。

$O(1)$ 是 Fibonacci heap 中 decrease-key 的攤銷時間複雜度。透過勢能函數，可以將平時不發生級聯切割時累積的勢能，用來支付之後的切割成本。

但單一操作在最壞情況下仍可能觸發大量級聯切割，因此不能宣稱最壞情況為 $O(1)$。