当Big-O符号何时失效？

Question

有哪些例子说明大O符号在实践中失败了？

也就是说：什么时候算法A的大O运行时间预测比算法B更快，但实际上运行算法B更快？

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

说明:

尽管一些答案表明，大O符号用于预测算法性能。 也就是说，它是一个缺陷工具：它只涉及渐近性能，并模糊常数因素。它之所以这样做是有原因的：它旨在预测算法性能，而不考虑在哪台计算机上执行算法。

我想知道的是: 这个工具的缺陷何时显现？ 我发现大O符号相当有用，但远非完美。 有哪些陷阱、边缘情况和易错点?

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

(无需证明的实验证据表明，操作均匀随机边权重的二叉堆花费O(1)时间而不是O(log n)时间；这是实验中的一个重要易错点。另一个难以计数的问题是调用DecreaseKey的预期次数)。

[1] 实际上并不是符号而是符号所代表的概念和理论方法来预测算法性能失败了。

关于被接受的答案:

我已经接受了一个答案来突出我所希望得到的答案类型。存在许多同样好的不同答案 :) 我喜欢这个答案的原因是它提供了一个一般规则，可以说明当缓存未命中占据执行时间时，Big-O符号“失败”的情况，这可能也有助于增加理解（在某种意义上，我现在不确定如何最好地表达）。

- Jonas Kölker

---

我不会说大O表示法有缺陷，只是它有局限性。说它有缺陷就好比说小于运算符在浮点数中不能正常工作一样。实际上，小于运算符确切地做了它所说的事情，但许多人对浮点数的理解有误，使得比较运算符似乎无法正常工作。 - Bill the Lizard

您的澄清有误。它不是一个有缺陷的工具，因为那意味着它会给出错误的答案。实际上它并没有。它是一个可以证明正确的工具。问题在于人们滥用它来回答它不能回答的问题。如果你只使用符号表示它能够描述的事物，那么就没有缺陷。一旦你试图使用它来描述实际性能，它会失败，因为它没有所有相关信息。它的作用不是预测算法性能，而是算法可扩展性。当问题规模增大时，算法变得慢了多少？ - jalf

如果你想知道（最坏情况下的）速度，你需要了解大O符号、输入的规模、算法的常数因子以及在实际情况中的实现细节。问题应该是“何时大O符号不足够”，而不是“何时大O符号失效”。随着大O符号复杂度之间的差异减小以及n的减少，你需要更加关注这些其他因素。 - patros

patros: 很好的观点，我可能是指“当Big-O不足够时”。但是再说一遍，难道限制不是工具的失败吗？ ;-)/// jalf: 所以如果算法A的运行时间为O(f(n))，f是O(g(n))，g不是O(f(n))，算法B的运行时间为O(g(n))，我们不应该预测A在n很大时比B快吗？这真的是你想表达的吗？如果不是：我的澄清有什么问题？ - Jonas Kölker

我的问题是你称它为“有缺陷”。;) 我认为这个限制不是工具的失败。我用的键盘不能用来去法国旅行，这是键盘的限制吗？显然不是，因为它并不是为此而设计的。如果我想去法国旅行，我会买机票，而不是键盘。我认为这正是符号表示法有用的原因：因为它将不同的性能相关问题分开。它不告诉你程序的性能如何，而是告诉你算法一个方面的确切属性。 - jalf

Answer 1

只有一种情况会导致它失败：当人们试图将其用于其不适用的功能时。

它告诉您算法的扩展性，而不能告诉您它有多快。

大O表示法不能告诉您哪个算法在任何特定情况下会更快。它只告诉您对于足够大的输入，其中一个算法将比另一个更快。

- jalf

---

没错。其他人提到了常数因子，但忽略了大O符号最终是可伸缩性的衡量标准。 - patros

没错。大O符号并不会失败。是人们没有理解和正确应用它。 - Bill the Lizard

我不同意关于“它的用途是什么”的说法。虽然Big-O可以衡量可扩展性，但人们对他们的软件的问题不是“这有多可扩展”，而是“这有多快”。Big-O以及您对各种操作速度和数据结构的了解，可以帮助您估计其速度以及如何使其更快。 - mqp

如果你想知道在特定情况下算法A是否比B更快，那么大O符号并不能帮助你。你需要测试和基准测试你的实现。大O符号只是告诉你随着问题规模的增加它们各自的行为方式。如果人们的问题是“这有多快”，那么他们不应该寻求大O符号来回答。 - jalf

基准测试和分析器是很好的工具，但拥有一些思维工具来推理代码并估计如何改进它也是很好的。算法的大O阶是一种简洁的表达方式，用于表达算法的结构特征，在许多情况下对性能有很大影响，是进行这些估计的重要思维工具。虽然它不能告诉你“速度有多快”，但这样说感觉有点吹毛求疵。 - mqp

