114 年 國立臺灣大學資料科學碩士學位學程《資料結構與演算法》

分析
設 $T_*(n)$ 為印出 * 的期望次數，$T_!(n)$ 為印出 ! 的期望次數。

• 若 $n=0$，只印 !，故 $T_!(0)=1,\;T_*(0)=0$。
• 若 $n\ge1$，演算法先印出 $n$ 個 *，再以均勻隨機 $p\in\{1,\dots,n-1\}$ 分割成兩子陣列，遞迴處理。

因此

$$T_*(n)=n+\frac{1}{n-1}\sum_{p=1}^{n-1}\bigl(T_*(p)+T_*(n-p)\bigr) \tag{1}$$

核心觀念

Akra–Bazzi 定理用來分析分治遞迴式，尤其適合各子問題規模不相同的情況。常見形式為

$$T(x)=\sum_{i=1}^{k} a_iT(b_ix+h_i(x))+g(x),$$

其中 $a_i>0$、$0<b_i<1$，而 $h_i(x)$ 是相對於 $x$ 足夠小的規模擾動項。函數 $g(x)$ 需符合定理要求的正則性與多項式成長條件。

先找出滿足下式的實數 $p$：

$$\sum_{i=1}^{k}a_ib_i^p=1.$$

接著，遞迴式的漸近解由下式決定：

$$T(x)=\Theta\left(x^p\left(1+\int_1^x\frac{g(u)}{u^{p+1}}\,du\right)\right).$$

解題方法

逐一檢查選項是否符合定理的適用範圍與結論：

• 定理可處理不同大小的子問題。
• 定理對非遞迴項 $g(n)$ 有成長條件。
• 定理給出漸近複雜度，不保證總能得到封閉形式。
• Akra–Bazzi 的適用範圍比 Master 定理廣。
• 指數 $p$ 是方程式的實數解，不要求為整數。

核心觀念

本題考查 $c$-means／$k$-means 的分群數、距離與分群結果的關係，以及演算法的收斂與時間複雜度。

設定 $c=3$ 表示演算法以三個群集為目標，但不代表相近的兩筆資料必定同群，也不代表演算法找到全域最佳解。標準 $k$-means 每次迭代的時間複雜度為 $O(nkd)$；若迭代 $I$ 次，總時間複雜度為 $O(nkdI)$，其中 $n$ 是資料筆數、$k$ 是群集數、$d$ 是特徵維度。

解題方法

逐項檢查敘述是否能由演算法定義保證：

1. 分群數設為三，是否代表任何距離度量下都必定收斂並產生三群？
2. 兩序列的 Hamming 距離較小，是否足以保證它們同群？
3. 演算法是否保證找到全域最佳解？
4. 特徵向量不同，是否代表兩序列不能同群？
5. 時間複雜度是否能忽略群數、特徵維度與迭代次數？

選項分析

(A) 錯誤。 設定 $c=3$ 是指定目標群數，不代表「不論距離度量都必定停止並產生三個非空群集」。標準 $k$-means 的中心更新使用特徵平均值，演算法本身也不是對任意距離度量都能直接套用。題目敘述的「總是」與「不論距離度量」過於絕對。

(B) 錯誤。 序列 a 與 b 的 Hamming 距離為 $1$，因為只有最後一個字元不同：

關鍵概念

• 全局比對使用 Needleman‑Wunsch DP。
• DP 表格大小為 $(m+1)\times(n+1)$，故時間 $O(mn)$，空間亦 $O(mn)$（未做空間優化）。
• 轉移式必須同時考慮匹配/錯配、插入與刪除三種情形。

選項判斷

• (A) $O(m+n)$ 為線性時間，與 DP 需要遍歷整個表格不符 → 錯。
• (B) 空間 $O(mn)$ 正確，但題目要求「關於 DP 解法的正確敘述」中，較核心的是遞迴關係式 → 次要。
• (C) 正確：

核心觀念

每個頂點的初始值是其度數，也就是相鄰頂點的數量。每次迭代時，頂點的新值等於上一輪所有鄰點的值總和；所有頂點都使用同一輪的舊值計算，再同時更新。完成兩輪後，依數值由大到小排序；數值相同時，標籤較小者排前面。

