滑雪租賃問題（ski-rental problem）

你打算開始學滑雪，但你完全不知道自己會不會愛上它而滑上好幾年，還是冷颼颼地玩一個週末就放棄。每天上雪場，你可以花 1 美元租雪具，或一次花 B 美元買一副、之後永遠不再付租金。如果你知道未來——確切會滑幾天——選擇很簡單：滑很多天，第一天就買；滑沒幾天，租就好。問題是你「不」知道未來，而且每天早上都得重新決定租或買，且不能反悔。這個小謎題是整個線上演算法思想最乾淨的示範。

以下是經典策略以及它為何好。前 B-1 天都用租的；若到第 B 天你還在滑，就買。把你的成本拿來跟 OPT 比，OPT 是你若事先知道總滑雪天數 T 會付的成本。若 T < B，最佳解是租滿 T 天（成本 T），你也只租（成本 T）——你恰好追平 OPT。若 T >= B，最佳解是第一天就買（成本 B），而你租了 B-1 天後才買，付 (B-1) + B = 2B - 1。所以在每種情況下你的成本最多是 2*OPT - 1：這條規則是 2-競爭的。直覺是「平衡」：你拒絕買，直到租金已經花得幾乎跟買一樣多，於是一次浪費掉的購買，傷你絕不會超過兩倍。

滑雪租賃的意義遠遠超出雪具：它是不確定下「按次付費 vs 一次付清」每一個決策的範本——維持資料庫連線開啟（租）還是快取結果（買）；反覆關閉並重啟雲端伺服器，還是預留它；讓自旋鎖繼續空轉，還是付出代價做情境切換。這裡的 2-競爭保證是任何確定性線上策略所能達到的最佳；巧妙地擲硬幣（隨機化）可以把期望比值壓低到 e/(e-1)，約 1.58。誠實的提醒：乾淨的因子 2 假設你知道 B；若租金或 B 本身會漂移，分析必須重做。