虽然试图了解西塔和O记法的区别，我碰到了以下声明：
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
但我不明白这一点。 这本书数学解释它，但它太复杂，变得非常无聊的时候，我真的不理解阅读。
使用简单，但功能强大的例子有谁能解释这两者之间的区别。
Answer 1:
大O是只给上渐近界，而大西塔也给人一种下限。
一切是Theta(f(n))也是O(f(n))而不是周围的其他方法。
T(n)被说成是Theta(f(n))如果是两个O(f(n)) 和 Omega(f(n))
出于这个原因， 大西塔是更多的信息，然后大O记法，所以如果我们可以说某地大西塔，它通常是首选。 然而，这是很难证明什么大西塔，而不是证明它是大O。
例如 ， 归并排序既是O(n*log(n))和Theta(n*log(n))但它也是O（N 2），由于N 2是渐近比“做大”。 然而，它不是西塔（N 2），由于该算法不欧米茄（N 2）。
Omega(n)是渐近下界 。 如果T(n)是Omega(f(n))这意味着从某个n0 ，有一个恒定的C1 ，使得T(n) >= C1 * f(n) 而大O说，有一个恒定的C2 ，使得T(n) <= C2 * f(n))
所有这三个（欧米茄，O，西塔）也仅渐近信息 （“为大的输入”）：
- 大O给出上限
- 大欧米茄给出下限和
- 大西塔同时给出的上限和下限
注意，这个符号是不相关的算法最好，最差，平均情况分析。 它们中的每一个可以被施加到每个分析。
Answer 2:
第110页（我有印度版） -我刚刚从Knuth的TAOCP第1卷报价。 我建议你阅读107-110页（ 第1.2.11渐近表示 ）
人们常常假设，它给经济增长的确切顺序搞乱O型符号; 他们使用它，就好像它指定了一个下界以及上限。 例如，因为它的运行时间为O（n ^ 2）的算法可能被称为低效率的。 但是，哦的运行时间（n ^ 2）并不一定意味着运行时间是不是也为O（n）
在107页，
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + N ^ 2 = O（N ^ 4）和
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + N ^ 2 = O（N ^ 3）和
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + N ^ 2 =（1/3）N ^ 3 +为O（n ^ 2）
大哦，是的近似值。 它可以让你有一个等号等号（=）取代〜。 在上面的例子，对于非常大的n，我们可以肯定的是，数量将保持低于N R个4和n ^ 3和（1/3）N ^ 3 + N ^ 2 [而不是简单地N ^ 2]
大欧米茄是下限 - 欧米茄的算法（N ^ 2），将无法做到高效为一体，具有O（N logN）的大型N.然而，我们不知道我们知道的N个值（在这个意义上大约）
大西塔是增长的确切顺序，既下限和上限。
Answer 3:
这里是我的尝试：
一个函数， f(n)是O(n)当且仅当存在常数， c ，使得f(n) <= c*g(n) 。
根据这个定义，我们可以说，功能f(2^(n+1))是O(2^n) ？
换句话说，不恒定的
'c'存在，使得2^(n+1) <= c*(2^n)注意所述第二函数（2^n）是在上述问题的大O后的功能。 这严重地混淆了我在第一。因此，然后用你的基本代数技巧来简化公式。
2^(n+1)分解成2 * 2^n。 这样做，我们留下了正在：2 * 2^n <= c(2^n)现在它的方便，方程适用于任何值
c其中c >= 2。 所以，是的，我们可以说，f(2^(n+1))是O(2^n)
大欧米茄的工作方式相同，除了它的计算结果f(n) > = c*g(n)对于某一常数'c'
因此，简化了上述功能以同样的方式，我们就只剩下（注意> =现在）：
2 * 2^n >= c(2^n)
所以，方程适用于范围0 <= c <= 2 。 因此，我们可以说， f(2^(n+1))是大欧米茄(2^n)
现在，由于这两个的举办，可以说功能是大西塔（ 2^n ）。 如果他们中的一个将不是恒定的工作'c' ，那么它不是大西塔。
上面的例子是由Skiena算法设计手册，这是一个奇妙的书拍摄。
希望帮助。 这确实是一个困难的概念简化。 不要被挂在什么这么多的'c'的，只是把它分解成更简单的使用条款和你的基本代数技能。
Answer 4:
我将用一个例子来说明差异。
让函数f（n）的被定义为
if n is odd f(n) = n^3
if n is even f(n) = n^2
从CLRS
函数f（n）的属于集合Θ（G（N）），如果存在正的常数c1和c2，使得它可以被 “夹在” C1G之间（n）和C2G（n）时，对于足够大的n。
和
O（G（N））= {F（N）：存在对所有的n≥N0正的常数c和N 0，使得0≤F（N）≤CG（N）}。
和
Ω（G（N））= {F（N）：存在正的常数c和N 0，使得0≤CG（n）的≤F（N）对所有的n≥N0}。
F上的上限（N）为n ^ 3。 所以我们的函数f（n）是显然为O（n ^ 3）。
但它是Θ（N ^ 3）？
为F（N）是在Θ（N ^ 3），它有两个功能中的一个之间，以被夹在形成下界，另一上界，这两者的生长以n ^ 3。 虽然上限是显而易见的，下界不能是n ^ 3。 下界实际上N ^ 2; F（n）是Ω（N ^ 2）
从CLRS
对于任何两个函数f（n）和G（N），我们有f（N）=Θ（G（N））当且仅当F（N）= O（G（N））和F（N）= Ω（G（N））。
因此F（n）不在Θ（N ^ 3），而它在为O（n ^ 3）和Ω（N ^ 2）
Answer 5:
如果运行时间在大O符号表示的，你知道的运行时间不会超过给定的表达式慢。 它表达了最坏的情况。
但是，随着西塔符号，你也知道，它不会更快。 也就是说，不存在最好的情况下，其中的算法将retun更快。
这样得出的预期运行时间更确切的约束。 然而，对于大多数的目的是更简单的忽略下限（更快的执行的可能性），而你通常只关心最糟糕的情况。
Answer 6:
在非常简单的语言差异会是这样的：
大O符号是用于算法的最坏情况分析。 大欧米茄用于算法的最佳案例分析。 大西塔用于算法的分析时，最好的情况和最坏情况分析是一样的。
比方说，你正在寻找使用二进制搜索算法排序后的数组的一个数字。
[1 2 3 4 5 6 7]
在最坏的情况下，例如当靶标是1它必须执行的log（n）分裂检查，这是log（7）在我们的例子。 它可以表示为O（N）。
在最好的情况下，例如，当目标是3只执行一个操作。 它可以表示为Ω（1）
文章来源: Difference between Big-Theta and Big O notation in simple language