圖中的鍵結視為無向圖的邊，每條鍵結只計為一條邊。

解題方法

依圖可列出各頂點的鄰點：

頂點	鄰點
1、2	3
3	1、2、4
4	3、5
5	4、6、10
6	5、7
7	6、8
8	7、9
9	8、10
10	5、9、11
11	10、12、13
12、13	11

依標籤 $1$ 至 $13$ 排列，初始度數為

$$(1,1,3,2,3,2,2,2,2,3,3,1,1)$$

第一輪以初始度數加總鄰點的值，得到

$$(3,3,4,6,7,5,4,4,5,8,5,3,3)$$

第二輪改以第一輪的值加總鄰點的值，得到

$$(4,4,12,11,19,11,9,9,12,17,14,5,5)$$

核心觀念

本題考無限背包問題：每種物品都能重複選取，總尺寸不得超過容量 $17$，並使總價值最大。

令 $dp[w]$ 表示容量為 $w$ 時可取得的最大價值，則遞迴式為：

$$dp[w]=\max_{\substack{i\in\{A,B,C,D,E\}\\s_i\le w}}\bigl(dp[w-s_i]+v_i\bigr)$$

其中 $s_i$、$v_i$ 分別是物品 $i$ 的尺寸與價值。由於物品可重複選取，每次計算都能再次使用任一種物品。

解題方法

依照尺寸由小到大計算 $dp[w]$，得到：

容量 $w$	0	1	2	3	4	5	6	7	8
最大價值 $dp[w]$	0	0	0	4	5	5	8	10	11

容量 $w$	9	10	11	12	13	14	15	16	17

核心觀念

這題考「棒球淘汰問題」中的最大流建模。假設 E 贏下剩餘 28 場比賽後，E 最多有

$$48+28=76$$

勝。因此 A、B、C、D 各自還能增加的勝場上限分別為：

$$A:76-75=1,\quad B:76-71=5,\quad C:76-69=7,\quad D:76-63=13$$

建圖時，源點連到每一組對戰的比賽節點，容量為該組剩餘比賽數；比賽節點連到參賽隊伍節點，容量視為無限；各隊伍節點再連到終點，容量為該隊可增加的勝場上限。

解題方法

A、B、C、D 之間共有六組對戰，場數為：

$$AB=5,\quad AC=7,\quad AD=4,\quad BC=2,\quad BD=4,\quad CD=4$$

源點到六個比賽節點的總容量為

$$5+7+4+2+4+4=26$$

隊伍 D 雖然可增加至多 13 勝，但與 A、B、C 之間只有

$$4+4+4=12$$

場比賽，所以最多只能從這些對戰流入 12 單位。A、B、C 的勝場容量合計為

$$1+5+7=13$$

核心觀念

本題考漸近成長率的比較。若

$$\lim_{n\to\infty}\frac{g_2(n)}{g_1(n)}=\infty$$

則 $g_2$ 的成長速度快於 $g_1$，應選 $(g_1,g_2)$。

依題目常見排版還原，函數為 $f_2(n)=2^{\log n}$、$f_4(n)=\sqrt{2^n}$、$f_5(n)=n^5(\log n)^2$；採演算法常用的 $\log_2 n$。選項 E 的「$f_s$」依函數編號判讀為 $f_3$。

解題方法

先判斷各函數的漸近成長率：

• $f_1(n)=n$，是線性成長。

• $f_2(n)=2^{\log_2 n}=n$，與 $f_1$ 同階。

• $f_3(n)=\dfrac{n}{n-4}$。當 $n\to\infty$ 時，

  $$\lim_{n\to\infty}\frac{n}{n-4}=1$$

  因此 $f_3(n)=\Theta(1)$。

• $f_4(n)=\sqrt{2^n}=2^{n/2}$，是指數成長。

• $f_5(n)=n^5(\log n)^2$，是多項式乘上對數因子。

由此得到成長順序：

$$f_3 \prec f_1\sim f_2 \prec f_5 \prec f_4$$

其中 $\prec$ 表示右側函數成長較快，$\sim$ 表示兩者同階。特別是，指數函數 $2^{n/2}$ 的成長快於任何固定次方的多項式乘對數因子。

