在线算法

在计算机科学中,在线算法是一种处理输入资料的独特形式,其演算过程中并不要求所有输入资料在算法开始运始之一刻即完备,反而可对逐步输入的资料加以处理并在输入完最后一项资料之后输出运算结果。与之相对的称为离线算法,则假设输入资料在运算开始前已完备。举例:选择排序是离线算法,而插入排序则为在线算法。

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

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

例子

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