“在线”上的区别是什么和“离线”算法？ [英] 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 know with how much knowledge the algorithm has at each stage of computation.

PS - 请不要链接到维基百科页面，我已经阅读了，仍在寻找澄清。一个解释，就像我十二岁，和/或一个例子会更有帮助。

PS - Please don't link to the wikipedia page, I have already read it and still am looking for clarification. An explanation as if I am twelve years old and/or an example would be much more helpful.

推荐答案

维基百科

查看维基百科页面时，您不明白什么？

Wikipedia

What, exactly, do you not understand when looking at the Wikipedia page?

在电脑中科学，一种在线算法是一种可以以串行方式逐个处理其
的算法，即按照
输入被馈送到算法的顺序，而不需要整个输入
从一开始就可用。相比之下，离线算法从一开始就给出了整个问题数据
，需要输出一个解决问题的
答案。 （例如，选择排序
要求在排序之前给出整个列表，而
插入排序则不会。）

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

让我在上面展开：

离线算法在算法开始之前需要所有的信息。在维基百科的例子中，选择排序是离线，因为步骤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.

相比之下，插入排序是在线，因为它不需要知道它将排序什么值，并且信息被请求WHILE算法正在运行。简单来说，它可以在每次迭代中获取新的价值。

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:

$ b $ 我是，给你两个不同群众的球，你需要
从塔上同时放下，只是为了确保伽利略
是正确的不能使用手表，我们只会眼球。

"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

I hope this was clear :D

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