0,Ω和Θ之间的区别是什么? [英] What is the difference between O, Ω, and Θ?
问题描述
我学习算法分析。我无法理解0,Ω和Θ之间的差异。
I am learning algorithm analysis. I am having trouble understanding the difference between O, Ω, and Θ.
它们限定的方法如下:
-
F(N)= O(G(N))
办法C·G(N)
是一个 上界F(N)
。因此存在 一些恒C
,使得F(N)
是 总是≤C·G(N)
,足够大的N
(即ñ≥N0
对于某一常数N0
)。 -
F(N)=Ω(G(N))
办法C·G(N)
是一个 下限F(N)
。因此存在 一些恒C
,使得F(N)
是 总是≥C·G(N)
,所有ñ≥N0
。 -
F(N)=Θ(G(N))
办法C1·G(N)
是一个上界F(N)
和C2·G(N)
是一个 下限F(N)
,所有ñ≥N0
。 因此,存在常数C1
和C2
这样F(N)≤C1·G(N)
和F(N)≥ C2·G(N)
。这意味着G(N)
提供了一个很好的,紧密的结合在F(N)
。
f(n) = O(g(n))
meansc · g(n)
is an upper bound onf(n)
. Thus there exists some constantc
such thatf(n)
is always ≤c · g(n)
, for large enoughn
(i.e.,n ≥ n0
for some constantn0
).f(n) = Ω(g(n))
meansc · g(n)
is a lower bound onf(n)
. Thus there exists some constantc
such thatf(n)
is always ≥c · g(n)
, for alln ≥ n0
.f(n) = Θ(g(n))
meansc1 · g(n)
is an upper bound onf(n)
andc2 · g(n)
is a lower bound onf(n)
, for alln ≥ n0
. Thus there exist constantsc1
andc2
such thatf(n) ≤ c1 ·g(n)
andf(n) ≥ c2 ·g(n)
. This means thatg(n)
provides a nice, tight bound onf(n)
.
我理解这一点的方法是:
The way I have understood this is:
-
0(F(N))
给定函数/算法的最坏情况下的复杂性。 -
Ω(F(N))
给定函数/算法的最好情况的复杂性。 -
Θ(F(N))
给出平均情况给定函数/算法的复杂度。
O(f(n))
gives worst case complexity of given function/algorithm.Ω(f(n))
gives best case complexity of given function/algorithm.Θ(f(n))
gives average case complexity of given function/algorithm.
请纠正我,如果我错了。如果是这样的话,每个时间算法的复杂性必须pssed在所有三个符号前$ P $。但我认为,这是pssed为或者是O,Ω,或ΘEX $ P $;为什么不是所有的三个?
Please correct me if I am wrong. If it is the case, time complexity of each algorithm must be expressed in all three notations. But I observed that it's expressed as either O, Ω, or Θ; why not all three?
推荐答案
重要的是要记住,符号,无论是0,Ω或Θ,EX presses功能的渐进的增长是非常重要的;它并没有什么本质上是与算法的本身的。有问题的函数的可以的是复杂性(运行时间)的算法,无论是最坏情况,最好的情况或平均情况,但符号是独立的,其中功能从何而来。
It is important to remember that the notation, whether O, Ω or Θ, expresses the asymptotic growth of a function; it does not have anything intrinsically to do with algorithms per se. The function in question may be the "complexity" (running time) of an algorithm, either worst-case, best-case or average-case, but the notation is independent of where the function comes from.
例如,函数f(N)= 3n的 2 5是:
For example, the function f(n)=3n2+5 is:
- 为O(n 2 ),这也是为O(n 2 log n)的,为O(n 3 ),O(N 4 )等,而不是为O(n)。
- Ω(N 2 ),这也是Ω(N日志N),Ω(N)等,而不是Ω(N 3 )。
- Θ(N 2 )。它甚至不是Θ(N 2 日志N)或Θ(N 2 / log n)的。
- O(n2), it is also O(n2log n), O(n3), O(n4) and so on, but is not O(n).
- Ω(n2), it is also Ω(n log n), Ω(n) and so on, but is not Ω(n3).
- Θ(n2). It is not even Θ(n2log n) or Θ(n2/log n).
现在,通常被认为是功能是在最坏情况下的算法的复杂性,这是用三个符号取决于我们想要说些什么以及我们如何认真做了分析。例如,我们可以观察到,因为有两个嵌套循环,正在运行的最坏情况下的时间的最多的为O(n 2 ),而不关心这是否是真正取得了一些意见。 (通常很明显,它是。)或者,我们可以说,运行排序的时间最坏的情况是Ω(N log n)的,因为必须有一定的投入,它必须至少CN(log n)的脚步。或者,我们可以看一个特定的归并算法,并看到它需要至多为O(n log n)的,在最坏情况下的步骤的和的一些投入使得它取n日志n步,所以运行时间的最坏情况是Θ(正log n)的
Now, usually the function considered is the worst-case complexity of an algorithm, and which notation of the three is used depends on what we want to say about it and on how carefully we do the analysis. For example, we may observe that because there are two nested loops, the worst-case running time is at most O(n2), without caring about whether this is actually achieved for some input. (Usually it is obvious that it is.) Or, we may say that the worst-case running time of sorting is Ω(n log n), because there must be some inputs for which it must take at least cn(log n) steps. Or, we may look at a particular mergesort algorithm, and see that it takes at most O(n log n) steps in the worst-case and that some input makes it take n log n steps, so the worst-case running time is Θ(n log n).
请注意,上述的所有的三个例子中,它仍然是相同的(最坏情况)上运行的被被分析的时间。我们可以代替,但重新分析最好的情况或平均情况,这三个我们使用的符号取决于我们想说的 - 不管我们想给一个上限,下限,或紧约束的顺序成长的同样的功能的。
Note that in all the three examples above, it was still the same (worst-case) running time that was being analyzed. We may analyze the best-case or average-case instead, but again, which notation of the three we use depends on what we want to say — whether we want to give an upper bound, lower bound, or tight bound on the order of growth of the same function.
这篇关于0,Ω和Θ之间的区别是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!