25

有哪些 Big-O 表示法 [1] 在实践中失败的例子？

也就是说：算法的 Big-O 运行时间什么时候会预测算法 A 比算法 B 快，而实际运行时算法 B 会更快？

稍微宽泛一点：关于算法性能的理论预测何时与观察到的运行时间不匹配？非大 O 预测可能基于搜索树中的平均/预期旋转次数，或排序算法中的比较次数，表示为因子乘以元素数量。

澄清：

尽管有些答案说了什么，但 Big-O 表示法旨在预测算法性能。也就是说，它是一个有缺陷的工具：它只谈论渐近性能，它模糊了常数因素。它这样做是有原因的：它旨在预测算法性能，而与您在哪台计算机上执行算法无关。

我想知道的是：这个工具的缺陷什么时候表现出来？我发现 Big-O 表示法相当有用，但远非完美。有哪些陷阱、边缘情况和陷阱？

我正在寻找的一个例子：使用斐波那契堆而不是二进制堆运行 Dijkstra 的最短路径算法，你得到 O(m + n log n) 时间与 O((m+n) log n)，对于 n顶点和 m 条边。您预计斐波那契堆迟早会提高速度，但在我的实验中从未实现过速度提高。

（没有证据的实验证据表明，在均匀随机边权重上运行的二进制堆花费 O(1) 时间而不是 O(log n) 时间；这是实验的一个大问题。另一个难以计数的问题是预期的调用 DecreaseKey 的次数）。

[1] 实际上，失败的不是符号，而是符号所代表的概念，以及预测算法性能的理论方法。</反迂腐>

关于接受的答案：

我已经接受了一个答案，以突出我希望得到的答案。存在许多同样好的答案:) 我喜欢这个答案的地方在于，它提出了一个通用规则，用于何时 Big-O 表示法“失败”（当缓存未命中主导执行时间时），这也可能增加理解（在某种意义上我不确定如何最好地表达 ATM）。

4

18 回答 18

105

它仅在一种情况下失败：当人们试图将它用于它不适合的东西时。

它告诉您算法如何扩展。它不会告诉你它有多快。

Big-O 符号不会告诉您在任何特定情况下哪种算法会更快。它只告诉你，对于足够大的输入，一个会比另一个快。

于 2009-06-02T19:06:07.447 回答
27

当 N 较小时，常数因子占主导地位。在包含五个项目的数组中查找一个项目可能比在哈希表中查找更快。

于 2009-06-02T19:02:54.007 回答
17

简短的回答：当 n 小时。当您只有三个目的地时，旅行商问题很快就会得到解决（但是，在万亿元素的列表中找到最小的数字可能会持续一段时间，尽管这是 O(n)。）

于 2009-06-02T19:03:21.463 回答
14

典型的例子是快速排序，它的最坏时间是 O(n^2)，而堆排序是 O(n logn)。然而在实践中，快速排序通常比堆排序更快。为什么？两个原因：

  • Quicksort 中的每次迭代都比 Heapsort 简单得多。更重要的是，它很容易通过简单的缓存策略进行优化。

  • 最坏的情况很难命中。

但是恕我直言，这并不意味着“大 O 失败”。第一个因素（迭代时间）很容易纳入您的估计中。毕竟，大 O 数应该乘以这个几乎恒定的因子。

如果你得到摊销数字而不是平均值，第二个因素就会消失。它们可能更难估计，但讲述了一个更完整的故事

于 2009-06-02T19:04:11.927 回答
11

Big O 失败的一个领域是内存访问模式。Big O 只计算需要执行的操作——如果算法导致更多的缓存未命中或需要从磁盘调入的数据，它无法跟踪。对于小的 N，这些影响通常会占主导地位。例如，由于内存访问，通过 100 个整数的数组进行线性搜索可能会击败通过 100 个整数的二叉树进行的搜索，尽管二叉树很可能需要更少的操作。每个树节点都会导致缓存未命中，而线性搜索大部分会在每次查找时命中缓存。

