線上演算法

在電腦科學中,線上演算法是一種處理輸入資料的獨特形式,其演算過程中並不要求所有輸入資料在演算法開始運始之一刻即完備,反而可對逐步輸入的資料加以處理並在輸入完最後一項資料之後輸出運算結果。與之相對的稱為離線演算法,則假設輸入資料在運算開始前已完備。舉例:選擇排序是離線演算法,而插入排序則為線上演算法。

注意:插入排序始終生成一個最優的結果,也就是說一個正確排序的列表。然而對於很多問題,線上演算法的性能比不上離線算法(即無法取得最優的結果)。如果對於同一個問題的在線算法和最優化的離線算法的性能比率是有界的,那麼這個在線算法被稱作是competitive。

並非所有在線算法都有與之對應的離線算法。

例子

以下是一些在線算法的例子