3

例如，假设我有一个 O(n) 的算法和一个摊销 O(n) 的算法。公平地说，严格来说，非摊销算法总是比摊销算法快或快吗？或者是否有任何理由更喜欢摊销版本（忽略代码简单性或易于实现之类的东西）？

4

6 回答 6

7
  1. 大 O 表示法只告诉您代码的扩展方式，而不是有限 N 的速度。
  2. 如果您关心最坏情况下的性能或延迟（例如实时或交互式系统），摊销和非摊销之间的区别很重要。但是，如果您只关心平均吞吐量，那么它们在所有实际用途中都是相同的。即使在科学计算和大规模数据挖掘等一些性能非常关键的情况下，摊销分析也足够好。
于 2010-02-22T01:51:24.770 回答
6

或者是否有任何理由更喜欢摊销版本

较小的常数。

于 2010-02-22T01:36:43.453 回答
5

O(n) 算法和摊销 O(n) 算法之间的主要区别在于，您对摊销 O(n) 算法的最坏情况行为一无所知。在实践中，这并不重要：如果你的算法运行了很多次，那么你可以依靠平均定律来平衡一些不好的情况，如果你的算法没有运行很多次，那么你就不太可能遇到最坏的情况。

“摊销”这个词唯一重要的情况是你不能接受出于某种原因偶尔表现不佳的情况。例如，在 GUI 应用程序中，您会很乐意放弃一些平均情况下的性能，以换取当用户坐在那里感到无聊时您永远不会陷入困境和停止响应的保证。在此类应用程序中，您希望确保即使是最坏情况的行为也适用于任何可能导致 GUI 停止响应的代码。

尽管如此，大多数时候，您不必担心摊销 O(n) 与 O(n)，而是可以担心常数因子是什么（正如其他人已经说过的那样）。

于 2010-02-22T02:05:58.367 回答
1

大 O 表示法告诉您算法如何随着输入的增长而变化。它不是分析代码的捷径。

对于程序中的所有 n，一个更好的算法可能是 O(n^2)，因为 O(n) 中有一个更大的常数。

因此，您对算法的选择实际上取决于哪种算法对于您的输入大小更快。我想你的问题的答案是在你的程序中分析这两种算法，然后决定哪个更快。

于 2010-02-22T01:37:39.757 回答
1

需要摊销算法的一个典型例子是 std::vector ，其中 insert 摊销为 O(1)。

使用摊销算法的一些原因：

  • 更有效的平均情况。
  • 更容易实施。
  • 不存在最坏情况保证算法。
于 2010-02-22T01:51:42.270 回答
0

严格来说，大 O 的度量不够精确，因此可以说具有 O(n) 的算法比具有摊销 O(n) 的算法更快。想想看。如果您在复杂性分析中降低保真度，常数因子可能会显着不同，并使摊销版本更快。

此外，摊销的影响往往取决于使用情况。例如，如果您使用的是哈希表，则摊销的影响将在很大程度上取决于您的 get 与 add 操作的比率。因此，如果您添加 1000 个条目，然后进行 10 亿次查找，那么您必须重新散列几次这一事实并没有太大的区别。但是，如果您不断添加条目，则重新散列的成本可能会增加。

这就是摊销与最坏情况不同的原因。Big-O 反映了最坏的情况，而摊销让您说“每个 x 中的一个都会受到打击，并且 x 足够大以至于无关紧要”。此外，如果您考虑像插入哈希表这样的示例，x 会根据某个常数增长。因此，如果您有一个以 100 个桶开始并且每次重新哈希加倍的哈希表，那么重新哈希会渐近地变得越来越远。此外，具有摊销复杂度的算法的绝对最坏情况复杂度取决于先前的调用，而在平均情况等测量中，调用被认为是独立的。

于 2010-02-22T02:48:03.733 回答