Θ(n)和O(n)之间有什么区别？

有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？

1> Mehrdad Afsh..：

---

简短说明:

如果算法是Θ(g(n)),则意味着算法的运行时间n(输入大小)变大,与g(n)成比例.

如果算法是O(g(n)),则意味着算法作为n变大的运行时间最多与g(n)成比例.

通常,即使人们谈论O(g(n)),他们实际上也意味着Θ(g(n)),但从技术上讲,存在差异.

---

技术上更:

O(n)表示上限.Θ(n)表示紧束缚.Ω(n)表示下限.

f(x)=Θ(g(x))iff f(x)= O(g(x))且f(x)=Ω(g(x))

基本上当我们说算法是O(n)时,它也是O(n ²),O(n ^1000000),O(2 ⁿ),...但是Θ(n)算法不是 Θ(n ²) .

实际上,由于f(n)=Θ(g(n))意味着对于n的足够大的值,对于c的某些值,f(n)可以被绑定在c ₁ g(n)和c ₂ g(n)内.₁和c ₂,即f的生长速率是渐近等于克:克可以是一个下界和和上界的F.这直接暗示f也可以是g的下限和上限.所以,

f(x)=Θ(g(x))iff g(x)=Θ(f(x))

类似地,为了显示f(n)=Θ(g(n)),足以表明g是f的上界(即f(n)= O(g(n))),f是下限g(即f(n)=Ω(g(n)),它与g(n)= O(f(n))完全相同.简洁,

f(x)=Θ(g(x))iff f(x)= O(g(x))和g(x)= O(f(x))

---

还有一些小哦和小的omega(?)符号表示函数的松散上边界和松散下边界.

总结一下:

f(x) = O(g(x))(大哦)意味着增长率f(x)渐近地小于或等于增长率g(x).

f(x) = ?(g(x))(big-omega)意味着增长率f(x)渐近地大于或等于增长率g(x)

f(x) = o(g(x))(小哦)意味着增长率f(x)渐渐低于增长率g(x).

f(x) = ?(g(x))(little-omega)意味着增长率f(x)渐近地大于增长率g(x)

f(x) = ?(g(x))(theta)意味着增长率f(x)渐近等于增长率g(x)

有关更详细的讨论,您可以阅读维基百科上的定义或参考经典教科书,如Cormen等人的算法导论.

2> Andrei Krotk..：

---

有一种简单的方法(一种技巧,我猜)要记住哪种符号意味着什么.

所有Big-O符号都可以被视为有一个条形码.

当看Ω时,条形位于底部,因此它是(渐近)下界.

当看到Θ时,条形显然位于中间.所以它是一个(渐近)紧束缚.

手写O时,通常在顶部完成,并绘制一个波浪形.因此O(n)是函数的上界.公平地说,这个不适用于大多数字体,但它是名称的原始理由.

---

在任何问题上我通常都不会低于3-4的答案.这值得一试.谢谢你分享这个技巧.:d

3> l_39217_l..：

---

一个是大"O"

一个是大Theta

http://en.wikipedia.org/wiki/Big_O_notation

Big O意味着您的算法将在不超过给定表达式的步骤中执行(n ^ 2)

Big Omega意味着您的算法将以不比给定表达式(n ^ 2)更少的步骤执行

当两个条件对于同一个表达式都为真时,您可以使用大的θ表示法....

---

但是错了!当n变得非常大时,步数以n ^ 2为界.但是,在n ^ 2 + c步骤中运行的算法需要超过n ^ 2步,但仍然是O(n ^ 2).Big-O表示法仅描述*渐近*beahviour.

4> kara deniz..：

---

我将提供一个简单的例子,而不是提供一个理论上的定义,这些定义已经在这里进行了精美的总结.

假设运行时间f(i)为O(1).下面是一个渐近运行时的代码片段?(n).它总是调用函数f(...) n时间.下限和上限都是n.

for(int i=0; i

下面的第二个代码片段具有渐近运行时O(n).它f(...) 在大多数 n时候调用该函数.上限是n,但下限可以是?(1)或?(log(n))取决于内部发生的情况f2(i).

for(int i=0; i

        

5> ahnbizcad..：
Theta是一种速记方式,指的是大O和Omega相同的特殊位置.

因此,如果有人声称The Theta is expression q,那么他们也必然要求Big O is expression q和Omega is expression q.



粗略的比喻:

如果:Theta声称,"那只动物有5条腿." 接下来是:大O是真的("动物的腿数小于或等于5".)而且Omega是真的("动物的腿数大于或等于5".)

这只是一个粗略的类比,因为表达式不一定是特定数字,而是具有不同数量级的函数,例如log(n),n,n ^ 2,(等).

        

6> Ricardo..：
一个图表可以使以前的答案更容易理解:

Θ-表示法 - 相同的顺序| O符号 - 上限

  

用英语讲,

在左边,注意有一个上限和下限都是相同的数量级(即g(n)).忽略常数,如果上限和下限具有相同的数量级,则可以有效地说f(n)=Θ(g(n))或f(n)是g(n)的大θ.

从正确的,更简单的例子开始,它说上限g(n)只是数量级并忽略常数c(正如所有大O符号所做的那样).

        

7> user54579..：
f(n)属于O(n)如果存在积极k的f(n)<=k*n

f(n)属于?(n)如果存在正k1,k2如k1*n<=f(n)<=k2*n

关于Big O符号的维基百科文章