就计算时间而言，O(n)算法是否可以超过O(n ^ 2)? [英] Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

问题描述

假设我有两种算法:

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

这自然是O(n^2).假设我也有:

This is naturally O(n^2). Suppose I also have:

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)，它也会花费更长的时间.有人可以对此进行扩展吗?之所以提出它，是因为我经常看到算法，例如它们将首先执行排序步骤或类似的步骤，并且在确定总复杂度时，它只是限制算法的最复杂元素.

It seems that even though my second algorithm is O(n), it will take longer. Can someone expand on this? I bring it up because I often see algorithms where they will, for example, perform a sorting step first or something like that, and when determining total complexity, its just the most complex element that bounds the algorithm.

推荐答案

渐进复杂性(big-O和big-Theta都表示)完全忽略了所涉及的常量因素-仅用于指示运行情况时间会随着输入的大小变大而改变.

Asymptotic complexity (which is what both big-O and big-Theta represent) completely ignores the constant factors involved - it's only intended to give an indication of how running time will change as the size of the input gets larger.

因此，对于某些给定的n，Θ(n)算法可能比Θ(n2)算法花费更长的时间-具体发生在哪个n取决于所涉及的算法，对于您的特定示例， n < 100就是这种情况，而忽略了两者之间优化的可能性不同.

So it's certainly possible that an Θ(n) algorithm can take longer than an Θ(n2) one for some given n - which n this will happen for will really depend on the algorithms involved - for your specific example, this will be the case for n < 100, ignoring the possibility of optimizations differing between the two.

对于任意两个分别花费Θ(n)和Θ(n2)时间的算法，您可能会看到的是:

For any two given algorithms taking Θ(n) and Θ(n2) time respectively, what you're likely to see is that either:

• 当n较小时，Θ(n)算法变慢，然后随着n增大，Θ(n2)算法变慢
  (如果Θ(n)更复杂，即具有更高的恒定因子，则会发生这种情况)，或者
• Θ(n2)总是慢一些.

• The Θ(n) algorithm is slower when n is small, then the Θ(n2) one becomes slower as n increases
  (which happens if the Θ(n) one is more complex, i.e. has higher constant factors), or
• The Θ(n2) one is always slower.

虽然可能当然很容易，但是Θ(n)算法可能会变慢，然后Θ(n2)一个，然后再Θ(n)一个，依此类推，随着n的增加，直到n变得非常大，从那时起Θ(n2)总是会变慢，尽管极不可能发生.

Although it's certainly possible that the Θ(n) algorithm can be slower, then the Θ(n2) one, then the Θ(n) one again, and so on as n increases, until n gets very large, from which point onwards the Θ(n2) one will always be slower, although it's greatly unlikely to happen.

假设Θ(n2)算法对某些c进行了cn2操作.

Let's say the Θ(n2) algorithm takes cn2 operations for some c.

Θ(n)算法对某些d进行dn操作.

And the Θ(n) algorithm takes dn operations for some d.

这符合正式定义，因为我们可以假定对于n大于0(即对于所有n)成立，并且运行时间所位于的两个函数是相同的.

This is in line with the formal definition since we can assume this holds for n greater than 0 (i.e. for all n) and that the two functions between which the running time is lies is the same.

与您的示例一致，如果您说c = 1和d = 100，则Θ(n)算法将变慢直到n = 100，这时Θ(n2)算法将变慢.

In line with your example, if you were to say c = 1 and d = 100, then the Θ(n) algorithm would be slower until n = 100, at which point the Θ(n2) algorithm would become slower.

_{(由 WolframAlpha )}.

从技术上讲，大-O只是一个上限，这意味着您可以说O(1)算法(或者实际上是任何花费O(n2)或更短时间的算法)也需要O(n2).因此，我改用big-Theta(Θ)表示法，这只是一个严格的界限.有关更多信息，请参见正式定义.

Technically big-O is only an upper bound, meaning you can say an O(1) algorithm (or really any algorithm taking O(n2) or less time) takes O(n2) as well. Thus I instead used big-Theta (Θ) notation, which is just a tight bound. See the formal definitions for more information.

Big-O通常被非正式地视为或被教导为紧密绑定，因此您可能实际上已经在不知不觉中使用big-Theta了.

Big-O is often informally treated as or taught to be a tight bound, so you may already have been essentially using big-Theta without knowing it.

如果我们仅在谈论一个上限(按照big-O的正式定义)，那将是一切".情况-O(n)可能会更快，O(n2)可能会更快，或者它们可能花费相同的时间(渐近)-关于比较通常不能得出特别有意义的结论算法的big-O，只能说，给定某种算法的big-O，该算法所花费的时间不会超过该时间量(渐近地).

If we're talking about an upper bound only (as per the formal definition of big-O), that would rather be an "anything goes" situation - the O(n) one can be faster, the O(n2) one can be faster or they can take the same amount of time (asymptotically) - one usually can't make particularly meaningful conclusions with regard to comparing the big-O of algorithms, one can only say that, given a big-O of some algorithm, that that algorithm won't take any longer than that amount of time (asymptotically).

这篇关于就计算时间而言，O(n)算法是否可以超过O(n ^ 2)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！