49

是否存在一种广泛使用的算法，其时间复杂度比另一种已知算法差，但在所有实际情况下它都是更好的选择（复杂度更差，但其他情况更好）？

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

有一些算法具有相应的时间复杂度，但是A具有如此大的常数，以至于对于少于宇宙中原子数量的输入 ，它没有任何优势。BO(N**2)O(N)BA

答案中的示例突出显示：

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

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

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

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

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

有关的：

  • “越差越好”的兴起。（为了这个问题的目的，“Worse is Better”短语的使用范围比文章中的更窄（即算法时间复杂度））

  • Python的设计理念：

    ABC集团力求完美。例如，他们使用了基于树的数据结构算法，这些算法已被证明对于渐近大型集合是最佳的（但对于小型集合来说并不是那么好）。

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

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

4

24 回答 24

35

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

于 2009-01-23T01:45:21.883 回答
29

单纯形是一种在最坏情况下具有指数时间复杂度的算法，但对于任何实际情况，它都是多项式的。可能存在用于线性规划的多项式算法，但它们非常复杂并且通常具有很大的常数。

于 2009-01-23T01:49:20.083 回答
15

蒙特卡洛积分是一种计算定积分的概率方法，不能保证返回正确答案。然而，在现实世界的情况下，它返回准确答案的速度远远快于可证明正确的方法。

于 2009-01-23T18:14:35.787 回答
14

“越差越好”也可以在语言中看到，例如 Perl、Python、Ruby、Php 甚至 C# 或 Java 背后的想法，或者任何不是汇编程序或 C 的语言（C++ 可能适合这里或不适合这里）。

基本上总有一个“完美”的解决方案，但很多时候最好使用“更差”的工具/算法/语言来更快地获得结果，并且减少痛苦。这就是人们使用这些高级语言的原因，尽管从理想的计算机语言的角度来看它们“更糟糕”，而是更面向人。

于 2009-01-23T02:09:36.237 回答
13

Coppersmith–Winograd 算法用于方阵乘法。它的时间复杂度是 O(n 2.376 ) vs. O(n 3 ) 的朴素乘法算法或vs. O(n 2.807 ) 的Strassen 算法。

来自维基百科文章：

然而，与 Strassen 算法不同的是，它并没有在实践中使用，因为它只为大到现代硬件无法处理的矩阵提供了优势（Robinson 2005）。

于 2009-02-02T12:03:09.950 回答
10

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

排序、图算法和线性代数技术等可以通过承担一些额外的簿记、通信和运行时开销来实现并行化，从而在挂钟时间方面加速。

于 2009-01-23T02:08:55.130 回答
9

通常会选择易于并行化或随机化的算法（如quicksort ）而不是缺乏这些品质的竞争算法。此外，通常情况下，当精确算法会产生指数运行时间时，问题的近似解是可以接受的，例如旅行商问题。

于 2009-01-23T01:50:03.013 回答
8

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

据推测，该集合的大小为 641K。

在 BAE SYSTEMS 的技术计算组工作时，该组负责处理各种飞机的结构和空气动力学代码，我们的代码库至少可以追溯到 25 年前（三分之一的员工在那里工作了那么长时间）。

许多算法针对 16 位大型机的性能进行了优化，而不是针对可扩展性进行了优化。这些优化完全适用于 1970 年代的硬件，但在取代它的 32 位和 64 位系统上的较大数据集上表现不佳。如果您选择的可扩展性较差，但在您当前正在使用的硬件上效果更好，请注意这是一种优化，将来可能不会适用。在编写 1970 年代的例程时，我们在 2000 年代放入其中的数据大小是不切实际的。不幸的是，试图从那些代码中提取一个清晰的算法，然后可以实现以适应现代硬件并不是一件容易的事。

除了使海洋沸腾之外，所谓的“所有实际情况”通常是一个时间相关变量。

于 2009-01-23T13:38:49.340 回答
5

不太符合标准，但是基于回溯的正则表达式与基于 DFA 的正则表达式的 O(N) 相比，具有指数最坏的情况，但几乎总是使用基于回溯的正则表达式而不是基于 DFA 的正则表达式。

编辑：（JFS）

正则表达式匹配可以简单快速（但在 Java、Perl、PHP、Python、Ruby 等中很慢）：