選項分析

核心觀念

本題考遞迴式的漸近解，主要工具包括：

• 主定理（Master Theorem）：處理 $T(n)=aT(n/b)+f(n)$，比較 $f(n)$ 與 $n^{\log_b a}$ 的成長速度。
• 遞迴展開與遞迴樹：將每層的工作量加總，適合分析縮小幅度不相同的子問題。
• 直接代入與幾何級數：可用來推導單一路徑遞迴，或驗證線性時間上界。

解題方法

逐一將各選項的遞迴式展開，並比較其實際成長速度與選項所聲稱的漸近界。

(A) $T(n)=2T(n/2)+\Theta(n)$

由主定理，$a=2$、$b=2$，因此

$$n^{\log_b a}=n^{\log_2 2}=n.$$

而 $f(n)=\Theta(n)$，與 $n^{\log_b a}$ 同階，故

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

選項聲稱 $\Theta(n^2)$，不正確。

(B) $T(n)=7T(n/2)+\Theta(n^2)$

由主定理，$a=7$、$b=2$，所以遞迴子問題的基準項為

$$n^{\log_b a}=n^{\log_2 7}.$$

因為 $\log_2 7>2$，$n^2$ 比 $n^{\log_2 7}$ 成長得慢，符合主定理第一種情形。因此

$$T(n)=\Theta(n^{\log_2 7}).$$

選項正確。

(C) $T(n)=\log n+T(\sqrt n)$

每次遞迴都將問題規模開平方。令 $n_0=n$，經過 $i$ 次遞迴後，問題規模為

$$n_i=n^{1/2^i}.$$

遞迴停止時，$n_i$ 小於固定常數 $c$。取對數後可知，遞迴層數為 $\Theta(\log\log n)$。

第 $i$ 層的非遞迴工作量為

$$\log(n_i)=\log\left(n^{1/2^i}\right)=\frac{\log n}{2^i}.$$

將各層工作量加總：

$$\sum_{i=0}^{\Theta(\log\log n)}\frac{\log n}{2^i} =\Theta(\log n),$$

因為這是首項為 $\log n$ 的幾何級數。因此選項正確。

(D) $T(n)=2^nT(n-1)$

依題目排版，選項聲稱解為 $(\sqrt{2})^{n^2+n}$。反覆展開遞迴式：

A：錯。二元樹僅是每個節點至多有左、右子樹；二元搜尋樹必須滿足「左子樹所有鍵 < 根鍵 < 右子樹所有鍵」的排序性質，並非所有二元樹皆符合。

B：錯。若插入順序為已排序序列，BST 會退化成鏈狀，最高可達 $h = n-1$，高度上界僅為 $O(n)$，非必然 $O(\log n)$。

C：錯。尋找給定節點的後繼（次小元素）需沿父指標上移或向右子樹的最左葉子，最壞情況需走過樹高 $h$，時間 $O(h)$，在一般 BST 中 $h$ 可能為 $\Theta(n)$，不保證 $O(1)$。

核心觀念

碰撞總數可寫成每一對不同物件是否落入同一桶的指示變數總和：

$$T=\sum_{\{i,j\}\subseteq S}\mathbf{1}[h(a_i)=h(a_j)]$$

因此，期望值為：

$$\mathbb{E}[T] =\sum_{\{i,j\}\subseteq S}\Pr[h(a_i)=h(a_j)]$$

共有 $\binom{n}{2}$ 對物件。均勻雜湊下，每對碰撞機率是 $1/m$；通用雜湊則保證每對碰撞機率至多為 $1/m$。題目中 $m=\lfloor n^{1.5}\rfloor=\Theta(n^{1.5})$，所以這兩種情況的期望碰撞數都是 $O(n^{0.5})$，自然也是 $O(n)$。

解題方法

對選項 (C) 的仿射雜湊函數，令兩個鍵相差 $d$。因為 $b$ 會在比較時抵消，碰撞條件是：

$$ad\equiv 0\pmod m$$

當 $m$ 是合數時，這個條件可能對多個 $a$ 成立，碰撞機率可能大於 $1/m$。要判斷最壞情況期望是否仍為 $O(n)$，可取一組讓許多物件對都在同一類碰撞條件下的鍵。

