在线算法、离线算法、半在线算法

解释一下在线算法（Online Algorithm），离线算法（Offline Algorithm）和半在线算法（Semi-Online Algorithm）的区别。

最近一直看算法，以后也会多记录一些相关内容。

在线算法 & 离线算法

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

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

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

以上摘录自维基百科。

在线算法只能得到一个最好的概率，没有办法去选取一定是最好的值。其实人生就是这样的一个在线算法，由于你永远不知道下一步会怎样，只能根据过去来猜测。一旦走错了，就无法再重来，你永远也没有“如果一切可以重来，我会选择……”的机会，希望我们都按照在线算法一样做出了最好的选择。智者曾说过“30岁前不要怕，30岁之后就不要悔”，一旦做出了决定就不要后悔，因为即使后悔也没有重来的机会了。

PS：说下在线算法(online algorithm)和离线(offline algorithm)算法，离线算法也就是知道了所有的输入，根据某些条件来选取最佳策略，而在线算法就是无法预知到后面的输入，只能按照目前的状况来做出下一步的最好决策，在线算法追求的是与离线算法一样的好结果。关于在线算法的详细信息可以看维基。写到后面想起了suit同学的口头禅“人一辈子就不能做错事”，呵呵。

半在线算法

半在线算法，就是指一部分信息是预先知道的，另一部分信息预先不知道。

总结

• 在线算法：啥都不知道。
• 离线算法：啥都知道。
• 半在线算法：部分知道。

如有不对的地方请指正。

参考文献

• https://zh.wikipedia.org/wiki/%E7%B7%9A%E4%B8%8A%E6%BC%94%E7%AE%97%E6%B3%95
• http://www.cnblogs.com/wanghetao/archive/2012/03/31/2427625.html
• https://www.zhihu.com/question/20142996

扩展阅读：

• https://www.zhihu.com/question/28025036