analysis - 关于大O和大欧米茄的问题

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

Does this simplify to 2O(n), O(2n), or O(n)?"

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

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

If we were trying to find a lower bound, though, can this rule still apply?

绝对是的。

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

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

如果算法的执行时间是原来的两倍怎么办？即使执行时间为 600 ms + 200*N ms，其速度的下限仍然是 Θ(N)，因此是 Ω(N)。

理解 Θ(N) 等最重要的一点是，这些符号用于研究某事物的伸缩性。一种算法花费的时间是另一种算法的两倍，没有说明任何一种算法的缩放程度，因此它们的速度下限具有相同的 Ω() 也就不足为奇了。