big-o - O(n) 算法的计算时间可以超过 O(n^2) 吗？

Question

假设我有两种算法:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这自然是O(n^2)。假设我还有:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这是O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

看来即使我的第二个算法是O(n)，它也会花费更长的时间。有人可以对此进行扩展吗？我提出它是因为我经常看到算法，例如，它们首先执行排序步骤或类似的操作，并且在确定总复杂度时，它只是限制算法的最复杂元素。

Answer 1

渐近复杂度(big-O 和 big-Theta 所代表的)完全忽略了所涉及的常数因素 - 它只是为了表明随着输入大小变大，运行时间将如何变化。

所以 Θ(n) 肯定有可能算法可能需要比Θ(n<sup>2</sup>)更长的时间给定的一些n - 其中n这种情况的发生实际上取决于所涉及的算法 - 对于您的具体示例， n < 100 就是这种情况，忽略两者之间优化不同的可能性。

对于任何两个给定的算法，取 Θ(n)和Θ(n<sup>2</sup>)分别时间，您可能会看到:

• Θ(n)当 n 时算法较慢很小，那么Θ(n<sup>2</sup>)一个变慢为 n增加
  (如果 Θ(n) 更复杂，即具有更高的常数因子，则会发生这种情况)，或
• Θ(n<sup>2</sup>)人总是比较慢。

尽管 Θ(n) 肯定有可能算法可能会慢一些，那么Θ(n<sup>2</sup>)一，然后 Θ(n)再次，依此类推 n增加，直到 n变得非常大，从那时起 Θ(n<sup>2</sup>)尽管这种情况不太可能发生，但速度总是会慢一些。

用更数学化的术语来说:

假设 Θ(n<sup>2</sup>)算法需要 cn<sup>2</sup>一些操作c .

还有Θ(n)算法需要 dn一些操作d .

这符合 the formal definition因为我们可以假设这适用于 n大于 0(即对于所有 n )，并且运行时间所在的两个函数是相同的。

根据你的例子，如果你说c = 1和d = 100 ，然后 Θ(n)算法会变慢，直到 n = 100 ，此时Θ(n<sup>2</sup>)算法会变得更慢。

_{(由 WolframAlpha 提供)}。

注释:

从技术上讲，big-O 只是一个上限，这意味着您可以说 O(1)算法(或者任何需要 O(n<sup>2</sup>) 或更少时间的算法)需要 O(n<sup>2</sup>)以及。因此，我改为使用 big-Theta (θ) 表示法，这只是一个紧界。请参阅the formal definitions了解更多信息。

Big-O 通常被非正式地视为或教导为紧束缚，因此您可能已经在不知情的情况下本质上使用了 big-Theta。

如果我们仅讨论上限(根据 big-O 的正式定义)，那宁愿是“一切皆有可能”的情况 - O(n)一个可以更快，O(n<sup>2</sup>)一个可以更快，或者可以花费相同的时间(渐近地) - 人们通常无法在比较大O算法时得出特别有意义的结论，只能说，给定某个算法的大O，该算法不会花费比该时间更长的时间(渐近地)。