问题描述
有没有一种广泛使用的算法的时间复杂度的糟糕的比另一种已知的算法，但它是一个的好的选择中的所有的实际情况中（ 糟糕的复杂性，但好，否则的）？
Is there a widely-used algorithm that has time complexity worse than that of another known algorithm but it is a better choice in all practical situations (worse complexity but better otherwise)?
这是可以接受的答案可能是这样的形式：
An acceptable answer might be in a form:
有算法 A 和 B 的 有 O（N ** 2）和 O（N）时间 复杂性相应地，但 B 有这么大的常数，它没有 在 A 优势投入少 然后若干个原子的的 宇宙。
这是答案的示例亮点：
-
单纯形法 - 最坏的情况是指数时间。 - VS 的著名的凸优化问题多项式算法
Simplex algorithm -- worst-case is exponential time -- vs. known polynomial-time algorithms for convex optimization problems.
的中位数算法，一个天真的中位数 - 。最坏的情况O（N ** 2）的 VS 的称为O（N）算法
A naive median of medians algorithm -- worst-case O(N**2) vs. known O(N) algorithm.
回溯正则表达式引擎 - 最坏情况下指数的 VS 的O（N）汤普森NFA为基础的引擎。
Backtracking regex engines -- worst-case exponential vs. O(N) Thompson NFA -based engines.
所有这些例子利用最坏情况与平均水平的情况。
All these examples exploit worst-case vs. average scenarios.
相关报道：
- 的`
-
崛起'更糟糕的是更好的'。 （关于这个问题的目的，更糟糕的是更好这句话用在窄的（即 - 算法的时间复杂度）感觉比文）
The Rise of ``Worse is Better''. (For the purpose of this question the "Worse is Better" phrase is used in a narrower (namely -- algorithmic time-complexity) sense than in the article)
该ABC组争取完美。 例如，他们使用基于树的数据 被证明是结构算法 是最佳的渐近大 集合（但没有那么大的 小集合）。
这个例子是答案，如果没有计算机能够存储这些大集合（即大是不是在这种情况下，足够大）。
This example would be the answer if there were no computers capable of storing these large collections (in other words large is not large enough in this case).
铜匠，威诺格拉德算法的方形矩阵乘法就是一个很好的例子（这是最快的（ 2008年），但它不如更糟算法）。 任何其他方面？从维基百科文章：这不是在实际使用，因为它仅提供了一个优点为矩阵很大，以致它们不能被通过现代硬件处理（罗宾逊2005）。
Coppersmith–Winograd algorithm for square matrix multiplication is a good example (it is the fastest (2008) but it is inferior to worse algorithms). Any others?From the wikipedia article: "It is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware (Robinson 2005)."
推荐答案
铜匠，威诺格拉德算法以方阵乘法。它的时间复杂度为O（n ）的 VS 的为O（n ）一个天真乘算法或 VS的。为O（n ）为 Strassen的算法。
Coppersmith–Winograd algorithm for square matrix multiplication. Its time complexity is O(n) vs. O(n) of a naive multiplication algorithm or vs. O(n) for Strassen algorithm.
从维基百科的文章：
然而，与Strassen的 算法，它不会在实践中使用 因为它仅提供了一个优点 对于矩阵如此之大，他们不能 现代的硬件处理 （罗宾逊2005年）。
这篇关于更糟糕的是更好的。有一个例子吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！