本篇文章汇总一些与LP问题相关或者不清楚有没有关系但是看到了、觉得有意思的概念。
随时更新
在线算法与离线算法
Online算法和Offline算法的最大区别在于是否一开始就掌握所有的输入量。Online算法的输入量是“像流水线一样”到来的,算法要在每一个时间节点都做决策——尽管不知道之后的输入会是什么样。
对应地,离线算法就是从一开始就知道所有输入量的算法。一般的算法都是离线算法。
竞争分析(Competitive Analysis)和最坏情况分析(Worst-case Analysis)
这是评价一个在线算法性能的两种方法。前者关心在线算法与离线算法的效率之比,后者考虑在线算法在最不理想情况下的表现。
网友评论