跳至內容

英文维基 | 中文维基 | 日文维基 | 草榴社区

線上演算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

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

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

例子

[編輯]

以下是一些線上演算法的例子