在计算时间方面，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 = 1 ， d = 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))意味着给定一个足够大的x ， g(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。
