跳转到内容

線上演算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

注意:插入排序始终生成一个最优的结果,也就是说一个正确排序的列表。然而对于很多问题,線上演算法的性能比不上离线算法(即无法取得最优的结果)。如果对于同一个问题的在线算法和最优化的离线算法的性能比率是有界的,那么这个在线算法被称作是competitive。

并非所有在线算法都有与之对应的离线算法。

例子

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