線上演算法（online algorithm）

想像一位停車場管理員，每輛車一駛進來，她就得立刻揮手指引它停進某個車位——她不能先等著看總共會來幾輛車、車有多大，再決定。每個選擇都是最終的，而且只能憑過去與現在做出，永遠看不到未來。線上演算法正是這樣運作：輸入一次只到一塊，演算法必須在下一塊揭曉之前，就對眼前這塊承諾一個動作。這和離線演算法（offline algorithm）恰恰相反，後者一開始就拿到完整輸入，可以先把全部研究透徹再動手。

更精確地說，輸入是一串請求 r1, r2, r3, ... 一個一個揭曉。當請求 r_t 到來時，演算法必須只用 r1..r_t（以及自己過去的回應）來產生對 r_t 的回應，而且這個回應之後不能反悔。想想一個簡單的線上任務：你管理衣帽間，每位客人離開時你得決定要不要再多開一分鐘的隊伍——一旦關閉就無法重開。由於演算法看不到接下來會發生什麼，它可能被逼進「此刻看來沒問題、等後面序列出現才知道很糟」的選擇。這就是核心困難所在：不是不夠聰明，而是缺乏資訊。

線上演算法之所以重要，是因為真實計算中有極大一部分都是線上的：快取必須在不知道下一個請求是什麼之前就先逐出某頁；路由器在看到其餘流量之前就得轉送一個封包；投資人在明天的價格出現之前就得買進或賣出。我們不能只拿這種演算法跟它自己的最壞情況比，因為某些困難是無法避免的——所以我們改拿它跟「知道整個未來的最佳離線解」相比。這個比較就是競爭比。誠實的提醒：這裡的「線上」並不是指「在網際網路上」，而是指決策是逐步、不可撤回、且在不知未來的情況下做出的。