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

渐近复杂度(这是大O和大Theta所代表的)完全忽略了所涉及的常数因素 - 它仅用于指示随着输入的大小变大,运行时间将如何变化.

因此,对于某些给定的?(n)算法,一个算法可能需要花费的时间超过一个- 这将会发生真正取决于所涉及的算法 - 对于您的具体示例,这将是这种情况,忽略了优化之间的差异的可能性二.?(n2)nnn < 100

对于任何两个给定的算法?(n)和时间,你可能会看到的是:?(n2)

• 该?(n)算法在n较小时较慢,然后随着增加而变慢 (如果一个更复杂,即具有更高的常数因子,则会发生),或者?(n2)n
?(n)
• 在一个总是慢.?(n2)

虽然这当然可能,该?(n)算法可以慢,那么一个,然后又一个,依此类推为增加,直到变得非常大,从该点起一个将永远是慢的,虽然它是大大不太可能发生.?(n2)?(n)nn?(n2)

稍微更多的数学术语:

假设算法对某些算法采取操作.?(n2)cn2c

并且?(n)算法dn为某些操作采取操作d.

这与形式定义一致,因为我们可以假设它保持n大于0(即对于所有n)并且运行时间所在的两个函数是相同的.

在你的榜样行,如果你是说c = 1和d = 100,则?(n)算法将变得更慢,直到n = 100,在该点算法将变得更慢.?(n2)

_{(由WolframAlpha提供)}.

符号说明:

技术上,big-O只是一个上限,这意味着你可以说一个O(1)算法(或者实际上任何算法花费的时间或更少的时间).因此我改为使用big-Theta(Θ)符号,这只是一个紧密的约束.有关更多信息,请参阅正式定义.O(n2)O(n2)

Big-O经常被非正式地视为或被教导成为一个紧张的界限,所以你可能已经基本上使用了big-Theta而不知道它.

如果我们只谈论一个上限(根据big-O的正式定义),那就更像是一个"任何事情"的情况 - O(n)一个可以更快,一个可以更快或者他们可以采取相同的时间量(渐近) - 关于比较算法的大O,通常不能做出特别有意义的结论,只能说,给定一些算法的大O,该算法不会采取任何算法比这个时间长(渐近).O(n2)

Answer 2

是的,O(n )算法在运行时间方面可以超过O(n ²)算法.当常数因子(我们在大O表示法中省略)很大时会发生这种情况.例如,在上面的代码中,O(n)算法将具有很大的常数因子.因此,它将比在O(n ²)中运行n <10 的算法表现更差.

这里,n = 100是交叉点.因此,当任务可以在O(n)和O(n ²)中执行并且线性算法的常数因子大于二次算法的常数因子时,那么我们倾向于优选具有更差运行时间的算法.例如,在对数组进行排序时,我们会切换到较小数组的插入排序,即使合并排序或快速排序运行渐进式更快.这是因为插入排序的常数因子比合并/快速排序小,并且运行速度更快.

Answer 3

大O(n)并不是要比较不同算法的相对速度.它们用于测量当输入大小增加时运行时间增加的速度.例如,

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

因此,当n足够大时,任何O(n)算法都会击败O(n^2)算法.它并不意味着任何固定的东西n.

Answer 4

长话短说,是的,它可以.定义O是基于这样一个事实,即这O(f(x)) < O(g(x))意味着肯定g(x)会花费更多的时间来运行而不是f(x)给予足够大的支持x.

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