这些术语在我的数据结构教材中使用，但解释很简略且不清楚。我认为它与算法每个计算阶段拥有多少知识有关。
（请不要链接到维基百科页面：我已经阅读过它，仍然在寻找澄清。以十二岁的方式解释和/或提供示例会更有帮助。）
在线算法和离线算法有什么区别？
47
- ordinary
2
1http://xlinux.nist.gov/dads/HTML/offline.html - Robert Harvey
1http://xlinux.nist.gov/dads/HTML/online.html - Robert Harvey
7个回答
82
维基百科
维基百科页面很清楚：
在计算机科学中，在线算法是一种可以按顺序逐个处理输入的算法，即按照输入到算法的顺序进行处理，而不需要从一开始就拥有整个输入。相比之下，离线算法从一开始就给出了所有问题数据，并要求输出解决该问题的答案。（例如，选择排序需要在对其进行排序之前提供整个列表，而插入排序则不需要。）
让我对上述内容进行扩展：
离线算法需要在算法开始之前获得所有信息。在维基百科的例子中，selection sort 是 离线 的，因为第一步是 查找列表中的最小值。为了做到这一点，你需要拥有整个列表 - 否则，你怎么可能知道最小值是什么呢？ 你不可能知道。
相比之下，插入排序是在线排序的，因为它不需要知道要排序的值的任何信息，并且在算法运行时请求信息。简而言之，它可以在每次迭代时抓取新值。
还不清楚？
想象一下以下例子（适用于四岁儿童！）。大卫要求您解决两个问题。
在第一个问题中，他说：
“我会给你两个具有不同质量的球，你需要从一个塔上同时将它们扔下来..只是为了确保伽利略是对的。你不能使用手表，我们只能凭眼观察。”
对于第二个问题，David说：
“好的，那个很顺利，但现在我需要你去踢几个球穿过一个场地。”
我先给你一颗球，你踢它。然后我再给你第二颗球，你也踢它。我甚至可以给你第三颗、第四颗球（而你甚至不知道我会给你这些球）。这就是一个在线算法的例子。事实上，你可以整天踢球。
希望这很清楚 :D
- David Titarenco
2
1您至少需要3个球，其中只有两个需要在4岁以下在线示例开始时可用。眼球稍后会出现 :) - sehe
在线算法与一遍算法有何关联？根据维基百科的定义：
一遍算法是一种流式算法，它仅按顺序读取其输入，而不进行无限制的缓冲。一遍算法通常需要O(n)（参见“大O”符号）时间和少于O(n)（通常为O(1)）的存储空间，其中n是输入的大小。在线算法是否是一遍算法的子集，其中算法的时间复杂度为O(n)，其存储复杂度为O(1)？也就是说，对于给定的任务，在线算法是否是最有效的一遍算法？谢谢！ - tonix6
一种在线算法仅逐步处理输入，并且在算法开始时不知道实际输入大小。常用的例子是调度：您有一组机器和一个未知的工作负载，每台机器都有特定的速度。您想尽快清除工作负载。但由于您不从一开始就知道所有输入（通常您只能看到队列中的下一个输入），因此您只能估计哪个机器最适合当前输入。这可能会导致工作负载的非最优分配，因为您无法对输入数据做出任何假设。
另一方面，离线算法仅使用完整的输入数据。在算法开始处理数据之前，必须了解所有工作负载。
示例：
工作负载： 1. Unit (重量：1) 2. Unit (重量：1) 3. Unit (重量：3) 机器： 1. Machine (每小时1重量) 2. Machine (每小时2重量)
可能的结果（在线）： 1. Unit -> 2. Machine // 2.机器现在的工作负载为30分钟 2. Unit -> 2. Machine // 2.机器现在的工作负载为1小时 要么 3. Unit -> 1. Machine // 1.机器现在的工作负载为3小时 或者 3. Unit -> 2. Machine // 1.机器现在的工作负载为2.5小时
==> 在2.5小时后完成工作
可能的结果（离线）： 1. Unit -> 1. Machine // 1.机器现在的工作负载为1小时 2. Unit -> 1. Machine // 1.机器现在的工作负载为2小时 3. Unit -> 2. Machine // 2.机器现在的工作负载为1.5小时
==> 在2小时后完成工作
请注意，离线算法中更好的结果仅是可能的，因为我们没有从一开始就使用更好的机器。我们已经知道将会有一个重的单位（单位3），因此应该由最快的机器处理此单位。
另一方面，离线算法仅使用完整的输入数据。在算法开始处理数据之前，必须了解所有工作负载。
示例：
工作负载： 1. Unit (重量：1) 2. Unit (重量：1) 3. Unit (重量：3) 机器： 1. Machine (每小时1重量) 2. Machine (每小时2重量)
可能的结果（在线）： 1. Unit -> 2. Machine // 2.机器现在的工作负载为30分钟 2. Unit -> 2. Machine // 2.机器现在的工作负载为1小时 要么 3. Unit -> 1. Machine // 1.机器现在的工作负载为3小时 或者 3. Unit -> 2. Machine // 1.机器现在的工作负载为2.5小时
==> 在2.5小时后完成工作
可能的结果（离线）： 1. Unit -> 1. Machine // 1.机器现在的工作负载为1小时 2. Unit -> 1. Machine // 1.机器现在的工作负载为2小时 3. Unit -> 2. Machine // 2.机器现在的工作负载为1.5小时
==> 在2小时后完成工作
请注意，离线算法中更好的结果仅是可能的，因为我们没有从一开始就使用更好的机器。我们已经知道将会有一个重的单位（单位3），因此应该由最快的机器处理此单位。
- Zeta
2
1今天学到了新东西，就像维基百科文章所说的一样。 - Robert Harvey
1@RobertHarvey：没有看过维基百科的文章，不知道这是好事还是坏事:D。 - Zeta
2
离线算法在调用时就已经知道所有的输入数据。而在线算法则可能在运行过程中获取部分或全部的输入数据。
- ltjax
1
我们可以根据算法在处理输入之前的可用性来区分离线和在线算法。
离线算法：所有输入信息都对算法可用，并由算法同时处理。通过完整的输入信息集，算法找到一种有效处理输入并获得最优解的方法。
在线算法：输入是动态的，即所有输入信息不是同时可用的，而是作为序列或随时间推移的一部分逐步提供。一旦有一个输入可用，算法必须立即做出决策，没有未来输入信息的任何知识。在这个过程中，算法产生一系列决策，这些决策将对其整体性能的最终质量产生影响。
例如：通信网络中的路由： 不同源的数据包到达最近的路由器。有多个通信链接连接到路由器。当一个新的数据包到达路由器时，路由器必须立即决定将数据包发送到哪个链接。（假设所有链接都被路由到目的地，所有链接带宽相同，所有链接都是到目的地的最短路径的一部分）。这里的目标是在不知道未来数据包的情况下，以一种方式分配每个传入的数据包到一个链接，使得每个链接的负载平衡。不能超载任何链接。这是一个负载均衡问题。
在这里，路由器中实现的调度程序不知道未来的数据包，但它必须针对每个传入的数据包做出调度决策。相反，离线调度程序完全了解所有传入的数据包，然后有效地将数据包分配到不同的链接，并可以在不同的链接之间实现最优负载平衡。
离线算法：所有输入信息都对算法可用，并由算法同时处理。通过完整的输入信息集，算法找到一种有效处理输入并获得最优解的方法。
在线算法：输入是动态的，即所有输入信息不是同时可用的，而是作为序列或随时间推移的一部分逐步提供。一旦有一个输入可用，算法必须立即做出决策，没有未来输入信息的任何知识。在这个过程中，算法产生一系列决策，这些决策将对其整体性能的最终质量产生影响。
例如：通信网络中的路由： 不同源的数据包到达最近的路由器。有多个通信链接连接到路由器。当一个新的数据包到达路由器时，路由器必须立即决定将数据包发送到哪个链接。（假设所有链接都被路由到目的地，所有链接带宽相同，所有链接都是到目的地的最短路径的一部分）。这里的目标是在不知道未来数据包的情况下，以一种方式分配每个传入的数据包到一个链接，使得每个链接的负载平衡。不能超载任何链接。这是一个负载均衡问题。
在这里，路由器中实现的调度程序不知道未来的数据包，但它必须针对每个传入的数据包做出调度决策。相反，离线调度程序完全了解所有传入的数据包，然后有效地将数据包分配到不同的链接，并可以在不同的链接之间实现最优负载平衡。
- Debasis Dwibedy
1
如果算法在执行之前不知道它将要处理的数据，则称其为在线算法。离线算法可以提前查看所有数据。
- Jainendra
0
缓存未命中问题：在计算机系统中，缓存是一种内存单元，用于避免更快的处理器和较慢的主存之间的速度不匹配。使用缓存的目的是通过将一些经常访问的页面保留在缓存中来最小化平均访问时间。假设这些页面可能会在不久的将来被处理器请求。通常，当处理器发出页面请求时，页面会从主存或辅助存储器中获取，并将页面的副本存储在缓存中。假设缓存已满，则缓存中实施的算法必须立即决定替换缓存块，而无需了解未来的页面请求。问题是：应该替换哪个缓存块？（在最坏的情况下，可能会发生您替换缓存块，紧接着处理器请求替换的缓存块）。
因此，算法必须设计成在没有整个请求序列的先验知识的情况下，在收到传入请求时立即做出决策。这种类型的算法称为在线算法。
- Debasis Dwibedy
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接