反向引用增加的力量需要付出巨大的代价：在最坏的情况下，最知名的实现需要指数搜索算法。

正则表达式引擎：

这种方法（DFA）确实更高效，甚至可以适应允许捕获和非贪婪匹配，但它也有重要的缺点：

  • 环顾四周是不可能的
  • 反向引用也是不可能的
  • 正则表达式预编译时间更长，占用更多内存

从好的方面来说，除了避免最坏情况下的指数运行时间外，DFA 方法还避免了与输入数据大小呈线性关系的最坏情况下的堆栈使用。

[3]：

于 2009-01-29T04:37:27.640 回答
5

一个例子来自计算几何。由于Chazelle ，多边形三角剖分具有最坏情况 O(N) 算法，但由于实现的难度和巨大的常数，它几乎从未在实践中实现。

于 2010-11-21T20:59:05.500 回答
5

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

于 2011-02-23T16:28:52.897 回答
4

对于固定长度的输入，基数排序的时间复杂度为 O(n)，但尽管渐近运行时间更差，但更常使用快速排序，因为基数排序的每个元素开销通常要高得多。

于 2009-01-23T19:25:08.033 回答
4

好的，考虑解决旅行商问题。唯一完美的解决方案是测试所有可能的路线。然而，随着 N 的增加，我们的硬件和时间限制变得不可能。所以我们想到了很多启发式方法。

这使我们回答了您的问题。对于 NP 完全问题，启发式（更糟）比蛮力更好。这描述了“越差越好”总是正确的情况。

于 2009-01-28T03:07:01.910 回答
4

在计算一组数字的中位数时，可以使用与快速排序非常相似的算法。您围绕一个数字进行分区，所有较大的都到一侧，所有较小的都到另一侧。然后你扔掉一侧并递归计算较大一侧的中位数。这在最坏的情况下需要 O(n^2)，但在平均情况下非常快（O(n)，常数较低）。

您可以获得保证的最坏情况 O(n) 性能，常数约为 40。这称为中位数算法的中位数。在实践中，你永远不会使用它。

于 2009-01-29T02:40:51.777 回答
4

如果我理解这个问题，那么您要求的算法在理论上更好，但在所有情况下实际上都更差。因此，除非出现错误，否则人们不会期望它们实际被使用。

一个可能的例子是通用记忆。从理论上讲，所有可能的输入都应该记住所有确定性函数调用。这样复杂的计算就可以用简单的表格查找代替。对于范围广泛的问题，这种技术有效地用时间换取存储空间。但是假设有一个中央存储库，其中包含所有人类计算机使用的所有可能功能的所有可能输入的结果。第一次有人在任何地方进行计算，那将是最后一次。所有后续尝试都将导致表查找。

但是我可以想到不这样做的几个原因：

  1. 存储所有结果所需的内存空间可能大到不可思议。看起来所需的比特数可能会超过宇宙中的粒子数。（但即使是估计这个数字的任务也很艰巨。）

  2. 很难构建一个有效的算法来记忆那个巨大的问题空间。

  3. 随着客户端数量的增加，与中央存储库通信的成本可能会超过收益。

我相信你可以想到其他问题。

事实上，这种时间/空间权衡在实践中非常普遍。理想情况下，所有数据都将存储在 L1 缓存中，但由于大小限制，您总是需要将一些数据放在磁盘或（可怕的！）磁带上。先进的技术减少了这些权衡的一些痛苦，但正如我上面所说的那样，存在限制。

回应 JF 塞巴斯蒂安的评论：

假设我们考虑使用阶乘存储库而不是通用记忆存储库。它不会保存所有可能输入的结果。相反，它将仅限于从1到的结果N! 现在很容易看出，任何进行阶乘的计算机都将从查找结果而不是进行计算中受益。即使计算(N+1)!查找也将是一个巨大的胜利，因为该计算将减少到N!(N+1).

现在为了让这个“更好”的算法变得更糟，我们可以增加 N 或增加使用存储库的计算机数量。

但我可能不理解这个问题的一些微妙之处。他们按照我的想法，我不断提出可以很好扩展的示例，直到他们没有。

于 2009-01-29T19:47:09.687 回答
3

合并排序与快速排序

