一尘不染

Big-O表示法何时会失败?

algorithm

在实践中,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。


阅读 197

收藏
2020-07-28

共1个答案

一尘不染

Big O失败的一个方面是内存访问模式。Big O仅计算需要执行的操作-
它无法跟踪算法是否导致更多的缓存未命中或需要从磁盘分页的数据。对于小氮,这些效应通常占主导地位。例如,由于内存访问,通过100个整数的数组进行线性搜索可能会击败通过100个整数的二叉树进行的搜索,即使二叉树很可能需要较少的操作。每个树节点将导致高速缓存未命中,而线性搜索通常会为每次查找命中高速缓存。

2020-07-28