0,Ω和Θ之间的区别是什么? [英] What is the difference between O, Ω, and Θ?

查看:246
本文介绍了0,Ω和Θ之间的区别是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我学习算法分析。我无法理解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)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e., n ≥ n0 for some constant n0).
  • f(n) = Ω(g(n)) means c · g(n) is a lower bound on f(n). Thus there exists some constant c such that f(n) is always ≥ c · g(n), for all n ≥ n0.
  • f(n) = Θ(g(n)) means c1 · g(n) is an upper bound on f(n) and c2 · g(n) is a lower bound on f(n), for all n ≥ n0. Thus there exist constants c1 and c2 such that f(n) ≤ c1 ·g(n) and f(n) ≥ c2 ·g(n). This means that g(n) provides a nice, tight bound on f(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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