定义

因为它不知道整个输入，所以在线算法被迫做出后来可能不是最优的决策，并且在线算法的研究关注于在这种情况下可能的决策质量。竞争分析通过比较同一问题实例的在线和离线算法的相对性能来形成这一想法。具体而言，算法的竞争比率被定义为其成本的最坏情况比除以所有可能的输入的最优成本。在线问题的竞争比率是在线算法实现的最佳竞争比率。直观地，算法的竞争比率给出了该算法产生的解决方案的质量的度量，而问题的竞争比率表明了解该问题的未来的重要性。

其他解释

有关算法在线输入的其他观点，请参阅

流式算法：关注准确表示过去输入所需的内存量;

动态算法：专注于维护在线输入问题解决方案的时间复杂性。

例子

一些在线算法：

插入排序

感知

水库采样

贪心算法

对手模型

度量任务系统

赔率算法

页面替换算法

计算方差的算法

Ukkonen的算法

在线问题