于 2009-06-02T19:06:50.473 回答
9

  1. 对于大多数算法，都有“平均情况”和“最坏情况”。如果您的数据经常落入“最坏情况”的场景，那么另一种算法（虽然理论上在平均情况下效率较低）可能会证明对您的数据更有效。

  2. 一些算法还具有您的数据可以利用的最佳情况。例如，一些排序算法的理论效率很差，但如果数据已经排序（或接近排序），实际上速度非常快。另一种算法虽然在一般情况下理论上更快，但可能无法利用数据已经排序并且实际上性能更差的事实。

  3. 对于非常小的数据集，有时具有更好理论效率的算法实际上可能由于“k”值较大而效率较低。

于 2009-06-02T19:03:39.137 回答
9

Big-O 描述了算法的效率/复杂性，而不一定是给定代码块的实现的运行时间。这并不意味着 Big-O 失败了。这只是意味着它并不意味着预测运行时间。

查看这个问题的答案以获得 Big-O 的一个很好的定义。

于 2009-06-02T19:07:08.833 回答
7

一个例子（我不是专家）是线性规划的单纯形算法在任意输入上具有指数最坏情况复杂性，即使它们在实践中表现良好。一个有趣的解决方案是考虑“平滑复杂度”，它通过查看任意输入的小随机扰动来混合最坏情况和平均情况的性能。

Spielman 和 Teng (2004)能够证明阴影顶点单纯形算法具有多项式平滑复杂度。

于 2009-06-02T19:07:36.367 回答
5

大 O 并没有说算法 A 比算法 B 运行得更快。它可以说当输入增长时，算法 A 使用的时间或空间以不同于算法 B 的速度增长。然而，对于任何特定的输入大小，大 O 表示法并没有说明一种算法相对于另一种算法的性能。

例如，A 每次操作可能较慢，但具有比 B 更好的 big-O。B 对于较小的输入具有更高的性能，但如果数据大小增加，将会有一些截止点 A 变得更快。Big-O 本身并没有说明截止点在哪里。

于 2009-06-02T19:58:02.367 回答
5

一般的答案是，Big-O 通过隐藏常数因素让你变得非常草率。如问题中所述，斐波那契堆的使用就是一个例子。斐波那契堆确实有很好的渐近运行时间，但在实践中，常数因子太大而对现实生活中遇到的数据集的大小没有用处。

斐波那契堆通常用于证明图相关算法的渐近复杂度的良好下界。

另一个类似的例子是用于矩阵乘法的Coppersmith-Winograd 算法。它是目前已知最快的矩阵乘法渐近运行时间 O(n 2.376 ) 的算法。然而，它的常数因子太大而无法在实践中使用。像斐波那契堆一样，它经常被用作其他算法的构建块来证明理论上的时间界限。

于 2009-06-02T20:17:40.000 回答
4

这在一定程度上取决于 Big-O 正在测量的内容 - 在最坏的情况下，它通常会“失败”，因为运行时性能会比 Big-O 建议的要好得多。如果是平均情况，那么情况可能会更糟。

如果算法的输入数据有一些先验信息，Big-O 表示法通常会“失败”。通常，Big-O 表示法指的是最坏情况的复杂性——如果数据是完全随机的或完全非随机的，这通常会发生。

例如，如果您将数据提供给经过分析的算法，并且 big-o 基于随机数据，但您的数据具有非常明确的结构，那么您的结果时间可能比预期的要快得多。同样，如果您测量的是平均复杂度，并且您提供的数据非常随机化，那么该算法的性能可能比预期的要差得多。

于 2009-06-02T19:01:47.377 回答
4
  1. 小 N - 对于今天的计算机，100 可能太小而无需担心。
  2. 隐藏乘数 - IE 合并与快速排序。
  3. 病理病例 - 再次，合并与快速
于 2009-06-02T19:21:29.740 回答
3

Big-Oh 表示法失败的一个广泛领域是当数据量超过可用 RAM 量时。

以排序为例，排序所花费的时间不受比较或交换次数的支配（在最佳情况下，比较或交换的次数分别为 O(n log n) 和 O(n)）。时间量取决于磁盘操作的数量：块写入和块读取。

为了更好地分析处理超出可用 RAM 的数据的算法，I/O 模型诞生了，您可以在其中计算磁盘读取次数。在那里，您考虑三个参数：

  • 元素个数，N；
  • 内存量（RAM），M（可以在内存中的元素数量）；和
  • 磁盘块的大小，B（每个块的元素数）。

值得注意的是磁盘空间量；这被视为无限。一个典型的额外假设是 M > B 2。

