哪种算法更快O(N)或O(2N)？

Question

谈论Big O符号,如果一个算法时间复杂度为O(N)而其他算法为O(2N),哪一个更快？

Answer 1

大O的定义是:

O(f(n))= {g | 存在N和c> 0使得所有n> N的g(n)<c*f(n)

在英语中,O(f(n))是最终增长率小于或等于f的所有函数的集合.

所以O(n)= O(2n).在渐近复杂性方面,它们都不比另一个"更快".它们代表相同的增长率 - 即" 线性 "增长率.

证明:

O(n)是O(2n)的子集:令g是O(n)中的函数.然后有N和c> 0使得g(n)<c*n对于所有n> N.所以对于所有n> N,g(n)<(c/2)*2n.因此g在O(2n)中).

O(2n)是O(n)的子集:令g是O(2n)中的函数.然后存在N和c> 0,使得对于所有n> N,g(n)<c*2n.因此对于所有n> N,g(n)<2c*n.因此g在O(n)中.

通常,当人们提到渐近复杂度("大O")时,他们指的是规范形式.例如:

• 对数:O(log n)
• 线性:O(n)
• 线性的:O(n log n)
• 二次方:O(n ²)
• 指数:对于某些固定的c> 1,O(c ⁿ)

(这是一个更全面的列表:常见时间复杂性表)

所以通常你会写O(n),而不是O(2n); O(n log n),而不是O(3 n log n + 15 n + 5 log n).

Answer 2

Timothy Shield的答案绝对正确,O(n)和O(2n)指的是同一组函数,因此一个不比另一个"更快".但值得注意的是,更快的速度并不适用于此.

维基百科关于"大O符号"的文章使用了"慢速增长"这一术语,你可能会使用"更快",这是更好的做法.这些算法由它们随着n的增加而增长来定义.

可以很容易地想象O(n ^ 2)函数在实践中比O(n)快,特别是当n很小或者O(n)函数需要复杂变换时.符号表示,对于输入的两倍,人们可以预期O(n ^ 2)函数的时间大约是之前的4倍,其中O(n)函数将花费大约之前的两倍. .

Answer 3

它取决于渐近符号隐藏的常数。例如，采取3n + 5步骤的算法位于类中O(n)。采取步骤的算法也是如此2 + n/1000。但2n小于3n + 5和大于2 + n/1000...

这有点像询问是否5小于 1 到 10 之间的某个未指定的数字。这取决于未指定的数字。仅知道算法按O(n)步骤运行并不足以决定采用2n步骤的算法是否会更快完成。

实际上，情况比这更糟糕：您询问 1 到 10 之间的某个未指定数字是否大于 1 到 10 之间的其他未指定数字。您选择的相同集合并不意味着您碰巧选择的数字将是平等的！O(n)和O(2n)是算法的集合，并且因为 Big-O 的定义抵消了乘法因子，所以它们是同一集合。集合中的单个成员可能比其他成员更快或更慢，但集合是相同的。

Answer 4

理论上 O(N) 和 O(2N) 是相同的。

但实际上，O(N) 的运行时间肯定会更短，但并不重要。当 N 足够大时，两者的运行时间将相同。