研究所考試

我們在之前的專欄《 線上演算法(1) 》中介紹了線上演算法的概念。不同於典型的離線演算法（offline algorithms）會在演算法執行前就取得完整輸入，線上演算法的輸入會在演算法執行的過程中才逐步出現，而非一開始就完整給定。因此，線上演算法會需要在不清楚未來狀況的前提下，一邊接收輸入，一邊做出決策，會更傾向於使用保守策略，確保無論輸入如何，解的品質都不會差到某個不可接受的程度。

常見的線上演算法解法爲競爭分析（competitive analysis），比較線上演算法產生的解與一個知道未來輸入的最佳演算法所產生的解，並在所有可能實例上取最壞比例，來分析線上演算法。在搭電梯問題中，我們會需要判斷是否該繼續等電梯，還是選擇走樓梯，因此誕生三種策略：「永遠走樓梯」、「永遠搭電梯」以及綜合前面兩種的「權衡利弊」，透過三者的競爭比率來分析優劣。在這次的專欄中，我們會藉由串列維護這個問題，並透過之前專欄提及的競爭分析與分攤分析，提供此問題一個優秀的線上演算法解法。

問題定義

在資料結構中，鏈結串列（Linked List） 是非常基礎且常用的結構。當我們要在一個包含 n 個元素的雙向鏈結串列 L = {x₁, x₂,..., x_n} 中尋找某個特定的元素 x_n 時，最基本的方法就是從頭開始一個一個往後找，這個程序被稱為 LIST-SEARCH。

成本定義

在搜尋元素的過程中，會有兩個需要負擔的代價（cost）。首先是搜尋成本：如果目標元素排在串列的第 i 個位置，我們就必須檢查 i 個元素才能找到它，因此搜尋成本就是 i。再來是調整成本：在鏈結串列中，重新排列元素的唯一合法手段是交換兩個相鄰的元素（討論此問題時假設串列為雙向串列），因此每次交換相鄰元素的成本定義為 1。

舉例來說，假設現在串列是 〈5, 3, 12, 4, 8, 9, 22〉。如果我們要搜尋元素「8」，它排在第 5 個位置，那麼搜尋到「8」這個元素的成本就是5。如果搜尋完後，我們想把它向前移動兩個位置（跟 4 交換、再跟 12 交換），需要執行 2 次交換，交換成本是 2。因此這次操作的總成本就是 5 + 2 = 7。維護串列的意義

這種問題在實務上非常常見。最著名的例子就是雜湊表（Hash Table）。當雜湊表發生碰撞時，通常會使用「鏈結法（Chaining）」，讓每個槽（Slot）後面都掛著一個鏈結串列。如果我們能動態地把「經常被搜尋的元素」往前排，就能大幅縮短未來的搜尋時間，進而使整個系統的效能大幅提升。

維護串列的理想狀況是，如果你能預知未來，知道某些元素會被瘋狂搜尋，那你只要提前把它們排到最前面，總成本就會降到最低。而最壞狀況則是，如果你運氣很差，無論你怎麼排，每一次的搜尋請求剛好都是串列的「最後一個元素」，那麼搜尋 m 次的總成本將高達 θ(nm)。 演算法（1）：FORESEE

擁有「預知未來」的超能力。它在開始執行前，就已經看過了整整 m 次的完整搜尋序列。因此，它可以在最完美的時機點對串列進行微調，達到理論上的最低成本。

演算法（2）：MOVE-TO-FRONT

無法「預知未來」，因此選擇非常簡單粗暴的策略：「只要某個元素被搜尋到，就立刻透過連續的相鄰交換，把它一路送到串列的最前端。」我們來計算MOVE-TO-FRONT的成本，首先假設在執行前，目標元素 k 位於串列的第 r_L (k) 個位置。此時搜尋到該元素的成本為r_L (k)，而移動到最前面所需的成本為 r_L (k)-1，因此MOVE-TO-FRONT每一次的搜尋的成本為：

實際對比

我們假設初始串列為〈1,2,3,4,5〉，而搜尋的順序為5,3,4,4。

先分析FORESEE：第一步爲搜尋 5，搜尋成本 5，它選擇按兵不動（交換 0 次）。單步成本 = 5，串列維持 〈1,2,3,4,5〉。第二步爲搜尋 3，搜尋成本 3。但因為它預知後面要瘋狂搜尋 4，它決定付出 3 的交換成本，把 4 先移動到到最前面！單步成本 = 3 + 3 = 6。串列變為 〈4,1,2,3,5〉。在第三步和第四步時，因為第二步早早把 4 放到了最前，接下來兩次搜尋 4 的成本都只要 1，最終成本為：5+6+1+1=13。

再分析MOVE-TO-FRONT：第一步爲搜尋 5，搜尋成本 5，交換 4 次移到最前。單步成本 = 5 + 4 = 9。串列變為 〈5,1,2,3,4〉。第二步爲搜尋 3，搜尋成本 4，交換 3 次。單步成本 = 4 + 3 = 7。串列變為 〈3,5,1,2,4〉。在第三步和第四步時，由於 4 之前被擠到後面，第三步花了 9 的代價才把它移到前端。直到第四步，4 已經在最前面了，這才享受到了單步成本 1 的甜頭。最終成本為：9+7+9+1=26。

