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

Question

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).

Answer 1

它恰好在一种情况下失败:当人们试图将它用于某些它不适合的东西时.

它告诉你算法如何扩展.它没有告诉你它有多快.

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

Answer 2

当N很小时,常数因子占主导地位.查找五个项目数组中的项目可能比在哈希表中查找项目更快.

Answer 3

简答:当n很小时.当您只有三个目的地时,快速解决旅行商问题(但是,在万亿元素列表中找到最小数字可以持续一段时间,尽管这是O(n).)

Answer 4

规范的例子是Quicksort,它的最短时间是O(n ^ 2),而Heapsort是O(n logn).然而,在实践中,Quicksort通常比Heapsort更快.为什么？两个原因:

• Quicksort中的每次迭代都比Heapsort简单得多.更重要的是,它可以通过简单的缓存策略轻松优化.

• 最坏的情况很难打.

但恕我直言,这并不意味着"大O失败".第一个因素(迭代时间)很容易纳入您的估算.毕竟,大O数应该乘以这个几乎恒定的事实.

如果你得到的是摊销数字而不是平均数,那么第二个因素会消失.他们可能更难估计,但要讲一个更完整的故事

Answer 5

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

Answer 6

Big-O描述了算法的效率/复杂性,而不一定描述了给定代码块的实现的运行时间.这并不意味着Big-O失败了.这只意味着它并不意味着预测运行时间.

查看这个问题的答案,了解Big-O的一个很好的定义.

Answer 7

1. 对于大多数算法,存在"平均情况"和"最坏情况".如果您的数据通常属于"最坏情况"的情况,那么另一种算法可能在理论上在平均情况下效率较低,可能对您的数据更有效.

2. 某些算法也具有您的数据可以利用的最佳情况.例如,一些排序算法具有可怕的理论效率,但如果数据已经排序(或几乎如此),则实际上非常快.另一种算法虽然理论上在一般情况下更快,但可能无法利用数据已经分类并且在实践中表现更差的事实.

3. 对于非常小的数据集,有时由于大的"k"值,具有更好理论效率的算法实际上可能效率较低.

Answer 8

一个例子(我不是专家)是线性编程的单纯形算法在任意输入上具有指数最坏情况复杂性,即使它们在实践中表现良好.一个有趣的解决方案是考虑"平滑的复杂性",它通过查看任意输入的小随机扰动来混合最坏情况和平均情况性能.

Spielman和Teng(2004)能够证明阴影顶点单纯形算法具有多项式平滑复杂度.

Answer 9

Big O 并没有说例如算法 A 运行得比算法 B 快。它可以说当输入增长时，算法 A 使用的时间或空间以与算法 B 不同的速度增长。然而，对于任何特定的输入大小，大 O 符号并没有说明一种算法相对于另一种算法的性能。

例如，A 每次操作可能更慢，但有比 B 更好的 big-O。B 对于较小的输入性能更好，但是如果数据大小增加，将会有一些截止点 A 变得更快。Big-O 本身并没有说明分界点在哪里。

Answer 10

一般的答案是 Big-O 通过隐藏常数因素让你变得非常草率。正如问题中提到的，使用斐波那契堆就是一个例子。Fibonacci Heaps确实有很好的渐近运行时间，但在实践中，常量因子太大而无法用于现实生活中遇到的数据集的大小。

斐波那契堆通常用于证明图相关算法的渐近复杂性的良好下界。

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