Θ(n)和O(n)之间有什么区别？
mar*_*nus 405 big-o notation time-complexity big-theta
有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？
Meh*_*ari 581
简短说明:
如果算法是Θ(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 2),O(n 1000000),O(2 n),...但是Θ(n)算法不是 Θ(n 2) .
实际上,由于f(n)=Θ(g(n))意味着对于n的足够大的值,对于c的某些值,f(n)可以被绑定在c 1 g(n)和c 2 g(n)内.1和c 2,即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等人的算法导论.
- 如果“如果一个算法的复杂度为 O(g(n))，则意味着随着 n 变大，该算法的运行时间至多与 g(n) 成正比。” 那么你怎么说“基本上当我们说一个算法是 O(n) 时，它也是 O(n2)、O(n1000000)、O(2n)”？ (2认同)
And*_*kov 318
有一种简单的方法(一种技巧,我猜)要记住哪种符号意味着什么.
所有Big-O符号都可以被视为有一个条形码.
当看Ω时,条形位于底部,因此它是(渐近)下界.
当看到Θ时,条形显然位于中间.所以它是一个(渐近)紧束缚.
手写O时,通常在顶部完成,并绘制一个波浪形.因此O(n)是函数的上界.公平地说,这个不适用于大多数字体,但它是名称的原始理由.
- 在任何问题上我通常都不会低于3-4的答案.这值得一试.谢谢你分享这个技巧.:d (5认同)
- 我喜欢这个。但是你能分享一下“这是名字的最初合理性”的来源吗？ (3认同)
l_3*_*7_l 55
一个是大"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. (20认同)
kar*_*niz 34
我将提供一个简单的例子,而不是提供一个理论上的定义,这些定义已经在这里进行了精美的总结.
假设运行时间f(i)为O(1).下面是一个渐近运行时的代码片段?(n).它总是调用函数f(...) n时间.下限和上限都是n.
for(int i=0; i<n; i++){
f(i);
}
下面的第二个代码片段具有渐近运行时O(n).它f(...) 在大多数 n时候调用该函数.上限是n,但下限可以是?(1)或?(log(n))取决于内部发生的情况f2(i).
for(int i=0; i<n; i++){
if( f2(i) ) break;
f(i);
}
- 在这种情况下，渐近意味着“对于足够大的 n”。渐进运行时间为 θ(n) 的代码片段的运行时间将随着 n 的增加而线性增长，例如运行时间 T 可以表示为 T(n) = a*n+b。对于较小的 n 值（例如 n=1 或 2），这可能不是描述行为的最佳方式 - 也许您有一些初始化代码需要比 f(i) 更长的时间。 (2认同)
ahn*_*cad 10
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,(等).
使用限制
\n\n让我们考虑一下f(n) > 0并g(n) > 0为所有人n。考虑这一点是可以的，因为最快的真正算法至少有一个操作，并在开始后完成其执行。这将简化微积分，因为我们可以使用值 ( f(n)) 而不是绝对值 ( |f(n)|)。
- \n
\n\nf(n) = O(g(n))一般的：
\n\n
Run Code Online (Sandbox Code Playgroud)\n\nf(n) \n0 \xe2\x89\xa4 lim \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 < \xe2\x88\x9e\n n\xe2\x9e\x9c\xe2\x88\x9e g(n)\n为了
\n\ng(n) = n：
Run Code Online (Sandbox Code Playgroud)\n\nf(n) \n0 \xe2\x89\xa4 lim \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 < \xe2\x88\x9e\n n\xe2\x9e\x9c\xe2\x88\x9e n\n例子：
\n\n
Run Code Online (Sandbox Code Playgroud)\n\nExpression Value of the limit\n------------------------------------------------\nn = O(n) 1\n1/2*n = O(n) 1/2\n2*n = O(n) 2\nn+log(n) = O(n) 1\nn = O(n*log(n)) 0\nn = O(n\xc2\xb2) 0\nn = O(n\xe2\x81\xbf) 0\n反例：
\n\n
Run Code Online (Sandbox Code Playgroud)Expression Value of the limit\n-------------------------------------------------\nn \xe2\x89\xa0 O(log(n)) \xe2\x88\x9e\n1/2*n \xe2\x89\xa0 O(sqrt(n)) \xe2\x88\x9e\n2*n \xe2\x89\xa0 O(1) \xe2\x88\x9e\nn+log(n) \xe2\x89\xa0 O(log(n)) \xe2\x88\x9e\n\n
\n\nf(n) = \xce\x98(g(n))一般的：
\n\n
Run Code Online (Sandbox Code Playgroud)\n\nf(n) \n0 < lim \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 < \xe2\x88\x9e\n n\xe2\x9e\x9c\xe2\x88\x9e g(n)\n为了
\n\ng(n) = n：
Run Code Online (Sandbox Code Playgroud)\n\nf(n) \n0 < lim \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 < \xe2\x88\x9e\n n\xe2\x9e\x9c\xe2\x88\x9e n\n例子：
\n\n
Run Code Online (Sandbox Code Playgroud)\n\nExpression Value of the limit\n------------------------------------------------\nn = \xce\x98(n) 1\n1/2*n = \xce\x98(n) 1/2\n2*n = \xce\x98(n) 2\nn+log(n) = \xce\x98(n) 1\n反例：
\n\n
Run Code Online (Sandbox Code Playgroud)Expression Value of the limit\n-------------------------------------------------\nn \xe2\x89\xa0 \xce\x98(log(n)) \xe2\x88\x9e\n1/2*n \xe2\x89\xa0 \xce\x98(sqrt(n)) \xe2\x88\x9e\n2*n \xe2\x89\xa0 \xce\x98(1) \xe2\x88\x9e\nn+log(n) \xe2\x89\xa0 \xce\x98(log(n)) \xe2\x88\x9e\nn \xe2\x89\xa0 \xce\x98(n*log(n)) 0\nn \xe2\x89\xa0 \xce\x98(n\xc2\xb2) 0\nn \xe2\x89\xa0 \xce\x98(n\xe2\x81\xbf) 0\n\n