在线和离线算法有什么区别？

Question

这些术语在我的数据结构教科书中使用,但解释非常简洁且不清楚.我认为这与算法在每个计算阶段有多少知识有关.

(请不要链接到维基百科页面:我已经阅读过了,我仍在寻找澄清.如果我十二岁和/或一个例子的解释会更有帮助.)

Answer 1

维基百科

维基百科页面非常清楚:

在计算机科学中,在线算法是能够以串行方式逐个处理其输入的算法,即,以输入被馈送到算法的顺序,而不是从一开始就可获得整个输入.相反,离线算法从一开始就给出了整个问题数据,并且需要输出解决手头问题的答案.(例如,选择排序要求在对其进行排序之前给出整个列表,而插入排序则不需要.)

让我扩展上述内容:

离线算法在算法启动之前需要所有信息.在Wikipedia示例中,选择排序是脱机的,因为步骤1是Find the minimum value in the list.要做到这一点,您需要提供整个列表 - 否则,您怎么可能知道最小值是什么？你不能.

相比之下,插入排序是在线的,因为它不需要知道它将排序什么值以及在算法运行时请求信息.简而言之,它可以在每次迭代时获取新值.

还不清楚吗？

想想以下例子(对于四岁的孩子!).大卫要求你解决两个问题.

在第一个问题中,他说:

"我会,给你两个不同质量的球,你需要同时从塔上扔下它们......为了确保伽利略是正确的.你不能使用手表,我们只是眼球它."

如果我只给你一个球,你可能会看着我并想知道你应该做什么.毕竟,说明很清楚.在问题开始时你需要两个球.这是一种离线算法.

对于第二个问题,大卫说

"好的,情况相当顺利,但是现在我需要你继续前进并在球场上踢几个球."

我继续给你第一个球.你踢它.然后我给你第二个球,然后你踢它.我也可以给你第三和第四球(你甚至不知道我会把它们交给你).这是在线算法的一个例子.事实上,你可能整天踢球.

我希望这很清楚:D

Answer 2

在线算法只是逐个处理输入,并且不知道算法开始时的实际输入大小.

一个经常使用的例子是调度:你有一组机器和一个未知的工作负载.每台机器都有特定的速度.您希望尽快清除工作负载.但由于您从一开始就不知道所有输入(您通常只能看到队列中的下一个),因此您只能估计哪个机器最适合当前输入.这可能导致工作负载的非最佳分配,因为您无法对输入数据进行任何假设.

另一方面,离线算法仅适用于完整的输入数据.在算法开始处理数据之前,必须知道所有工作负载.

例:

Workload:
   1. Unit (Weight: 1)
   2. Unit (Weight: 1)
   3. Unit (Weight: 3)
Machines:
   1. Machine (1 weight/hour)
   2. Machine (2 weights/hour)

Possible result (Online):
   1. Unit -> 2. Machine  // 2. Machine has now a workload of 30 minutes
   2. Unit -> 2. Machine  // 2. Machine has now a workload of one hour
  either
   3. Unit -> 1. Machine  // 1. Machine has now a workload of three hours
  or 
   3. Unit -> 2. Machine  // 1. Machine has now a workload of 2.5 hours

 ==> the work is done after 2.5 hours

Possible result (Offline):
   1. Unit -> 1. Machine  // 1. Machine has now a workload of one hour
   2. Unit -> 1. Machine  // 1. Machine has now a workload of two hours
   3. Unit -> 2. Machine  // 2. Machine has now a workload of 1.5 hours

 ==> the work is done after 2 hours

请注意,离线算法中的更好结果是可能的,因为我们从一开始就不使用更好的机器.我们已经知道将有一个重型单元(单元3),所以这个单元应该由最快的机器处理.