在线算法和离线算法的区别

本章浅谈一下在线算法，当然，说到在线算法会想到离线算法，这两个概念都会提到，帮助大家理解。

（一）在线算法

在计算机科学中，一个在线算法是指它可以以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经知道所有的输入。相对的，对于一个离线算法，在开始时就需要知道问题的所有输入数据，而且在解决一个问题后就要立即输出结果。例如，选择排序在排序前就需要知道所有待排序元素，然而插入排序就不必。

一个很好的展示在线算法概念的例子是加拿大旅行者问题，这个问题的目标是在一个有权图中以最小的代价到达一个目标节点，但这个有权图中有些边是不可靠的，可能已经被剔除。然而一个旅行者只有到某个边的一个端点时才能确定该边是否已经被移除了。最坏情况下，该问题会变得简单，即所有的不确定的边都被移除该问题将会变成通常的最短路径问题。

（二）离线算法

算法设计策略都是基于在执行算法前输入数据已知的基本假设，也就是说，对于一个离线算法，在开始时就需要知道问题的所有输入数据，而且在解决一个问题后就要立即输出结果，通常将这类具有问题完全信息前提下设计出的算法成为离线算法(offlinealgorithms)

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

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

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

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：