一个O(n)的算法在计算时间上是否可能超过O(n^2)?

Question

一个O(n)的算法在计算时间上是否可能超过O(n^2)?

62

假设我有两个算法：

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)，它也会花费更长时间。有人可以详细解释一下吗？我提出这个问题是因为我经常看到算法，例如首先执行排序步骤或类似操作，在确定总体复杂度时，只需找到最复杂的元素来约束算法。

- Brian

5

一个时间复杂度为 O(n) 的算法最多需要 c*n 步才能完成，其中 c 是某个常数。因此，无论你在第一个循环中进行了多少次恒定迭代，你的算法仍然是 O(n)。 - ChronoTrigger

49

你的理解是正确的：大 O 分析并不用于确定绝对的资源使用量，而是用于比较随着输入规模增长时资源使用量的增长速度。 - amon

3

你认为第二个算法为什么需要更长的时间？当n大于100时，第一个算法就需要更长的时间。 - aquinas

2

参见：银河算法 - harold

1

大家都给出了非常好的答案。我知道它本来不应该明确涵盖运行时，但这些答案有助于让这个困境更清晰。@aquinas 你是对的。我发帖后才想到这一点，哈哈。 - Brian

大O符号通常用来讨论当n趋近于无穷大时的极限，或者更现实地说，当n非常大时。在你发布的例子中，如果n是十亿，那么第一个例子将比第二个例子花费更长的时间。如果n非常小，我们通常不太关心大O复杂度，正如你所列举的原因：如果n小于，假设是10，那么其他因素几乎总是会主导算法的运行时间，而不是N^2部分。 - Elliott

6个回答

19

< p> 是的，在运行时间方面，O（n）算法可以超过O（n ^{2 ）算法。当常数因子（我们在大O符号中忽略它）很大时会发生这种情况。例如，在您上面的代码中，O（n）算法将具有较大的常数因子。因此，对于n <10的情况，它将比以O（n ^{2 ）运行的算法表现更差。

这里，n = 100是交叉点。因此，当任务可以在O（n）和O（n ^{2 ）中都执行时，且线性算法的常数因子大于二次算法的常数因子时，我们倾向于选择具有较差运行时间的算法。例如，当对数组进行排序时，即使归并排序或快速排序的渐近速度更快，我们也会转换为插入排序来排序较小的数组。这是因为插入排序具有比合并/快速排序更小的常数因子，将更快运行。}}}

- Nikunj Banka

3

没关系。这是我在stackoverflow上发表的第一个答案，仅花了几分钟就写完了。我想我需要提高打字速度。 - Nikunj Banka

1

很好的回答，但在OP提供的示例中，n = 100不应该是交叉点吗？ - Derek W

2

Big-O只提供了一个大致的想法，并确定了渐近行为。如果差异较小，比如O(n)与O(n log n)，那么常数就更加重要了——一个需要100n纳秒的程序实际上永远不会比一个需要(n ln n)纳秒的程序更快（如果你计算交叉点，那将是未来几百万年）。 - gnasher729

@NikunjBanka 你上面评论中的论点并不完全正确；我认为你忘记了常数因子。O(n) 的意思是“对于某个c，它需要时间cn”；O(nn) 的意思是“对于某个d，它需要时间dnn”。但如果我们只有“O(n)”和“O(nn)”，我们就不知道c和d是多少，也无法解方程“cn < dnn”来求解n。请参见被接受的答案。你的评论似乎假设c=d=1，但OP的非常好的例子分别具有常数因子1（O(n*n)算法）和100（O(n)算法）。 - Søren Debois

1

@SørenDebois，我没有忘记注释。问题已经被编辑了。之前OP使用了10次迭代，现在已经更改为100次。正式答案也相应地进行了编辑，如你在1小时前看到的。我会做出必要的更改。 - Nikunj Banka

显示剩余3条评论

17

大 O(n) 并不适用于比较不同算法的相对速度。它们是用来衡量输入大小增加时运行时间增加的快慢。例如，

O(n) 表示如果 n 增加1000倍，则运行时间大致增加1000倍。
O(n^2) 表示如果 n 增加1000倍，则运行时间将大致增加1000000倍。

因此，当 n 足够大时，任何 O(n) 算法都将击败 O(n^2) 算法。这并不意味着对于固定的 n 就有任何影响。

- hivert

5

简而言之，可以。O的定义基于这样一个事实：如果O(f(x)) < O(g(x))，则对于足够大的x，g(x)运行所需的时间肯定比f(x)多。

