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

Question

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

(请不要链接到维基百科页面:我已经阅读过它，但我仍在寻找澄清。好像我十二岁的解释和/或示例会更有帮助.)

Answer 1

维基百科

维基百科页面很清楚:

In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. (For example, selection sort requires that the entire list be given before it can sort it, while insertion sort doesn't.)

让我对上面的内容进行扩展:

离线算法在算法开始之前需要所有信息。在维基百科示例中，selection sort 离线 因为第 1 步是在列表中查找最小值。为此，您需要提供整个列表 - 否则，您怎么可能知道最小值是多少？您不能。

相比之下，插入排序是在线，因为它不需要知道要排序的值的任何信息，并且在算法运行时请求信息。简单地说，它可以在每次迭代中获取新值。

还是不清楚？

思考以下示例(适合四岁的 child !)。大卫要你解决两个问题。

在第一个问题中，他说:

"I'm, going to give you two balls of different masses and you need to drop them at the same time from a tower.. just to make sure Galileo was right. You can't use a watch, we'll just eyeball it."

如果我只给你一个球，你可能会看着我，想知道你应该做什么。毕竟，指示非常明确。在问题开始时你需要两个球。这是一个离线算法。

对于第二个问题，大卫说

"Okay, that went pretty well, but now I need you to go ahead and kick a couple of balls across a field."

我继续给你第一个球。你踢它。然后我给你第二个球，你踢那个。我还可以给你第三个和第四个球(你甚至不知道我要把它们给你)。这是一个在线算法的例子。事实上，您可能整天都在踢球。

我希望这是清楚的 :D