對選項 (D)，隨機的 $c$ 只是對所有雜湊值加上相同常數，不會改變物件彼此是否碰撞。因此可直接尋找許多鍵，使 $x^2+x$ 在模 $m$ 下相同。

選項分析

(A) 正確。 均勻雜湊下，每一對不同鍵的碰撞機率為 $1/m$，故

$$\mathbb{E}[T]=\binom{n}{2}\frac{1}{m} =\Theta\left(\frac{n^2}{n^{1.5}}\right) =\Theta(n^{0.5})=O(n)$$

(B) 正確。 通用雜湊保證任意一對不同鍵的碰撞機率至多為 $1/m$，所以

$$\mathbb{E}[T]\le \binom{n}{2}\frac{1}{m} =O(n^{0.5})=O(n)$$

(C) 錯誤。 取 $n=k^2$，其中 $k$ 為質數，則 $m=k^3$。令輸入鍵為

$$0,\ k^2,\ 2k^2,\ \ldots,\ (k^2-1)k^2$$

核心觀念

最小生成樹（MST）是總權重最小的生成樹。兩棵 MST 的共同邊權重相同，因此若它們的對稱差集為 $F$，則 $F$ 中來自兩棵樹的邊，按每個權重值分別計算時，數量相等。

本題也考查割性質：若某條邊是其跨越割中唯一最輕的邊，則它會出現在每一棵 MST 中。

解題方法

逐項檢查 $F$ 的結構、邊權與總權重，再判斷「最遠 MST」問題是否能以多項式時間求解。

選項分析

(A) 錯誤。 $H=(V,F)$ 不一定是由路徑與環組成的互不相交聯集，因為頂點在 $F$ 中的度數可以大於 $2$。

例如取所有邊權皆為 $1$ 的完全圖 $K_4$，頂點為 $a,b,c,d$。令

$$T_1=\{ab,ac,ad\},\qquad T_2=\{ab,bc,cd\}.$$

兩者都是 MST，而

$$F=\{ac,ad,bc,cd\}.$$

在 $H$ 中，頂點 $c$ 與 $a,b,d$ 相連，度數為 $3$，故 $H$ 不是路徑與環的互不相交聯集。

(B) 錯誤。 $F$ 中可以有不同權重的邊。

例如以一條權重為 $0$ 的橋連接兩個三角形；其中一個三角形的三條邊權重皆為 $1$，另一個三角形的三條邊權重皆為 $5$。兩棵 MST 可以在兩個三角形中分別選擇不同的邊。此時 $F$ 同時含有權重為 $1$ 與權重為 $5$ 的邊。

(C) 正確。 假設邊 $e$ 的權重在整張圖中只出現一次。若 $e$ 出現在某棵 MST $T_1$，刪除 $e$ 會將 $T_1$ 分成兩個連通部分，形成一個割。依 MST 的割性質，$e$ 必為跨越此割的唯一最輕邊，因此必出現在每一棵 MST。

核心觀念

這段程式的架構是「每次從尚未處理的頂點中，取出目前標記值最小的頂點，再更新它的鄰點」。三個問題都能使用這種逐步選取頂點的架構，但標記值的意義與更新方式不同：

• 最短距離：$A[v]$ 表示從 $s$ 到 $v$ 的目前最短距離估計。
• 瓶頸路徑：$A[v]$ 表示從 $s$ 到 $v$ 的路徑中，最小可能的最大邊權。
• 最小生成樹：$A[v]$ 表示將 $v$ 接到目前生成樹所需的最小邊權。

前兩者是 Dijkstra 類型的標記更新；最小生成樹則是 Prim 演算法。三者的「選最小標記頂點」相似，但更新公式與最後輸出不可混為一談。

解題方法

要判斷選項，分別檢查三件事：更新式是否維持正確的標記意義、回傳值是否符合問題目標，以及是否能用 Fibonacci heap 支援必要操作。

三個問題的正確更新方式如下。

ST-DISTANCE

$$A[y]\gets \min\{A[y],\,A[x]+w(x,y)\}$$

回傳 $A[t]$。更新時必須與原標記比較，保留較小的距離候選值。

ST-BOTTLENECK