例如，已知对于小值来说，插入排序优于归并排序（如果我没记错的话，这应该适用于n小于31的情况）。

- Save

3

是的。O()只表示渐进复杂度。如果线性算法有足够大的线性减速常数（例如，如果循环核心运行时间长10倍），它可能比二次算法更慢。

O()符号仅是一种外推，尽管它非常好用。

- peterh

2

还没有讨论的是，一个给定的算法一旦开始运行可能会非常快，具有很小的常数乘数，但是它有一个巨大的设置时间（无论_n_如何都是恒定的）。对于非常大的_n_，设置时间变得微不足道，但对于小的_n_来说，这可能意味着比具有“较慢”O的算法运行得更慢。 - Phil Perry

3

你唯一得到的保证是——无论常数因素如何——对于足够大的 n，O(n)算法比O(n^2)算法花费更少的操作次数。

举个例子，让我们来计算OP提供的漂亮示例中的操作次数。他的两个算法只有一行不同：

for (int i = 0; i < n; i++) {       (* A, the O(n*n) algorithm. *)

vs.

for (int i = 0; i < 100; i++) {     (* B, the O(n) algorithm. *)

由于其他程序都是相同的，实际运行时间的差异将由这两行代码决定。

对于 n=100，两行代码都会执行 100 次迭代，因此在 n=100 时，A 和 B 的表现完全相同。

对于 n<100（例如 n=10），A 只会执行 10 次迭代，而 B 会执行 100 次。显然 A 更快。

对于 n>100 （例如 n=1000），A 的循环会执行 1000 次迭代，而 B 的循环仍然执行其固定的 100 次迭代。显然 A 更慢。

当然， O(n) 算法更快需要 n 有多大取决于常数因子。如果在 B 中将常数 100 更改为 1000，则截止值也会更改为 1000。

- Søren Debois

对于n<100，且n=10，A如何进行10次迭代？10^2等于100。B不是需要100*10，即1000次吗？ - Hedylove

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

"Asymptotic complexity（即大O和大Theta所代表的内容）完全忽略了涉及到的常数因子-它只是旨在提供输入大小增加时运行时间如何变化的指示。"

"因此，一个Θ(n)算法可能比一个Θ(n²)算法在某些给定的n下需要更长的时间-这将取决于所涉及的算法-对于您的特定示例，这将在n < 100的情况下发生，忽略两者之间优化差异的可能性。"

"对于任何两个给定的算法，分别采用Θ(n)和Θ(n²)时间，你可能会看到以下情况之一："

当 n 很小时，Θ(n) 算法比 Θ(n²) 算法更慢，当 n 增加时，Θ(n) 算法变得更慢（如果 Θ(n) 算法更复杂，即具有更高的常数因子），或者
Θ(n²) 算法总是更慢。

尽管 Θ(n) 算法可能会在某些情况下比 Θ(n²) 算法更慢，然后又比 Θ(n) 算法更快，以此类推，直到 n 变得非常大，从那时起，Θ(n²) 算法将永远更慢，尽管这种情况发生的可能性很小。

稍微更数学化一点：

假设 Θ(n²) 算法需要进行 cn² 次操作，其中 c 是某个常数。

而 Θ(n) 算法需要进行 dn 次操作，其中 d 是某个常数。

这符合正式定义，因为我们可以假设对于大于 0 的 n（即所有 n），运行时间所在的两个函数是相同的。

按照你的例子，如果你说 c = 1 和 d = 100，则当 n = 100 时，Θ(n²) 算法会变慢，此前 Θ(n) 算法会更慢。

_{(由WolframAlpha提供)}.

符号说明：

严格来说，大O表示的只是一个上界，这意味着你可以说一个O(1)算法（或者任何时间复杂度小于O(n²)的算法）也需要O(n²)的时间。因此，我使用了大Theta（Θ）符号，它表示紧密的上下界。更多信息请参见正式定义。

通常情况下，大O符号被非正式地视为或教授为紧密的上下界，因此您可能已经在不知道的情况下使用了大Theta符号。

如果我们只讨论上限（根据 big-O 的正式定义），那么情况将会是“任何情况都可以”——O(n) 和 O(n²) 两者都可能更快，或者它们需要相同数量的时间（渐进地）——通常无法从比较算法的 big-O 中得出特别有意义的结论，我们只能说，对于某个算法的 big-O，该算法的运行时间不会超过那个数量级（渐进地）。请保留 HTML 标签。