关于big O和big Omega的问题

Question

我认为这可能是一个关于大O表示法的初学者问题。例如，我有一个算法，它递归地拆分整个列表(O(n))，然后将其重新组合在一起(O(N))。我假设这意味着效率是O(n) + O(n)。这是否简化为2O(n)、O(2n)或O(n)？根据我对这个符号的了解，它将是O(2n)，并且使用渐近符号的规则，您可以省略2，从而得到O(n)的效率。

但是，如果我们试图找到一个下限，那么这个规则还能适用吗？如果Ω(n) +Ω(n) =Ω(2n)，你还能去掉2吗？我不这么认为，因为你实际上是在降低下限(因为n< 2n)。

Answer 1

是否简化为2O(n)、O(2n)或O(n)?"

以上都是，但前两个过于复杂。O(n)将是规范符号。

2*N与N成正比，因此对于足够大的N( O( 2*N ) )，如果最大成本与2*N成正比，那么对于足够大的N( O(N) )，最大成本也与N成比例。

如果我们试图找到一个下限，那么这个规则还能适用吗？

肯定是这样。

2*N与N成正比，因此对于足够大的N(Ω( 2*N ) )，如果最小成本不小于2* N，则对于足够大的N(Ω(N) )，最小成本也不小于N。

例如，假设您有一个算法，其执行时间为300ms+ 100*N。其速度的下界是Θ(N)，因此Ω(N)。

如果算法的执行时间是原来的两倍呢？即使它需要600ms+200xNms来执行，其速度的下限仍然是Θ(N)，因此Ω(N)。

要认识到理解Θ(N)之类的最重要的事情是，这些符号用于研究事物的缩放程度。一种算法花费的时间是另一种算法的两倍，这并不能说明这两种算法的伸缩性有多好，所以它们可以在速度下限上使用相同的Ω()也就不足为奇了。

Answer 2

它将简化--通常为O(n)，表明解决问题所需的时间与问题的大小成正比。在这种情况下，写成2O(n)可能更合适，尽管它的意思是相同的。

Answer 3

已经有一段时间了，但我认为你在这两种情况下都是对的。

更新

实际上看起来像Ω(n) +Ω(n) ==Ω(n)