O(n)时间复杂度的算法是否总是比O(n^2)时间复杂度的算法更快？

Question

这个问题出现在我的算法课上。这是我的想法：

我认为答案是否定的，时间复杂度为O(n)的算法不总是比时间复杂度为O(n²)的算法更快。

例如，假设我们有总时间函数S(n) = 99999999n和T(n) = n²。显然，S(n) = O(n)且T(n) = O(n²)，但对于所有n < 99999999，T(n)比S(n)更快。

这种推理是否有效？我稍微怀疑一下，因为尽管这是一个反例，但它可能是一个反对错误想法的反例。

非常感谢！

- Decaf-Math

---

你的分析是正确的，我非常确定那是这个问题的正确答案。 - Edward Peters

这是一个关于编程的问题，可能与此相关：https://dev59.com/iFsX5IYBdhLWcg3wJMrb - Salvador Dali

Answer 1

Big-O符号并不描述算法在任何给定输入下的速度，而是描述随着元素数量增加时所需时间的增长。如果您的算法在恒定时间内执行，但该时间为1000亿年，则对于大范围的输入，它肯定比许多线性、二次甚至指数级别的算法慢得多。

但这可能不是问题真正想问的。问题是询问具有最坏情况复杂度O（N）的算法A1是否总是比具有最坏情况复杂度O（N ^ 2）的算法A2更快；通过“更快”，它可能是指复杂度本身。在这种情况下，您只需要一个反例，例如：

- A1的正常复杂度为O(log n)，但最坏情况复杂度为O（n ^ 2）。 - A2的正常复杂度为O（n），最坏情况复杂度为O（n）。

在这个例子中，即使A1具有更大的最坏情况复杂度，它通常也比A2更快（即扩展性更好）。

- Asik

---

这个回答中的项目符号中A1和A2是否被错误地交换了？- 问这个问题是因为最坏情况的复杂度与答案主体中的不同。 - RukshanJS

Answer 2

你在谈论最坏情况的复杂度，对于一些算法来说，在实际应用中最坏情况永远不会发生。 说一个算法比另一个运行得更快意味着它为所有输入数据和所有输入大小都运行得更快。所以你的问题的答案显然是否定的，因为最坏情况时间复杂度不是运行时间的准确度量，而是最坏情况下操作数量的增长顺序。 在实践中，运行时间取决于实现，并且不仅仅是关于这个操作数的数量。例如，人们必须关心分配的内存、缓存效率、空间/时间局部性。显然，最重要的事情之一就是输入数据。 如果您想要看到一个算法在具有更高的最坏情况复杂度时比另一个算法运行得更快的例子，请查看所有排序算法及其根据输入的运行时间。

- T. Claverie

Answer 3

由于问题中提到了“始终”，这意味着只需找到一个反例即可证明答案是否定的。

以O(n^2)和O(n logn)为例，但同样适用于O(n^2)和O(n)

一个简单的例子可以是冒泡排序，您可以不断比较成对的元素，直到数组排序完成。冒泡排序的时间复杂度为O(n^2)。 如果您在已排序的数组上使用冒泡排序，则比使用其他时间复杂度为O(nlogn)的算法更快。

- CMPS

Answer 4

你说的每一个方面都是正确的，你提供了一种反例来证明这个陈述的错误。如果这是考试的话，那么它应该会给你满分。

然而，为了更好地理解大O符号和复杂性问题，我将在下面分享我的推理过程。我还建议你在困惑时始终想象以下图表，特别是O(n)和O(n^2)线：

---

大O符号

我自己的理解在我第一次学习计算复杂度时是这样的：

大O符号表示对于足够大的输入大小，"足够大"取决于具体的公式（使用图形，当比较O（n）和O（n ^ 2）线时，n = 20），高阶算法将始终比低阶算法慢。

这意味着，对于小输入，不能保证高阶复杂度算法运行速度比低阶算法快。

但是，大O符号提供了一个信息：当输入大小不断增加，持续增加......直到达到"足够"大小后，高阶复杂度算法将始终比低阶算法慢。而这样的"足够"大小是保证存在的*。

---

最坏时间复杂度

尽管大O符号提供了算法运行时间的上限，但它取决于输入的结构和算法的实现，通常会有最好、平均和最坏的复杂度。

著名的例子是排序算法：快速排序与归并排序！

快速排序的最坏情况为O(n^2)

归并排序的最坏情况为O(n lg n)

然而，快速排序基本上总是比归并排序更快！

因此，如果您的问题涉及最坏情况复杂度，快速排序和归并排序可能是我能想到的最好的反例（因为它们都很常见且著名）。

---

因此，无论是从输入大小、输入结构还是算法实现的角度来看，结合这两个部分的答案都是否定的。

- shole