在這個例子中，MOVE-TO-FRONT 的總成本是 FORESEE 的 2 倍。而接下來我們要證明：不論未來的序列有多長、多詭異，MOVE-TO-FRONT 的總成本最多都不會超過 FORESEE 的 4 倍！但在證明之前，我們需要先引入兩個數學工具：「反序」與「集合劃分」。

反序（Inversion）

反序是指同一對元素，在兩個串列中的相對前後順序不一樣。我們用隊伍來舉例：小明和小華在排隊。在串列 L 中，小明排在小華前面；但在串列 L’ 中，小華卻排在小明前面。這對「小明與小華」就是一個反序。兩個串列之間所有的反序總數，稱為反序計數（Inversion Count），記作 I(L,L’)。反序計數越高，代表兩個串列的排序狀態越不相同、越混亂。如果我們將某個串列中相鄰的兩個元素交換，那麼它跟另一個串列的反序計數，不是剛好 +1，就是剛好 -1。

集合劃分 在第 i 次搜尋開始前（此時 MOVE-TO-FRONT 的串列為 L_i-1^M，FORESEE 的串列為 L_i-1^F），我們要搜尋元素 x。我們將串列中的其他所有元素，根據它們排在 x 的前面還是後面，劃分為三個陣營：

• BB (Before, Before)：在 MOVE-TO-FRONT 裡排在 x 前面，在 FORESEE 裡也排在 x 前面的元素。
• BA (Before, After)：在 MOVE-TO-FRONT 裡排在 x 前面，但在 FORESEE 裡卻排在 x 後面的元素。
• AB (After, Before)：在 MOVE-TO-FRONT 裡排在 x 後面，但在 FORESEE 裡卻排在 x 前面的元素。

利用這三個集合，我們可以精準寫出 x 在兩個串列中的絕對索引位置：

現在，我們要使用勢能法（Potential Method）來計算攤銷成本。首先定義位能函數，我們將第 i 步執行完後的位能定義為：

換句話說，兩串列間每存在一個反序，就儲存 2 單位的位能。因為反序數不可能為負，所以位能恆大於等於 0。當 MOVE-TO-FRONT 搜尋完 x 後，它會把 x 一路跟前面的元素交換，直到最前端。這時會發生兩件事：

• 與 BB 集合的元素交換：原本 x 和 y（屬於 BB）在兩個串列中都是「y 在 x 前面」，順序一致。現在 MOVE-TO-FRONT 把 x 換到 y 前面了，導致兩者的相對順序變得不一致。這會創造一個新的反序。
• 與 BA 集合的元素交換：原本在 MOVE-TO-FRONT 中 z（屬於 BA）在 x 前面，但在 FORESEE 中 x 在 z 前面，順序本來是衝突的。現在 MOVE-TO-FRONT 把 x 換到 z 前面，相對順序反而變得跟 FORESEE 一致，因此消滅一個原本的反序。

因此，MOVE-TO-FRONT 的這群交換操作，會讓反序總數淨增加 |BB| - |BA|。因為一個反序代表 2 單位位能，所以 MOVE-TO-FRONT 造成的位能變化量為 2(|BB| - |BA|)。

依據分攤分析的公式，第 i 步的攤銷成本等於「實際成本 + 位能變化量」：

接著，我們帶入實際成本與 MOVE-TO-FRONT 的位能變化：（t_i 是 FORESEE 自己偷偷做的交換次數，每次交換最多增加 2 單位位能，所以加上 2t_i。）

利用前面提到的絕對索引位置計算公式，可將 rL_i-1^M (x) 替換成 |BB|+|BA|+1，帶入展開並化簡後可得：

為了引入 FORESEE 的位置公式，我們刻意加上正數項（把等號右側變成包含 |AB| 的形式），並利用絕對索引位置計算公式整理成 FORESEE 搜尋 x 的成本。此時我們會發現等號右側的搜尋成本加上交換次數，就是 FORESEE 在第 i 次付出的實際成本！

最後，當我們將 m 次操作的攤銷成本全部加總，整理後可得：

這樣的結果證明，無論遇到任何情況的串列搜尋，MOVE-TO-FRONT 的成本絕對不會超過 FORESEE 的 4 倍，也代表 MOVE-TO-FRONT 的競爭比率為 4（4-competitive）。

透過今天的專欄，我們對於線上演算法的分析有了更近一步的認識。在串列維護問題當中，我們可以使用分攤分析的勢能法定義位能，證明出在每一次搜尋時都把目標移至最前方的演算法 MOVE-TO-FRONT，其解的品質最差只會比全知全能的演算法 FORESEE 多 4 倍！這個經典的例子也說明線上演算法的奧妙之處：明明 MOVE-TO-FRONT 對於未來的輸入一無所知，我們卻能透過巧妙地設計位能函數，把前期頻繁搬動元素的成本存為對未來有利的位能儲備，並且能跟全知視角的 FORESEE 打得有來有回，交出競爭比率 4 的好成績。