algorithm - Big-O 表示法什么时候失效？

Question

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

也就是说:算法的 Big-O 运行时间何时会预测算法 A 比算法 B 快，但实际上算法 B 在您运行时更快？

范围更广:关于算法性能的理论预测何时会与观察到的运行时间不匹配？非 Big-O 预测可能基于搜索树中的平均/预期旋转次数，或排序算法中的比较次数，表示为乘以元素数量的因子。

澄清:

尽管有些答案怎么说，Big-O 表示法是用于预测算法性能的。也就是说，这是一个有缺陷的工具:它只谈论渐近性能，并且模糊了常数因子。它这样做是有原因的:它旨在独立于您在哪台计算机上执行算法来预测算法性能。

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

我正在寻找的示例:使用 Fibonacci 堆而不是二进制堆运行 Dijkstra 的最短路径算法，您得到 O(m + n log n) 时间与 O((m+n) log n) ，对于 n 个顶点和 m 个边。您会期望 Fibonacci 堆的速度迟早会提高，但在我的实验中从未实现过这种速度提高。

(没有证据的实验证据表明，在均匀随机边权重上运行的二叉堆花费 O(1) 时间而不是 O(log n) 时间；这是实验的一个大陷阱。另一个是婊子数是对 DecreaseKey 的预期调用次数。

[1] 事实上，失败的不是符号，而是符号所代表的概念，以及预测算法性能的理论方法。

关于接受的答案:

我接受了一个答案，以突出显示我希望得到的答案类型。许多不同的答案都一样好:)我喜欢这个答案的原因是它提出了一个关于大 O 符号何时“失败”(当缓存未命中主导执行时间)的一般规则，这也可能增加理解(在某种意义上我不确定如何最好地表达 ATM)。

Answer 1

恰恰在一种情况下它会失败:当人们试图将它用于不适合它的用途时。

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

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