algorithm - 越糟越好。有例子吗？

Question

是否有一种广泛使用的算法的时间复杂度比另一种已知算法差，但在所有中它是更好的选择实际情况(更糟复杂性但更好否则)？

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

There are algorithms A and B that have O(N**2) and O(N) time complexity correspondingly, but B has such a big constant that it has no advantages over A for inputs less then a number of atoms in the Universe.

答案中的示例重点:

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

• 中位数算法的朴素中位数 - 最坏情况 O(N**2) vs. 已知 O(N) 算法。

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

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

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

---

相关:

• The Rise of ``Worse is Better'' . (出于这个问题的目的，“越坏越好”短语的使用范围较窄(即算法时间复杂度)比文章中的意义要大)

• Python's Design Philosophy :

  The ABC group strived for perfection. For example, they used tree-based data structure algorithms that were proven to be optimal for asymptotically large collections (but were not so great for small collections).

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

• Coppersmith–Winograd algorithm方阵乘法是一个很好的例子(它是最快的(2008 年)，但不如更差的算法)。 还有其他吗？来自维基百科的文章:“它在实践中没有使用，因为它只为大到现代硬件无法处理的矩阵提供优势(Robinson 2005)。”

Answer 1

quick-sort最坏情况下的时间复杂度为 O(N^2)，但通常认为它优于其他最坏情况下时间复杂度为 O(N log n) 的排序算法。