遊戲的新規則：未來是看不見的
你至今學過的每個演算法，都共享一項悄無聲息的奢侈：在它動第一步之前，整個輸入就已經攤在它面前。合併排序看得到整個陣列；戴克斯特拉演算法看得到整張圖；連背包問題這種難題，至少也一開始就知道所有物品。這一階把這份奢侈扔掉。線上演算法一次只收到一段輸入，而且必須在下一段抵達之前，對當前這一段做出不可撤回的回應。它不准等待、不准偷看後面、也不准反悔。未來是貨真價實地藏著的，而決定一旦做出便是定局。
這並不是為了刁難而捏造的人為限制——它就是真實系統的日常處境。快取必須在還不知道下一個被請求的頁面是哪一個之前，就決定要逐出什麼。叫車服務必須現在就派一輛車給乘客，而不是等整晚的請求都明朗後才派。路由器轉發一個封包時，看不到明天的流量。在每一種情形裡，等待完整輸入都是不可能的，因為輸入就是未來本身。所以我們需要一套方法，去設計這種「盲目決策」的演算法，而且更難的是——需要一把公平的尺，去衡量一個盲目的決策者，最好究竟能做到什麼程度。
那把尺：與一位先知競爭
一個註定會犯下某些錯誤的演算法——只因它看不見未來——你要怎麼給它打分數？把它的成本拿去和零相比並不公平；和另一個線上演算法相比則說明不了什麼。乾淨俐落的點子，也是這一整階的核心，就是拿它去和最佳離線演算法相比——一位想像中的對手，通常稱為 OPT，他事先就拿到了整段輸入序列，並把它打得完美無瑕。OPT 是一位先知：它不是你真能執行的演算法，而是事後諸葛的黃金標準。我們的線上演算法必須盲打；OPT 則手握整份劇本。
競爭比就是記錄這道落差的那個數字。對一個最小化問題（付出某種成本，例如快取未命中或金錢），若對每一段輸入序列都有 cost(ALG) <= c 乘以 cost(OPT) + b，其中 b 是一個不隨輸入增長的固定常數，我們就說線上演算法 ALG 是 c-競爭的。那個加法的 b 用來吸收微小的起始效應；真正要緊的是乘法的 c。一個 2-競爭的演算法承諾：無論未來丟給我什麼，我付出的永遠不超過一位全知規劃者所付的兩倍。這個承諾對每一段序列都成立——它是一個最壞情況的保證，與上一階的近似比精神完全相同，只是這裡由「擁有後見之明的 OPT」扮演了當時那個未知最佳解的角色。
滑雪租借：最小的誠實範例
感受競爭分析最乾淨的地方，是滑雪租借問題。你在滑雪，但你不知道自己還會滑幾天——可能一天，也可能整季。每天你可以花 $1 租雪具，或在任何時刻花 $B（比方說 $10）直接買斷，之後永遠免費滑。如果你事先就知道總天數，選擇便輕而易舉：滑不到 B 天就全程租，滑 B 天以上就第一天買。但你並不知道——每天早上你都得在看不見未來的情況下，決定租還是買。這是「租還是買」的縮影，而它無處不在：要嘛持續付一筆小小的反覆成本，要嘛一次付清讓它消失。
著名的策略是這樣：前 B-1 天都用租的，若到了第 B 天你還在滑，就買。把它拿去和 OPT 對照看。若這一季結果很短——你滑了 k < B 天就停——你租掉了 k 元，而 OPT（知道 k）也會租 k 天，於是打平。若這一季很長——你滑了至少 B 天——你付了 B-1 元租金再加 B 元買斷，共 2B-1 元；但 OPT 知道季節很長，會在第一天就花恰好 B 元買下。比值是 (2B-1)/B = 2 - 1/B，略小於 2。所以這條簡單的規則是 (2 - 1/B)-競爭的：你付出的永遠不超過先知的、本質上兩倍的金額。
rent-until-break-even (buy price = B):
days_rented = 0
while you are still skiing today:
if days_rented == B-1:
buy ($B), ski free forever # break-even reached
else:
rent today ($1); days_rented += 1
worst case total = (B-1) + B = 2B-1 , OPT = B -> ratio 2 - 1/B為什麼不早一點或晚一點買？一個對手論證把它釘死。假設你的規則是「第 m 天買」。對手知道 m，就乾脆讓你在買完的隔天停止滑雪：你白買了。買太早（m 小），一個短季節就抓住你買了幾乎沒用到的雪具；買太晚（m 大），一個長季節就抓住你遠遠租過了損益兩平點。損益兩平的選擇 m = B 是唯一的平衡點，它讓兩個陷阱付出相同的倍數，而沒有任何確定性規則能勝過 2 - 1/B。最後這句話是一個貨真價實的下界，不是想像力的不足——對手可被證明地，至少以這個幅度擊敗每一個確定性策略。
分頁：每一個快取核心裡的同一個觀念
滑雪租借是個玩具，但同一套機制統治著每一台電腦內部的一個問題：分頁。快取裝著 k 頁的快速記憶體；對頁面的請求一次來一個；請求一個已在快取中的頁面是免費的（命中），但請求一個不在的頁面是一次缺頁，迫使你載入它，並逐出某一頁以騰出空間。你要逐出哪一頁？你必須現在就選，看不到未來的請求流。我們計數的成本是缺頁次數，而我們要問：一條線上逐出規則，能逼近那個無可避免的最小值到什麼程度？
這裡的離線最佳解是一條美麗的先知規則，叫做 Belady 演算法：永遠逐出那個「下次被使用最遙遠」的頁面。它可被證明為最佳——卻無法線上執行，因為它讀取了未來。真實的快取使用像 LRU（逐出最久未使用的頁面）或 FIFO 這樣的規則。令人矚目的定理是：LRU 與 FIFO 各自恰好是 k-競爭的：在最壞的序列上，它們的缺頁次數可達 Belady 的 k 倍，其中 k 是快取大小，而沒有任何確定性的線上分頁規則能勝過 k。所以一個 1000 槽的快取，最壞情況下可能比後見之明多缺頁 1000 倍——令人清醒，然而這正是可達成的最佳確定性保證，而在具有局部性的真實軌跡上，LRU 通常表現得遠優於這道天花板。
下界的那一半同樣是一個對手論證，而它的形狀值得一看。把注意力限制在 k+1 個不同的頁面上——比快取能裝的多一個。無論線上演算法用什麼確定性規則，對手知道這條規則，就永遠請求「演算法剛剛逐出的那一頁」。於是每一個請求都是缺頁：k+1 個請求、k+1 次缺頁，長期下來幾乎每一步都缺頁。同時 Belady 握住「除了下次最遙遠被用到那頁以外」的所有頁，在同一序列上大約每 k 個請求才缺頁一次。相除便得到倍數 k。對手要揭露最壞情況，從不需要超過 k+1 個頁面——一個小巧而精確的構造，恰如當初為頂點覆蓋設下界的那個匹配。
隨機性鬆開了對手的掌握
那些下界——滑雪租借的 2 - 1/B、分頁的 k——感覺像牆。但它們只是確定性演算法的牆，因為對手的全部力量都來自「精確預測你會怎麼做」。一旦你的演算法擲起硬幣，對手就失去了那份確定：它仍能選擇輸入，卻再也無法知道你會逐出哪一頁、會在哪一天買。這正是當初讓隨機快速排序能抵抗「已排序輸入」攻擊的同一根槓桿——隨機性奪走了對手的固定靶。面對一個健忘的（oblivious）對手（一個事先把整段序列定死、不會根據你的擲幣結果調整的對手），隨機化能把競爭比大幅拉低。
對滑雪租借而言，一個隨機化的買入日（從一個精心偏斜的機率分布中選擇何時買，而非固定在第 B 天）把期望競爭比從 2 降到 e/(e-1)，約 1.58——一個真實的改進，靠的不是運氣，而是把成本在擲幣上取平均所證明出來的。對分頁而言，隨機化的標記演算法達成約 2 ln k 的期望比值，而非 k：對 k = 1000 而言，那大約是 14 而非 1000，一道巨大的落差。誠實的但書與隨機快速排序的相同：這些改進後的比值是對演算法內部隨機性取的期望值。在任何單獨一次執行上你都可能更糟；被保證的是「在擲幣上取平均」的結果，對每一個健忘對手能挑的固定輸入都成立。
它的位置，以及這一階接下來的去向
退一步，看見那幅統一的圖像。競爭分析在精神上，就是你一再做過的同一個動作：把一個不可知的量，釘在一個可計算的替身上。在近似裡，那是被廉價下界困住的 OPT；在這裡，那是被「與一位早已看穿它的先知相比較」所困住的未來。這一階的每一道前沿，都鬆開一個你曾視為理所當然的不同假設。線上演算法捨棄了「你在決定前能看到整個輸入」這個假設。接下來的幾篇捨棄其他的：你能儲存整個輸入、最壞情況是唯一誠實的視角、指數時間是難結構唯一的代價。
- 第 2 篇捨棄儲存假設：串流模型，資料只奔流而過一次，而記憶體小得遠不足以留住它——而草圖讓你即便如此仍能用可證明的極小空間回答問題。
- 第 3 篇從結構著手對付難度：參數化複雜度與固定參數可解，當你隔離出一個小參數、把指數爆炸限制在它身上時，一個 NP 困難問題就變得可解。
- 第 4 篇在證明用罄時轉向實務：區域搜尋與元啟發式法——模擬退火及其同類——它們朝好解攀爬，沒有競爭保證，卻有現實世界的肌肉。
- 第 5 篇質疑最壞情況本身：平滑分析只要把對手的輸入稍加擾動，便能解釋為何理論上令人畏懼的演算法在實務中如魚得水。
從這篇帶走一個習慣，它會陪你走完這一階其餘的路：每當一個演算法必須在某種限制下行動——沒有未來、沒有記憶、沒有時間——先說出它被拿去衡量的那個全能對手是誰，再找出那個簡單的對手構造，去封頂「任何人最好能做到多好」。滑雪租借的損益兩平日、分頁的 k+1 個頁面，都不是孤立的把戲；它們是同一套誠實的會計，被施加在任何「無知有其代價」之處。