继续排序示例，您通常倾向于在 I/O 情况下进行合并排序：将元素分成大小为 θ(M) 的块并在内存中对它们进行排序（例如使用快速排序）。然后，通过将每个块中的第一个块读取到内存中来合并它们中的 θ(M/B)，将所有元素填充到一个堆中，并重复选择最小的元素，直到你选择了其中的 B 个。写出这个新的合并块并继续。如果您耗尽了读入内存的某个块，请从同一块中读取一个新块并将其放入堆中。

（所有表达式都应该被理解为大 θ）。您形成 N/M 个排序的块，然后合并。你合并N/M次日志（base M/B）；每次读取和写入所有 N/B 块时，都需要 N/B * (log base M/B of N/M) 时间。

您可以分析内存中的排序算法（经过适当修改以包括块读取和块写入）并发现它们比我介绍的合并排序效率低得多。

这些知识来自我的 I/O 算法课程，Arge 和 Brodal ( http://daimi.au.dk/~large/ioS08/ )；我还进行了验证该理论的实验：一旦超出内存，堆排序就会花费“几乎无限”的时间。快速排序变得慢得难以忍受，合并排序慢得让人难以忍受，I/O 效率高的合并排序表现良好（最好的）。

于 2009-06-02T19:38:36.057 回答
2

我见过一些案例，随着数据集的增长，算法复杂性变得不如内存访问模式重要。在某些情况下，使用智能算法导航大型数据结构可能会导致比使用更糟糕的 big-O 的算法更多的页面错误或缓存未命中。

对于较小的 n，两种算法可能具有可比性。随着 n 的增加，更智能的算法会表现得更好。但是，在某些时候，n 增长到足以使系统屈服于内存压力，在这种情况下，“更糟糕”的算法实际上可能会执行得更好，因为常量基本上被重置了。

不过，这并不是特别有趣。当你达到这个反转点时，这两种算法的性能通常都无法接受，你必须找到一种新的算法，它具有更友好的内存访问模式和更好的 big-O 复杂度。

于 2009-06-03T21:15:08.600 回答
1

当您的数据不适合模型时，大 O 表示法仍然有效，但您会看到最佳和最坏情况的重叠。

此外，一些操作针对线性数据访问与随机数据访问进行了调整，因此一种算法虽然在周期方面更胜一筹，但如果调用它的方法从设计中改变，它可能会非常缓慢。同样，如果算法由于访问内存的方式导致页面/缓存未命中，Big-O 不会准确估计运行进程的成本。

显然，正如我忘记的那样，当 N 很小时:)

于 2009-06-02T18:59:39.037 回答
1

这个问题就像在问，“一个人的智商什么时候会在实践中失败？” 很明显，智商高并不意味着你会在生活中取得成功，智商低并不意味着你会灭亡。然而，我们衡量智商作为评估潜力的一种手段，即使它不是绝对的。

在算法中，Big-Oh 符号为您提供算法的 IQ。这并不一定意味着该算法将在您的特定情况下表现最佳，但有一些数学基础表明该算法具有一定的潜力。如果 Big-Oh 表示法足以衡量性能，您会看到更多的它和更少的运行时测试。

将 Big-Oh 视为一个范围，而不是衡量好坏的具体衡量标准。有最好的情况和最坏的情况，以及介于两者之间的大量情况。根据算法在 Big-Oh 范围内的适合程度来选择算法，但不要依赖符号作为衡量性能的绝对标准。

于 2009-06-02T19:09:52.713 回答
1

简短的回答：当你开始使用大量内存时，总是在现代硬件上。教科书假设内存访问是统一的，但现在不再如此。您当然可以对非统一访问模型进行 Big O 分析，但这有点复杂。

小的 n 情况很明显但并不有趣：足够快就是足够快。

在实践中，我在使用 Delphi、Java、C# 和 Smalltalk 中包含几百万个对象的标准集合时遇到了问题。而对于较小的那些，主要因素被证明是哈希函数或比较

于 2009-07-02T15:14:34.453 回答
1

Robert Sedgewick 在他的 Coursera 算法分析课程中谈到了大 O 符号的缺点。他将特别令人震惊的例子称为银河算法，因为虽然它们可能比它们的前辈具有更好的复杂性等级，但它需要天文规模的输入才能在实践中显示出来。

https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf

于 2015-02-02T16:11:02.463 回答