更糟糕的是更好.有一个例子吗？

有没有一种被广泛使用的算法,该算法的时间复杂度更差比其它已知的算法,但它是一个更好的选择,所有的实际情况(更糟糕的复杂性,但更好的,否则)？

可接受的答案可能是以下形式:

有算法A和B具有O(N**2)和O(N)时间复杂性相应,但B 具有这样的大常数,它没有优于A为小于一个数量在宇宙原子的输入.

答案中的示例突出显示:

单纯形算法 - 最坏情况是指数时间 - 与凸优化问题的已知多项式时间算法相比.

中位数算法的中位数 - 最坏情况O(N**2)与已知O(N)算法.

回溯正则表达式引擎 - 最坏情况指数与基于O(N)Thompson NFA的引擎.

所有这些示例都利用了最坏情况和平均情况.

是否存在不依赖于最坏情况与平均情况之间差异的示例？

---

有关:

"更糟糕的是更好"的崛起.(出于这个问题的目的,"更糟的是更好"这个短语用于比文章更窄的(即 - 算法时间复杂度)意义上)

Python的设计理念:

ABC集团力求完美.例如,他们使用基于树的数据结构算法,这些算法被证明是渐近大型集合的最佳选择(但对于小型集合来说并不是那么好).

如果没有能够存储这些大型集合的计算机(换句话说,大型集合在这种情况下不够大),这个例子就是答案.

用于方阵乘法的Coppersmith-Winograd算法是一个很好的例子(它是最快的(2008),但它不如更差的算法).还有其他人？ 来自维基百科的文章:"它并没有在实践中使用,因为它只为矩阵提供了一个优势,使它们无法被现代硬件处理(Robinson 2005)."

shoosh.. 35

快速排序具有O(N ^ 2)的最坏情况时间复杂度,但是通常认为它比在最坏情况下具有O(N log n)时间复杂度的其他排序算法更好.

1> shoosh..：

---

快速排序具有O(N ^ 2)的最坏情况时间复杂度,但是通常认为它比在最坏情况下具有O(N log n)时间复杂度的其他排序算法更好.

---

正如我所说,高概率不影响最坏情况分析.

---

这是一个很好的例子,但具有O(N**2)时间复杂度的天真(未修改)快速排序版本并未得到广泛使用.

---

"如果算法随机均匀地选择枢轴元素,则无论输入的特性如何,它都可以在O(n log n)时间内完成." http://en.wikipedia.org/wiki/Randomized_algorithm#Quicksort

---

因此,非天真的QuickSort是最坏情况的O(n*log(n)).虽然我不知道上面的选择算法是否实际用于实现QuickSort.

---

@JF Sebastian在Java(直到Java 6)中,所有原始数组类型的`Arrays.sort`是使用9的伪调整器实现的"调整快速排序",它仍然具有O(N ^ 2)最坏情况时间复杂度.

---

@JF:C的`qsort()`当然是一个快速排序.它很可能使用3的中值或一些简单的变量来选择一个枢轴,因此易受O(n ^ 2)行为的影响.我怀疑有****语言的任何**实现使用最坏情况线性时间中值选择算法来确定枢轴(从而保证O(nlog n)快速排序),因为此算法的常量是非常高 - 在我记得的渐近分析中大约20.

2> shoosh..：

---

Simplex是一种算法,在最坏的情况下具有指数时间复杂度,但对于任何实际情况,它都是多项式.可能存在用于线性编程的多项式算法,但它们非常复杂并且通常具有大的常数.

---

RSM的一个主要优点是它可以在对问题进行微小更改后进行热启动 - 这正是您在进行整数编程的分支绑定时所需要的.在这些情况下,内点法并不是那么有用.

3> Robert Gould..：

---

"Whis is Better"也可以在语言中看到,例如Perl,Python,Ruby,Php甚至C#或Java背后的思想,或者不是汇编程序或C语言的任何语言(C++可能适合或不适合).

基本上总是有一个"完美"的解决方案,但很多时候使用"更糟糕的"工具/算法/语言来更快地获得结果并且减少痛苦.这就是为什么人们使用这些更高级别的语言,尽管它们从理想的计算机语言角度来看更"糟糕",而是更加以人为本.

---

