关于大O和大Omega的问题 [英] Question about big O and big Omega

问题描述

我认为这可能是有关big-O表示法的初学者问题.举例来说，我有一种算法可以将整个列表递归分解(O(n))，然后将其放回一起(O(n)).我假设这意味着效率为O(n)+ O(n).这会简化为2O(n)，O(2n)或O(n)吗?根据我对这种表示法的了解，它应该是O(2n)，并且使用渐进表示法则可以删除2，从而获得O(n)的效率.

I think this is probably a beginner question about big-O notation. Say, for example, I have an algorithm that breaks apart an entire list recursively(O(n)) and then puts it back together (O(n)). I assume that this means that the efficiency is O(n) + O(n). Does this simplify to 2O(n), O(2n), or O(n)? From what I know about this notation, it would be O(2n) and using the rules of asymptotic notation you can drop the 2, giving an efficiency of O(n).

但是，如果我们尝试找到下限，此规则是否仍然适用?如果Ω(n)+Ω(n)=Ω(2n)，您还可以丢掉2吗?我认为不会，因为您实际上会降低下限(因为n< 2n).

If we were trying to find a lower bound, though, can this rule still apply? If Ω(n) + Ω(n) = Ω(2n), can you still drop the 2? I would think not, since you would actually be lowering the lower bound (since n < 2n).

推荐答案

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

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

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

All of the above, but the first two are overly complex. O(n) would be the canonical notation.

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

2*N is proportional to N, so if the maximum cost is no more than proportional to 2*N for a sufficiently large N ( O(2*N) ), the maximum cost is also no more than proportional to N for a sufficiently large 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成正比足够大的N(Ω(N)).

2*N is proportional to N, so if the minumum cost is no less than proportional to 2*N for a sufficiently large N ( Ω(2*N) ), the minimum cost is also no less than proportional to N for a sufficiently large N ( Ω(N) ).

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

For example, say you have an algorithm that takes 300 ms + 100*N ms to execute. The lower bound of its speed is Θ(N) and thus Ω(N).

如果算法执行时间是原来的两倍，该怎么办?即使执行花费600毫秒+ 200 * N毫秒，其速度的下限仍然是Θ(N)，因此仍然是Ω(N).

What if the algorithm were to take twice as long to execute? Even if it took 600 ms + 200*N ms to execute, the lower bound of its speed is still Θ(N) and thus Ω(N).

了解Θ(N)等最重要的事情是，这些符号用于研究事物的扩展程度.一种算法花费的时间是另一种算法的两倍，而后者却没有说出两种算法的扩展程度如何，因此对于速度的下限具有相同的Ω()也就不足为奇了.

The most important thing to realise to understand Θ(N) and the like is that these notations are used to study how well something scales. That one algorithm takes twice as long as another doesn't say anything about how well either scales, so it shouldn't be a surprise that they can have the same Ω() for the lower bound of their speed.

这篇关于关于大O和大Omega的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！