在计算时间方面,O(n)algorithm能否超过O(n ^ 2)?

假设我有两个algorithm:

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)

看来,即使我的第二个algorithm是O(n) ,这将需要更长的时间。 有人可以扩大这个吗? 我把它提出来是因为我经常看到algorithm在哪里,例如,首先执行sorting步骤或类似的东西,并且在确定总体复杂度时,它是决定algorithm的最复杂的因素。

实际上,big-O只是一个上界,也就是说你可以说O(1)algorithm(或者是任何一个花费O(n 2 )或更less时间的algorithm)也需要O(n 2 ) 。 为此,让我们切换到big-theta(Θ)符号,这只是一个严格的界限。 有关更多信息,请参阅正式定义 。

如果你只知道大O,很可能你(被错误地)教导说大O是一个紧张的束缚。 如果是这样的话,你大概可以假定big-Theta意味着你被教大O的手段。

对于这个答案的其余部分,我会假设你问(或者说)是大的,而不是大的。 如果没有,如前所述,如果谈论大O,那宁愿成为“一切皆有可能”的情况 – O(n)可以更快, O(n 2 )可以更快,或者他们可以相同的时间量(渐近地) – 通常不能对比较大的Oalgorithm做出特别有意义的结论,只能说,给定某个algorithm的大O,那个algorithm不会采取比这个时间长(渐近地)。


渐近复杂性(这是大O和大-Theta所代表的)完全忽略了所涉及的常量因素 – 它只是用来指示随着input大小的变化,运行时间将如何变化。

所以对于某些给定的nΘ(n)algorithm可能需要比Θ(n 2 )更长的时间 – 这将会发生的真的取决于所涉及的algorithm – 对于您的具体示例,这将是对于n < 100 ,忽略了两者之间优化的可能性。

对于分别采用Θ(n)Θ(n 2 )时间的任何两个给定algorithm,您可能会看到的是:

  • n较小时, Θ(n)algorithm较慢,则随着n增加, Θ(n 2 )将变慢
    (如果Θ(n)更复杂,即具有更高的常数因子,则会发生这种情况)
  • Θ(n 2 )总是比较慢。

尽pipeΘ(n)algorithm可能会更慢,然后Θ(n 2 ) ,然后Θ(n)再次增加,直到n变得非常大,从这点开始Θ(n 2 )将始终较慢,尽pipe极不可能发生。


用略微更加math的术语来说:

假设Θ(n 2 )algorithm对某些c采取cn 2操作。

Θ(n)algorithm对某些d进行dn运算。

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

按照你的例子,如果你说c = 1d = 100 ,那么Θ(n)algorithm会比较慢,直到n = 100 ,这时Θ(n 2 )algorithm会变慢。

(由WolframAlpha提供 )

是的 ,O(n)algorithm在运行时间上可以超过O(n 2 )algorithm。 当常数因子(我们在大O符号中省略)很大时会发生这种情况 。 例如,在上面的代码中,O(n)algorithm将有一个很大的常数因子。 因此,当n <10时,它将比在O(n 2 )中运行的algorithm更差。

这里,n = 100是交叉点。 因此,当O(n)和O(n 2 )都可以执行任务时,线性algorithm的常数因子比二次algorithm的常数因子多,那么我们倾向于select运行时间较短的algorithm。 例如,当对一个数组进行sorting时,即使在合并sorting或快速sorting运行渐近的情况下,我们也会切换到较小数组的插入sorting。 这是因为插入sorting比合并/快速sorting具有更小的常数因子,运行速度更快。

O(n)并不意味着比较不同algorithm的相对速度。 它们是为了衡量input量增加时运行时间增加的速度。 例如,

  • O(n)表示如果n乘以1000,则运行时间大致乘以1000。
  • O(n^2)表示如果n乘以1000,则运行大致乘以1000000。

所以当n足够大时,任何O(n)algorithm都会击败O(n^2)algorithm。 这并不意味着任何固定的东西。

长话短说,是的,它可以。 O的定义是基于O(f(x)) < O(g(x))意味着给定一个足够大的xg(x)将明确地花费更多的时间来运行f(x)

例如,一个已知的事实是,对于小值合并sorting是优于插入sorting(如果我没有记错,这应该适用于n小于31

是。 O()意味着只有渐近的复杂性。 线性函数可以比二次函数慢一些,如果线性函数具有足够大的线性减慢常数(如果循环的核心运行时间长了10倍,那么它的二次型会比较慢)。

O() – 符号只是一个推断,虽然是相当不错的一个。

唯一的保证就是 – 不pipe常数是多less,对于足够大的n ,O(n)algorithm将比O(n ^ 2)algorithm花费更less的操作。

作为一个例子,让我们来计算OP中整洁的例子中的操作。 他的两个algorithm只有一行不同:

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

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

由于其余的程序都是一样的,实际运行时间的差异将由这两条线决定。

  • 对于n = 100,两行都进行100次迭代,所以A和B在n = 100时完全相同
  • 对于n <100,比如n = 10,A只做10次迭代,而B做100次。显然A更快。
  • 对于n> 100,比如n = 1000。 现在A的循环做了1000次迭代,而B循环仍然进行了固定的100次迭代。 显然A更慢。

当然,O(n)algorithm要快得多,取决于常数因子。 如果在B中将常数100更改为1000,那么截断值也将变为1000。