$$A[y]\gets \min\{A[y],\,\max\{A[x],w(x,y)\}\}$$

延伸一條邊後，路徑的瓶頸值是原瓶頸與新邊權的較大者；再從所有候選路徑中取最小值。回傳 $A[t]$。

MST

使用 Prim 演算法時，更新式為

$$A[y]\gets \min\{A[y],\,w(x,y)\}$$

此處 $A[y]$ 是將 $y$ 接入目前生成樹所需的最小邊權。最小生成樹總權重應回傳所有頂點鍵值的總和，而非單一頂點的 $A[t]$：

$$\sum_{v\in V} A[v]$$

根頂點的 $A[s]=0$，因此不影響總和。

選項分析

(A) 錯誤。
選項給的更新式是 $A[y]=A[x]+w(x,y)$，沒有與 $A[y]$ 原值取最小值，可能把較好的候選距離覆寫成較差的距離。

核心概念
此題的重點在於了解 平面格狀圖的最小 $s$-$t$ 切割 與 對偶圖的最短路徑 之間的關係，以及 最大流–最小割定理 的正確應用與演算法時間複雜度。

---

(A) 逐一列舉至多 $2^{2n}$ 個邊集合即可得到最小割

• 錯誤原因

  • 最小割的 邊數 未必受 $2n$ 的上界限制。雖然任一 單調路徑 長度為 $2n-2$，但最小割的邊集合不一定形成單一路徑；它可以是一條在對偶圖中的曲線，跨過多於 $2n$ 條原圖邊。例如，若所有邊權重相同，最小割會是 寬度為 $n$ 的切線，其跨過的邊數為 $n$，已超過 $2n$ 的上界並不保證。
  • 更嚴重的是，若某些邊的權重為 $0$，最小割可能會包含大量 $0$ 權重的邊，而仍保持同樣的最小總權值。此時最小割的邊數可高達 $\Theta(n^2)$。因此僅列舉「至多 $2^{2n}$」的子集合 不一定涵蓋所有可能的最小割，會遺漏正確答案。

• 結論：此敘述 不正確。

---

(B) 最小割的跨邊必形成從 $(n,1)$ 到 $(1,n)$ 的單調路徑

• 錯誤原因

  • 最小割在原圖中對應的是 對偶圖的一條最短路徑。對偶圖的頂點是原圖的面，而對偶圖的邊對應原圖的邊。此最短路徑的起點與終點分別位於 西南邊界 與 東北邊界 的 面，而非原圖的頂點 $(n,1)$、$(1,n)$。
  • 因此跨過的邊集合 不一定 按照原圖頂點的單調路徑排列；它可能在格子中「蜿蜒」而形成曲線。

• 結論：此敘述 不正確。

---

(C) 用 Dinic 計算最大流，時間 $O(n)$，即得最小割值

• 正確的部分

  • 以每條無向邊建立兩條相反方向的有向邊，容量等於該邊的權重，確實可以把問題轉成 最大流，再利用 最大流–最小割定理 取得最小割值。

• 錯誤的部分

  • 圖 $G$ 有 $n^2$ 個頂點與約 $2n(n-1)=\Theta(n^2)$ 條邊。Dinic 演算法在一般圖上的時間複雜度為 $O(E\sqrt V)$（在單位容量圖上為 $O(E\log V)$），在此情況下至少是 $O(n^2\sqrt{n^2})=O(n^3)$，遠大於 $O(n)$。
  • 敘述中將時間誤寫為 $O(n)$，顯然不符合實際分析。

• 結論：此敘述 不正確（雖然概念正確，但時間複雜度錯誤，使整體敘述錯誤）。

---

(D) 最小割的跨邊即為從 WS 到 NE 的最短路徑，使用 Bellman‑Ford

核心觀念

只要一條樹邊兩端的節點原本同色，就至少要重新著色其中一端。把「需要重新著色的節點」視為頂點集合，這個集合必須涵蓋所有同色邊，因此是同色邊所形成圖上的頂點覆蓋。

重新著色的總權重要最小，所以目標是求最小權重頂點覆蓋。由於新顏色彼此唯一，重新著色的節點不會再與相鄰節點同色。

解題方法

