在实践中，Big-O标记[1]失败的例子有哪些？

就是说：算法的Big-O运行时间何时会预测算法A快于算法B，而实际上，算法B在运行时更快？

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

澄清 ：

尽管有一些答案，Big-O表示法 还是 可以预测算法性能。就是说，这是一个 有缺陷的
工具：它仅谈到渐近性能，并且模糊了恒定因素。这样做是有原因的：它旨在预测算法性能，而与在哪台计算机上执行算法无关。

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

我正在寻找的示例：使用斐波那契堆而不是二进制堆运行Dijkstra的最短路径算法，对于n，您得到O（m + n log n）时间与O（（m + n）log
n）顶点和m边。您可能希望早晚从Fibonacci堆中获得速度的提高，但是在我的实验中却从未实现过速度的提高。

（没有证据的实验证据表明，以统一的随机边缘权重进行操作的二进制堆花费的时间为O（1）而不是O（log
n）；这是实验的一大难题。另一个值得期待的难题是调用DecreaseKey的次数）。

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

在接受的答案上 ：

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