相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

Big-O表示法[1]在实践中失败的一些例子是什么？

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

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

澄清:

不管有些答案的说法,大O符号是指预测算法的性能.也就是说,这是一个有缺陷的工具:它只谈论渐近性能,并且模糊了常数因素.这样做有一个原因:它意味着预测算法性能,而不依赖于您执行算法的计算机.

我想知道的是:这个工具的缺陷什么时候显示出来？我发现Big-O符号非常有用,但远非完美.有什么陷阱,边缘情况,陷阱？

我正在寻找的一个例子:使用Fibonacci堆而不是二进制堆运行Dijkstra的最短路径算法,得到O(m + n log n)时间对O((m + n)log n),对于n顶点和m边.你期望迟早会从斐波纳契堆中速度增加,但是在我的实验中说速度增加从未实现过.

(实验证据,没有证明,表明在均匀随机边缘权重上运行的二进制堆花费O(1)时间而不是O(log n)时间;这是实验的一个重要问题.另一个需要计算的婊子是预期的调用DecreaseKey的次数).

[1]真的不是失败的符号,而是符号所代表的概念,以及预测算法性能的理论方法.</抗炫学>

在接受的答案上:

我已经接受了一个答案来强调我希望的那种答案.许多不同的答案同样存在:)我喜欢的答案是,它建议了Big-O表示法"失败"时的一般规则(当缓存未命中占据执行时间时),这也可能增加理解(在某种意义上)我不知道如何最好地表达ATM).