Answer 2

当N比较小时，常数因素起主导作用。在包含五个元素的数组中查找一个项可能比在哈希表中查找更快。

- mqp

Answer 3

简短回答：当 n 很小的时候。当你只有三个目的地时，旅行商问题很快就能得到解决（虽然在一个由一万亿元素组成的列表中查找最小数可能需要一段时间，但这是 O(n) 的）。

- balpha

Answer 4

典型的例子是快速排序，其最坏时间复杂度为O(n^2)，而堆排序则为O(n logn)。但实际上，快速排序通常比堆排序更快，为什么呢？有两个原因：

• 快速排序中的每次迭代要比堆排序简单得多。此外，它可以通过简单的缓存策略进行优化。

• 很难达到最坏情况。

但在我看来，这并不意味着“大O符号失效”。第一个因素（迭代时间）很容易纳入你的估算中。毕竟，大O数字应该乘以这个几乎恒定的因素。

如果你获取平摊数据，第二个因素就会消失。虽然估算可能更加困难，但它可以讲述一个更完整的故事。

- Javier

---

注意：快速排序的预期时间复杂度为O(n log n)。使用“预期”是因为分区算法中存在随机性。您还可以在O(n)时间内确定性地围绕中位数进行分区，以获得最坏情况下O(n log n)的快速排序边界。 - Jonas Kölker

Answer 5

Big O并不包括内存访问模式。它只计算需要执行的操作次数，无法跟踪算法是否导致缓存未命中或需要从磁盘换页的数据。对于小的N，这些效果通常会占主导地位。例如，在100个整数的数组中进行线性搜索可能会击败100个整数的二叉树搜索，因为由于内存访问，二叉树很可能需要更少的操作。每个树节点都将导致一次缓存未命中，而线性搜索大多数情况下会在缓存中命中每次查找。

- Michael

---

最差情况下只是一个常数因子，而且仅适用于较小的n（尽管可能比情况下要大）。 - David Thornley

@David，问题是：大O符号在何时无法预测性能。 - cgp

是的。一般的答案是“当 n 足够小时”。像内存访问模式和账本记录之类的因素只会影响被视为“足够小”的 n 的大小。 - David Thornley

@David - 我在我的回答中已经提到了这一点，“对于小的 N，这些影响通常会占主导地位。”我想给出一个具体的例子，因为已经有几个答案讨论了大 O 只估算函数执行时间增长的情况。 - Michael

实际上，大O符号也用于硬盘访问。通常它用于指定计算步骤，但是有一个专门研究减少磁盘访问量的领域。在那里，他们使用大O符号来表示磁盘访问的数量。这是一个相关课程的例子：http://www.win.tue.nl/~hermanh/teaching/2IL35/。 - Matthijs Wessels

Answer 6

1. 大多数算法都有“平均情况”和“最坏情况”。如果您的数据通常处于“最坏情况”，则可能会发现另一个算法在实际应用中更有效，尽管在平均情况下理论上不如原来的算法高效。

2. 有些算法也有最佳情况，可以利用您的数据。例如，某些排序算法的理论效率很差，但如果数据已经排序（或接近排序），它们实际上非常快。另一个算法在一般情况下理论上更快，但可能无法利用数据已经排序这一事实，在实践中表现更差。

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

- Eric Petroelje

---

请注意，在情况＃2中，如果您更精确地指定问题（“对大部分排序列表进行排序”），则Big-O会给出正确的答案。 - Captain Segfault

@Segfault - 非常正确，但更重要的是算法在性能上有“极端”情况，既有好的极端情况，也有坏的极端情况。因此，典型情况下的大O并不总是能完全说明问题。了解你的数据和可用算法的边缘情况有时可以帮助你选择与典型情况下最优算法不同的算法。 - Eric Petroelje

Answer 7

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

查看这个问题的答案，可以得到关于Big-O的很好的定义。

- CoderDennis

Answer 8

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

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

- othercriteria

Answer 9

大O表示法并不意味着算法A比算法B运行得更快。它可以表示算法A使用的时间或空间与算法B在输入增长时以不同的速率增长。然而，对于任何特定的输入大小，大O符号并不会说明一个算法相对于另一个算法的性能。

例如，A可能每个操作都比B慢，但其大O值更好。B对于较小的输入更具性能优势，但如果数据大小增加，将存在某个截止点，此时A变得更快。大O本身并不说明这个截止点在哪里。

- JacquesB

Answer 10

一般来说，大O表示法能够隐藏常数因子，使得算法看起来更加高效。正如问题中提到的，使用斐波那契堆就是一个例子。斐波那契堆确实具有很好的渐进运行时间，但在实践中，常数因子太大，不能用于实际数据集合的大小。

斐波那契堆经常用于证明与图相关算法的渐进复杂度的下限。

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

- Adam Rosenfield