競爭比（competitive ratio）

你要怎麼評一個被迫盲目行動、看不到未來的決策者？拿她跟一個完美的先知比似乎不公平，但我們仍想要一個數字。競爭比就給出這樣一個數字：它衡量在最壞情況下，線上演算法比「事先知道整串輸入的最佳解」差了多少倍。它是線上演算法公認的計分卡，就像大O是執行時間的計分卡一樣。

精確地說：設 ALG(sigma) 是你的線上演算法在輸入序列 sigma 上付出的成本，OPT(sigma) 是任何離線演算法——一個一開始就看到整串 sigma 的演算法——在同一串 sigma 上能付出的最小成本。若存在常數 c（以及一個固定的加法常數 a），使得對「每一串」sigma 都有 ALG(sigma) <= c * OPT(sigma) + a，就說這個演算法是 c-競爭的。競爭比就是最小的這種 c。加法項 a 讓我們忽略微小的啟動效應，以捕捉長期行為。比值為 1 表示你追平全知的最佳解；比值為 2 表示你可能付出無法避免成本的兩倍，但絕不會更多。關鍵在於：標尺是 OPT，而不是你自己的最好情況——所以較大的比值誠實地反映了「不知未來」的代價。

這個想法之所以有力，是因為它是一個面對「故意設計輸入來害你的對手」也成立的最壞情況保證，但它從不為「任何真實演算法都無法避免的困難」責怪你（OPT 拿到的是同一串輸入）。它也是驚喜出沒之處：分頁的自然規則 LRU 是 k-競爭的，滑雪租賃的損益兩平策略是 2-競爭的，而這些界往往可證明是任何線上方法所能達到的最佳。誠實的提醒：競爭比是對抗性輸入上的最壞情況度量，所以 2-競爭的演算法並不是「通常差兩倍」——在典型輸入上它常常好得多；那個 2 只是有保證的天花板。