O,Ω和Θ之间有什么区别？

Question

我正在学习算法分析.我无法理解O,Ω和Θ之间的差异.

它们的定义方式如下:

• f(n) = O(g(n))装置c · g(n)是一个上限f(n).因此存在一些常数c,使得f(n)总是≤ c · g(n),对于足够大的n (即,n ? n0对于某一常数n0).
• f(n) = ?(g(n))装置c · g(n)是一个下界f(n).因此存在一些常数c,f(n)总是≥ c · g(n),对于所有人n ? n0.
• f(n) = ?(g(n))意味着c1 · g(n)是对上限f(n)和c2 · g(n)一个下限f(n),对于所有n ? n0.因此存在常数c1和c2 使得f(n) ? c1 ·g(n)和f(n) ? c2 ·g(n).这意味着它g(n) 提供了一个很好的紧密绑定f(n).

我理解这个的方式是:

• O(f(n)) 给出了给定函数/算法的最坏情况复杂性.
• ?(f(n)) 给出了给定函数/算法的最佳案例复杂性.
• ?(f(n)) 给出了给定函数/算法的平均情况复杂度.

如果我错了,请纠正我.如果是这种情况,则必须以所有三种符号表示每种算法的时间复杂度.但我观察到它表示为O,Ω或Θ; 为什么不是全部三个？

Answer 1

重要的是要记住,符号,无论是O,Ω还是Θ,表达函数的渐近增长 ; 它与算法本身没有任何内在联系.有问题的函数可能是算法的"复杂性"(运行时间),无论是最坏情况,最佳情况还是平均情况,但符号与函数的来源无关.

例如,函数f(n)= 3n ² +5是:

• O(n ²),也是O(n ² log n),O(n ³),O(n ⁴)等,但不是O(n).
• Ω(n ²),它也是Ω(n log n),Ω(n)等,但不是Ω(n ³).
• Θ(n ²).它甚至不是Θ(n ² log n)或Θ(n ²/log n).

现在,通常所考虑的函数是算法的最坏情况复杂性,并且使用三者的符号取决于我们想要说什么以及我们如何仔细地进行分析.例如,我们可能会观察到,因为有两个嵌套循环,最坏情况下的运行时间最多为 O(n ²),而不关心这是否实际上是针对某些输入实现的.(通常很明显它是.)或者,我们可以说排序的最坏情况运行时间是Ω(n log n),因为必须有一些输入,它必须至少需要cn(log n)脚步.或者,我们可以查看一个特定的mergesort算法,并且看到在最坏情况下最多需要O(n log n)步骤,并且某些输入使得它需要n log n步,因此最坏情况下的运行时间是Θ(n log n).

请注意,在上面的所有三个示例中,仍然是正在分析的相同(最坏情况)运行时间.我们可能会分析最佳案例或平均案例,但同样,我们使用的三种符号取决于我们想说的内容 - 我们是否想要给出上限,下限或紧密限制增长相同的功能.

Answer 2

Θ表示渐近紧上限和下限.

O表示上限,但此界限可能紧密也可能不紧.
o表示不紧的上限.

Ω表示下限,但此限制可能会或可能不会很紧.
ω表示不紧的下界.

Answer 3

以下是一些真正可以帮助您的资源:

• 维基百科
• 维基书
• 麻省理工学院讲座视频
• 来自印度IITB的视频

Answer 4

对于这三者的意思,请参阅CanBerkGüder的回答.

另请注意,它们与最佳案例,最坏情况和普通案例无关.例如,冒泡排序是Θ(n)最佳情况(因为如果数据已经排序,则仅需要进行n-1次比较),以及Θ(n ^ 2)最坏情况.假设随机混洗输入,它是Θ(n ^ 2)平均情况.因此,该平均情况也是O(n ^ 2),O(n ^ 3)和O(2 ^ n).

所以,O,Θ和Ω告诉你它是什么类型的约束.他们没有告诉你限制是什么.在上下文中,它可能是对最佳情况,更坏情况,平均情况或整个算法(所有情况)的限制.

当然,如果算法具有Ω(g)最佳情况,那么它本身就是Ω(g).如果它具有O(g)最坏情况,则为O(g).所以那里有一种关系.但如果它有Θ(g)的平均情况,那几乎没有告诉你最好和最坏的情况.

至于"为什么不是全部三个？".

如果函数是Θ(g),那么它也是O(g)和Ω(g).因此,在Θ界限旁边提供其他界限没有多大意义.

当你单独看到其中一个时,通常是因为我们只关心上限,或者我们只关心下限.所以我们说所有比较排序必然是Ω(n log n)最坏的情况,并且冒泡排序是O(n ^ 2)最坏情况但是O(n)最好的情况,因为我们不是试图完全描述时间复杂性,我们只是在特定的上下文中表达我们关心的界限.

无论如何,大多数人似乎都很懒惰,并且不想输入希腊字母.我知道我是.所以我们只是说比较分类"至多是O(n log n)".这真的是滥用符号,但它得到了重点.