令 $G_T$ 是由樹 $T$ 的節點及「兩端原本同色」的邊所構成的圖，則

$$f(T)=\text{$G_T$ 的最小權重頂點覆蓋值}.$$

若 $T'$ 是由根節點開始、沿著原色與根相同的節點所形成的連通子樹，$T'$ 內的同色邊正是需要處理的邊。離開 $T'$ 後，每個邊界子樹可獨立處理。因此，正確的分解是 $T'$ 的最小權重頂點覆蓋值，加上所有「接在 $T'$ 節點底下、但不屬於 $T'$」的子樹答案：

$$f(T)=\operatorname{MVC}(T')+\sum_{a\in T'}\ \sum_{\substack{b\in\{a.l,\,a.r\}\\ b\neq\perp,\ b\notin T'}} f(T_b)$$

其中 $T_b$ 是以 $b$ 為根的子樹，$\operatorname{MVC}(T')$ 表示 $T'$ 上同色邊的最小權重頂點覆蓋值。題目選項的求和寫成 $\operatorname{Leaf}(T)$，也就是原樹的葉節點；葉節點沒有子樹，這一項恆為 0，等於完全沒計入 $T'$ 外面那些子樹的成本。即使改成 $\operatorname{Leaf}(T')$ 也不夠，因為異色子樹也可能接在 $T'$ 的內部節點下。

選項分析

(A) 錯誤。
重新著色的節點須構成頂點覆蓋，不是最大權重獨立集。兩者雖有補集關係，但最大權重獨立集的權重本身不等於最小權重頂點覆蓋的權重。以根權重為 $1$、兩個葉節點權重各為 $10$，且三者同色為例，最小權重頂點覆蓋只需重新著色根，權重為 $1$；最大權重獨立集則選兩個葉節點，權重為 $20$。此外，求和索引也有上述葉節點記號問題。

(B) 依題目字面寫法錯誤。
最小權重頂點覆蓋是正確的核心模型，但求和範圍寫為 $\operatorname{Leaf}(T)$，因此公式不完整。

核心觀念

將 $x_i\in\{0,1\}$ 放寬為 $0\le x_i\le1$，即可得到線性規劃鬆弛 $P'$。本題要分別計算：

• $\alpha$：原 0-1 整數規劃的可行解數。
• $\beta$：原問題的最優整數解數。
• $\gamma$：整數間隙。以下採最大化問題常用的乘法定義：$\gamma=\mathrm{OPT}_{LP}/\mathrm{OPT}_{IP}$。
• $v_4$：鬆弛可行區域在四維空間中的體積。
• $v_3$：鬆弛最優解集合的三維體積。

解題方法

1. 計算整數可行解與最優解

若 $x_2=1$，第三條限制式變成

$$x_1+x_3+8+7x_4\le8,$$

因此只能有 $(x_1,x_2,x_3,x_4)=(0,1,0,0)$，這一解的目標值為 $0$。

若 $x_2=0$，只需檢查 $(x_1,x_3,x_4)$ 的 8 種組合。當 $(x_1,x_3,x_4)=(1,1,1)$ 時，三條限制式左側皆為 $9$，不符合上限 $8$；其餘 7 種組合皆可行。因此

$$\alpha=7+1=8.$$

在可行整數解中，目標值最大的組合為 $(1,0,0,1)$ 與 $(0,0,1,1)$，兩者目標值皆為 $7$。所以

$$\mathrm{OPT}_{IP}=7,\qquad \beta=2.$$

2. 求線性規劃鬆弛的最優值與最優解集合

將三條限制式分別乘上 $\frac25,\frac15,\frac25$ 後相加，左側得到

$$2x_1+2x_3+5x_4+\frac{19}{5}x_2\le 8.$$

因為 $x_2\ge0$，所以 $P'$ 的目標值滿足

$$2x_1+2x_3+5x_4\le8.$$

關鍵概念

• $X\le _p Y$ 表示在多項式時間內把 $X$ 轉換為 $Y$。
• 若 $X\le _p Y$ 且 $Y\in\mathsf P$，則 $X\in\mathsf P$。
• 若 $X\le _p Y$ 且 $X$ 為 NP‑hard，則 $Y$ 也是 NP‑hard（或更難）。
• 若 $X\le _p Y$ 且 $Y\le _p X$，則 $X$ 與 $Y$ 多項式等價，擁有相同的複雜度等級。

逐項判斷

(A) 錯
$A$ NP‑hard 且 $A\le _p B$ ⇒ $B$ 至少同樣 NP‑hard，不能保證 $B\in\mathsf P$。

(B) 正
假設 $B$ NP‑hard 且 $E\le _p B$。已知 $B\le _p C$ 與 $C\le _p E$，得到

$B\le _p C\le _p E\le _p B,$

核心觀念

使用**勢能法（potential method）**分析攤銷成本。若一次操作的實際成本為 $c_i$，勢能函數為 $\Phi$，則該操作的攤銷成本定義為

$$\hat{c}_i = c_i + \Phi_i - \Phi_{i-1}.$$

只要每次操作的攤銷成本都有固定上界，且勢能非負、初始勢能為 $0$，就能推出從全零開始執行 $n$ 次操作的總實際成本為 $O(n)$。

解題方法

設 $t$ 為此次遞增時，最低位起連續的 $1$ 的個數。也就是說，$A[0],\ldots,A[t-1]$ 都是 $1$，而 $A[t]=0$。這次操作會：

• 讀取 $A[0]$ 到 $A[t]$，共 $t+1$ 次讀取。
• 將 $A[0],\ldots,A[t-1]$ 設為 $0$，並將 $A[t]$ 設為 $1$，共 $t+1$ 次寫入。

每次寫入成本至多為

$$\max\left(\frac{31}{3},\frac{51}{5},1\right)=\frac{31}{3}.$$

因此，這次操作的實際成本至多為

$$c_i \le (t+1)\left(1+\frac{31}{3}\right) = \frac{34}{3}(t+1).$$

定義勢能函數為

$$\Phi(A)=\frac{34}{3}\sum_{r=0}^{k-1} A[r].$$

核心觀念

這題考兩件事：

1. NP 完全性證明：證明問題屬於 NP，並從已知的 NP 完全問題做多項式時間歸約。
2. 子集合和的近似演算法：以動態規劃列出可達子集合和，定期刪除彼此太接近的值，將清單大小控制在多項式範圍內。

由於 $S$ 中每個數都是奇數，任一子集合的和，其奇偶性等於該子集合的元素個數奇偶性。因此，和為奇數的子集合必定含有奇數個元素。

(a) NP 完全性證明

屬於 NP

證明者提供一個子集合 $T\subseteq S$ 作為憑證。可在多項式時間內計算 $\operatorname{sum}(T)$、確認它等於 $k$，並確認 $|T|$ 為奇數。因此 ODDNUMBERSUM 屬於 NP。

NP 困難

由 SUBSET SUM 歸約。給定一個正整數集合 $\{a_1,\ldots,a_n\}$ 與目標 $t>0$，問題是是否存在子集合，其和為 $t$。

若 $n$ 為偶數，加入一個數 $t+1$；這個數大於目標，不能出現在任何解中。如此可令 $n$ 為奇數而不改變答案。以下仍以 $n$ 表示調整後的元素數量，並令

$$R=2n+1,\qquad M=3^n,\qquad C=\sum_{i=0}^{n-1}3^i.$$

對每個 $a_i$ 建立兩個數：

$$x_i=1+2R(Ma_i+3^{i-1}),\qquad y_i=1+2R\cdot 3^{i-1}.$$

令新集合與目標為

$$S'=\{x_i,y_i:1\le i\le n\},\qquad k'=n+2R(Mt+C).$$

每個 $S'$ 中的數都是正奇數，且因 $n$ 為奇數，$k'$ 也是奇數。這些數彼此不同：同一組中的 $x_i\ne y_i$；不同索引的 $3^{i-1}$ 編碼可區分同類數字，而 $M$ 大於所有編碼項之和，也能區分 $x_i$ 的原始數值部分。

若 $S'$ 中某子集合的和為 $k'$，設它選了 $q$ 個數。每個數都可寫成 $1$ 加上 $2R$ 的倍數；又 $q\le 2n<2R$ 且 $n<2R$，比較兩邊除以 $2R$ 的餘數可得 $q=n$。