是的,它与你的问题没有直接关系,但由于标题并没有将问题限制在算法上,我不希望有些新概念的人在以后偶然发现,并认为"更糟更好"只适用算法,当它更一般的想法.

---

从技术上讲,你是对的(这是最好的"正确").*title*不限制范围,但*我的问题的第一句话*.

4> Dour High Ar..：

---

蒙特卡罗积分是一种计算定积分的概率方法,不能保证返回正确的答案.然而,在现实世界的情况下,它比正确的方法更快地返回一个准确的答案.

5> jfs..：

---

用于方阵乘法的Coppersmith-Winograd算法.它的时间复杂度是O(n ^2.376)对比天然乘法算法的O(n ³)或者对于Strassen算法对 O(n ^2.807).

来自维基百科的文章:

但是,与Strassen算法不同,它并没有在实践中使用,因为它只为矩阵提供了一个优势,使得它们无法被现代硬件处理(Robinson 2005).

6> Matt J..：

---

该语句几乎可以应用于任何并行算法.它们在计算的早期阶段没有经过深入研究的原因是,对于单个执行线程(想想单处理器),它们确实比渐近复杂性,小n的常数因子,它们众所周知的顺序对应物慢,或两者.然而,在当前和未来的计算平台的背景下,可以利用少数(思考多核),几百(想想GPU)或几千(想想超级计算机)处理元素的算法将击败顺序版本的裤子在挂钟时间内,即使所有处理器花费的总时间/能量对于并行版本来说要大得多.

排序,图形算法和线性代数技术都可以通过承担一些额外的簿记,通信和运行时开销以及并行化的成本来加速挂钟时间.

7> Dave Ray..：

---

通常,可以选择容易并行化或随机化的算法(如快速排序)而不是缺乏这些质量的竞争算法.此外,通常情况下,当精确算法产生如旅行商问题中的指数运行时,问题的近似解是可接受的.

8> Pete Kirkham..：

---

如果没有能够存储这些大型集合的计算机,那么这个例子就是答案.

据推测,该系列的尺寸为641K.

---

在负责各种飞机的结构和空气动力学代码的BAE SYSTEMS技术计算小组工作时,我们的代码库至少可以追溯到25年(并且有三分之一的员工在那里工作了很长时间).

许多算法针对16位主机的性能进行了优化,而不是针对可扩展性进行了优化.这些优化完全适用于20世纪70年代的硬件,但在替换它的32位和64位系统上的较大数据集上表现不佳.如果您选择的可伸缩性更差的东西在您当前正在处理的硬件上运行得更好,请注意这是一个优化,它可能在将来不适用.在编写那些20世纪70年代的例程时,我们在2000年代投入的数据大小是不切实际的.不幸的是,尝试从这些代码中提取清晰的算法然后可以实现以适应现代硬件并非易事.

如果没有沸腾的海洋,那么"所有实际情况"通常都是一个时间依赖的变量.

9> Ellery Newco..：

---

虽然不是很明显,但基于回溯的正则表达式与基于DFA的正则表达式的O(N)相比具有指数最坏的情况,但是基于回溯的正则表达式几乎总是被使用而不是基于DFA的正则表达式.

编辑:(JFS)

正则表达式匹配可以简单快速(但在Java,Perl,PHP,Python,Ruby等中速度很慢):

反向引用所增加的功率成本很高:在最坏的情况下,最着名的实现需要指数搜索算法.

正则表达式引擎:

这种方法(DFA)确实更有效,甚至可以适应捕获和非贪婪匹配,但它也有一些重要的缺点:

外观是不可能的

反向引用也是不可能的

正则表达式预编译更长,占用更多内存

从好的方面来说,以及避免最坏情况指数运行时间,DFA方法可以避免最坏情况下的堆栈使用,这种使用与输入数据的大小呈线性关系.

[3]:

10> kolistivra..：

---

一个例子来自计算几何.由于Chazelle,多边形三角测量具有最坏情况的O(N)算法,但由于实施的坚韧性和巨大的常数,它几乎从未在实践中实现.

11> Andrew Aylet..：

---

存在用于确定素数的多项式时间算法,但是在实践中,使用指数时间算法或执行足够的概率计算以具有足够的确定性总是更快.