41

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

（请不要链接到 Wikipedia 页面：我已经阅读过它，我仍在寻找澄清。如果我是 12 岁的解释和/或示例会更有帮助。）

4

7 回答 7

75

维基百科

维基百科页面非常清楚：

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

让我扩展上面的内容：

离线算法需要在算法开始之前的所有信息。在 Wikipedia 示例中，选择排序是离线的，因为第 1 步是Find the minimum value in the list. 为此，您需要提供整个列表 - 否则，您怎么可能知道最小值是多少？你不能。

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

还是不清楚？

想想下面的例子（对于四岁的孩子！）。大卫要求你解决两个问题。

在第一个问题中，他说：

“我要给你两个不同质量的球，你需要同时把它们从塔上扔下来……只是为了确保伽利略是对的。你不能用手表，我们只会用眼球它。”

在此处输入图像描述

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

对于第二个问题，大卫说

“好吧，这很顺利，但现在我需要你继续在球场上踢几个球。”

在此处输入图像描述

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

我希望这很清楚：D

于 2012-07-15T22:21:54.803 回答
6

在线算法仅逐段处理输入，并且在算法开始时不知道实际输入大小。

一个常用的例子是调度：你有一组机器和一个未知的工作负载。每台机器都有特定的速度。您希望尽快清除工作量。但是由于您从一开始就不知道所有输入（您通常只能看到队列中的下一个），您只能估计哪台机器最适合当前输入。这可能会导致您的工作负载分布不理想，因为您无法对输入数据做出任何假设。

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

例子：

工作量：
   1. 单位（重量：1）
   2. 单位（重量：1）
   3. 单位（重量：3）
机器：
   1.机器（1重量/小时）
   2.机器（2个重量/小时）

可能的结果（在线）：
   1. Unit -> 2. Machine // 2. Machine 现在有 30 分钟的工作量
   2. Unit -> 2. Machine // 2. Machine 现在的工作量为一小时
  任何一个
   3. Unit -> 1. Machine // 1. Machine 现在有三个小时的工作量
  或者
   3. Unit -> 2. Machine // 1. Machine 现在有 2.5 小时的工作量

 ==> 工作在 2.5 小时后完成

可能的结果（离线）：
   1. Unit -> 1. Machine // 1. Machine 现在有一个小时的工作量
   2. Unit -> 1. Machine // 1. Machine 现在有两个小时的工作量
   3. Unit -> 2. Machine // 2. Machine 现在有 1.5 小时的工作量

 ==> 2小时后工作完成

请注意，离线算法中的更好结果是唯一可能的，因为我们从一开始就没有使用更好的机器。我们已经知道会有一个重型单元（单元 3），所以这个单元应该由最快的机器处理。

于 2012-07-15T22:07:50.937 回答
2

离线算法在调用它的那一刻就知道它的所有输入数据。另一方面，在线算法可以在运行时获取部分或全部输入数据。

于 2012-07-15T22:07:33.580 回答
1

如果算法事先不知道将要执行的数据，则称该算法是在线的。离线算法可能会提前看到所有数据。

于 2012-07-16T04:33:53.943 回答
1

在线算法是一种接收一系列请求并响应每个请求立即执行操作的算法。

相反，离线算法在所有请求都被处理后执行动作。

Richard Karp 的这篇论文更深入地了解了在线、离线算法。

于 2015-06-15T06:55:14.513 回答
1

我们可以在算法处理之前根据输入的可用性来区分离线和在线算法。

离线算法：所有输入信息都可用于算法并由算法同时处理。借助完整的输入信息集，该算法找到了一种有效处理输入并获得最佳解决方案的方法。

在线算法：输入是即时进行的，即所有输入信息不能同时提供给算法，而是作为一个序列或一段时间内的一部分一部分。在输入可用时，算法必须在不知道未来输入信息的情况下立即做出决定。在此过程中，算法会产生一系列决策，这些决策将对其整体性能的最终质量产生影响。

例如：通信网络中的路由：

来自不同来源的数据包到达最近的路由器。多条通信链路连接到路由器。当新的数据包到达路由器时，路由器必须立即决定将数据包发送到哪个链路。（假设所有链路都路由到目的地，所有链路带宽相同，所有链路都是到目的地的最短路径的一部分）。这里，目标是在不知道未来数据包的情况下，将每个传入的数据包分配给其中一个链路，以使每个链路的负载得到平衡。任何链接都不应超载。这是一个负载平衡问题。

在这里，路由器中实现的调度器不知道未来的数据包，但它必须为每个传入的数据包做出调度决策。相比之下，离线调度器对所有传入的数据包有充分的了解，然后它可以有效地将数据包分配给不同的链路，并可以最佳地平衡不同链路之间的负载。

于 2017-09-07T12:26:46.373 回答
0

缓存缺失问题：在计算机系统中，高速缓存是一种内存单元，用于避免较快的处理器和最慢的主内存之间的速度不匹配。使用缓存的目的是通过在缓存中保留一些经常访问的页面来最小化平均访问时间。假设这些页面可能会在不久的将来被处理器请求。通常，当处理器发出页面请求时，会从主存储器或辅助存储器中取出该页面，并将该页面的副本存储在高速缓冲存储器中。假设缓存已满，那么缓存中实现的算法必须立即决定替换缓存块，而不知道未来的页面请求。问题出现了：必须替换哪个缓存块？（在最坏的情况下，您可能会在下一刻替换缓存块，被替换的缓存块的处理器请求）。因此，算法必须以这样一种方式设计，即它在传入请求到达时立即做出决定，而无需事先了解整个请求序列。这种类型的算法被称为在线算法

于 2017-09-07T12:48:09.897 回答