在线和离线算法有什么区别？ [英] What is the difference between an on-line and off-line algorithm?

问题描述

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

These terms were used in my data structures textbook, but the explanation was very terse and unclear. I think it has something to do with how much knowledge the algorithm has at each stage of computation.

（请不要链接到Wikipedia页面：我已经阅读过，并且我仍在寻找澄清。好像我十二岁时的解释岁以下和/或一个示例会更有用。）

(Please, don't link to the Wikipedia page: I've already read it and I am still looking for a clarification. An explanation as if I'm twelve years old and/or an example would be much more helpful.)

推荐答案

维基百科

Wikipedia页面非常清楚：

Wikipedia

The Wikipedia page is quite clear:

在计算机科学中，一种在线算法可以处理其
以串行方式逐个输入，即以
输入被馈送到算法的顺序，而从一开始就没有整个输入
。相反，离线算法从一开始就给
全部问题数据，并且需要输出一个
答案来解决当前的问题。 （例如，选择排序
要求在对整个列表进行排序之前给出整个列表，而
插入排序则不需要。）

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.)

让我继续上面的内容：

离线算法需要在算法开始之前的所有信息。在Wikipedia示例中，选择排序为离线，因为步骤1为在列表中找到最小值。为此，您需要提供整个列表-否则，您怎么可能知道最小值是什么？您不能。

An offline algorithm requires all information BEFORE the algorithm starts. In the Wikipedia example, selection sort is offline because step 1 is Find the minimum value in the list. To do this, you need to have the entire list available - otherwise, how could you possibly know what the minimum value is? You cannot.

插入排序是在线，因为它不需要知道有关它将对什么值进行排序以及在算法运行时请求信息的任何信息。简而言之，它可以在每次迭代时获取新值。

Insertion sort, by contrast, is online because it does not need to know anything about what values it will sort and the information is requested WHILE the algorithm is running. Simply put, it can grab new values at every iteration.

想到以下几点示例（适用于四岁儿童！）。大卫要您解决两个问题。

Think of the following examples (for four year olds!). David is asking you to solve two problems.

在第一个问题中，他说：

In the first problem, he says:

我要给你两个质量不同的球，你需要
同时从塔上放下它们。.只是为了确保Galileo
是正确的。你不能使用手表，我们只会盯上它。

"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."

如果我只给您一个球，您可能会看着我而感到奇怪你应该做什么。毕竟，说明很清楚。问题开始时，您需要两个球。这是一种离线算法。

If I gave you only one ball, you'd probably look at me and wonder what you're supposed to be doing. After all, the instructions were pretty clear. You need both balls at the beginning of the problem. This is an offline algorithm.

对于第二个问题，David说

For the second problem, David says

很好，但是现在我需要您继续将
a几个球踢过一个田地。

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

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

I go ahead and give you the first ball. You kick it. Then I give you the second ball and you kick that. I could also give you a third and fourth ball (without you even knowing that I was going to give them to you). This is an example of an online algorithm. As a matter of fact, you could be kicking balls all day.

我希望这很清楚：D

这篇关于在线和离线算法有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！