快速排序的平均时间复杂度为 O( n log n )。它可以就地对数组进行排序，即 O(1) 的空间复杂度。

归并排序的平均时间复杂度也为 O( n log n )，但它的空间复杂度要差得多：Θ( n )。（链表有一种特殊情况）

由于快速排序的最坏情况时间复杂度是 Θ(n^2)（即所有元素都落在每个枢轴的同一侧），而归并排序的最坏情况是 O( n log n )，归并排序是库的默认选择实施者。

在这种情况下，我认为合并排序的最坏情况时间复杂度的可预测性胜过快速排序低得多的内存需求。

鉴于可以大大降低快速排序时间复杂度最坏情况的可能性（例如通过随机选择枢轴），我认为除了快速排序的病态情况外，合并排序在所有情况下都更糟。

于 2009-01-28T12:33:26.433 回答
2

我一直将“越差越好”这个术语理解为与正确解决方案相关的问题，这些问题非常复杂，其中存在相对更容易理解的近似（或足够好的）解决方案。

这使得设计、生产和维护更容易。

于 2009-01-23T02:19:58.430 回答
2

有一个 O(n) 算法用于从未排序的集合中选择第 k 个最大元素，但很少使用它来代替排序，这当然是 O(n logn)。

于 2009-01-23T08:59:13.430 回答
2

尽管具有 O(n 2 ) 复杂度的插入排序对于小型集合 (n < 10) 来说比任何其他排序算法都更快。那是因为嵌套循环很小并且执行速度很快。许多实现了 sort 方法的库（包括 STL）实际上将它用于小数据子集以加快处理速度。

于 2009-01-29T02:31:01.000 回答
1

蒙特卡洛整合已经被提出，但更具体的例子是金融中的蒙特卡洛定价也是一个建议。这里的方法比其他方法更容易编码，可以做更多的事情，但它比有限差分慢得多。

做 20 维有限差分算法并不实用，但 20 维定价执行很容易设置。

于 2009-01-29T05:02:39.557 回答
1

意大利面条排序比任何其他排序算法都要好，因为它的设置时间为 O(n)，执行时间为 O(1)，提取排序数据的时间为 O(n)。它以 O(n) 的空间复杂度完成了所有这些工作。（总体性能：在时间和空间上都是 O(n)。）然而，由于一些奇怪的（显而易见的）原因，没有人将它用于任何事情，更喜欢远低于 O(nlogn) 算法及其同类。

于 2010-05-31T05:03:37.397 回答
1

  1. Y-fast-trie 对于后继/前任有复杂的 loglogu 时间，但它具有相对较大的常数，因此 BST（即 logn）可能更好，这是因为 log(n) 在任何实际使用中都非常小，所以常数很重要最多。

  2. 融合树的查询复杂度为 O(logn/loglogu)，但常量非常大，BST 可以在 logn 中实现相同的结果，这再次更好（loglogu 也非常小，因此 O(logn/loglogu)=O(logn) 对于任何实际原因）。

  3. 确定性中值算法非常慢，即使它是 O(n)，所以使用排序 (nlogn) 或概率版本（理论上可能需要 O(n!) 但很有可能需要 O(n) 和概率它需要 T*O(n) 随 T 呈指数下降，并且 n) 要好得多。

于 2019-09-13T20:20:23.083 回答
0

迭代深化

与使用alpha-beta 修剪增强的普通深度优先搜索相比，与较差（或不存在）的分支排序启发式结合使用的迭代加深搜索将导致扫描更多节点。然而，当使用良好的分支排序启发式时，由于 alpha-beta 修剪的增强效果，树的很大一部分被消除了。与时间或空间复杂性无关的第二个优势是，对问题域的解决方案的猜测是早期建立的，并且随着搜索的进行，猜测会得到细化。正是这第二个优势使它在许多问题领域如此具有吸引力。

于 2010-05-31T04:16:13.313 回答
0 
Quick-sort has worst case time complexity of O(N^2)! 
It is considered better than other sorting algorithms 
like mergesort heapsort etc. which have O(N log n) time complexity 
in the worst case.
The reason may be the 
1.in place sorting 
2.stability, 
3.very less amount of code involved.
于 2013-07-12T17:17:28.460 回答