在试图理解Theta和O符号之间的区别时，我遇到了以下声明：
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
但我不明白这一点。这本书以数学的方式解释了它，但它太复杂了，当我真的不理解时，阅读起来真的很无聊。
任何人都可以使用简单但功能强大的示例来解释两者之间的区别。
Big O只给出上渐近界，而大The也给出了下界。
所有Theta(f(n))也是O(f(n))，但不是相反。
T(n)据说是Theta(f(n))，如果它是O(f(n))和Omega(f(n))
出于这个原因，big-Theta比大O符号更具信息性，所以如果我们可以说一些大-Theta，它通常是首选。然而，证明某些东西是大的Theta比证明它是大O更难。
例如，merge sort既是O(n*log(n))又是Theta(n*log(n))，但它也是O（n2），因为n2渐近地“大于”它。但是，它不是Theta（n2），因为算法不是Omega（n2）。
Omega(n)是渐近下界。如果T(n)是Omega(f(n))，它意味着从某个n0，有一个恒定的C1，使T(n) >= C1 * f(n)。而大O说，有一个恒定的C2，使T(n) <= C2 * f(n))。
所有三个（Omega，O，Theta）只给出渐近信息（“大输入”）：
请注意，此表示法与算法的最佳，最差和平均情况分析无关。这些中的每一个都可以应用于每个分析。
我将引用Knuth的TAOCP第1卷 - 第110页（我有印度版）。我建议阅读第107-110页（1.2.11节渐近表示）
人们经常通过假设它给出一个确切的增长顺序来混淆O符号;他们使用它就好像它指定了下限和上限。例如，算法可能被称为低效，因为其运行时间为O（n ^ 2）。但O（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）
Big-Oh用于近似值。它允许你用等号=符号替换〜。在上面的例子中，对于非常大的n，我们可以确定数量将保持低于n ^ 4和n ^ 3和（1/3）n ^ 3 + n ^ 2 [并且不仅仅是n ^ 2]
Big Omega用于下限 - 具有Omega（n ^ 2）的算法不如具有大N的O（N logN）的算法有效。但是，我们不知道N的值是什么（在这个意义上我们知道大约）
Big Theta用于确定增长顺序，包括下限和上限。
如果运行时间以big-O表示法表示，则表示运行时间不会比给定表达式慢。它表达了最糟糕的情况。
但是使用Theta符号，你也知道它不会更快。也就是说，没有最佳情况下算法会更快地重新调整。
这给出了预期运行时间的更精确限制。然而，对于大多数目的而言，忽略下限（更快执行的可能性）更简单，而您通常只关注最坏情况。
这是我的尝试：
一个函数，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）是上述问题中Big O之后的函数。起初这让我很困惑。2^(n+1)分解为2 * 2^n。这样做，我们留下：
2 * 2^n <= c(2^n)c的值，其中c >= 2。所以，是的，我们可以说f(2^(n+1))是O(2^n)。Big Omega以同样的方式工作，除了它评估f(n)> = c*g(n)为某些常数'c'。
因此，以相同的方式简化上述功能，我们留下（注意> = now）：
2 * 2^n >= c(2^n)
因此，该等式适用于范围0 <= c <= 2。所以，我们可以说f(2^(n+1))是(2^n)的大欧米茄。
现在，由于那些人持有，我们可以说功能是Big Theta（2^n）。如果他们中的一个不能为'c'的常数工作，那么它不是Big Theta。
上面的例子来自Skiena的算法设计手册，这是一本很棒的书。
希望有所帮助。这真的是一个简化的难题。不要对'c'这么多挂掉，只需将其分解为更简单的术语并使用你的基本代数技巧。
我将用一个例子来说明差异。
将函数f（n）定义为
if n is odd f(n) = n^3
if n is even f(n) = n^2
来自CLRS
如果存在正常数c1和c2，则函数f（n）属于集合Θ（g（n）），使得它可以“夹在”c1g（n）和c2g（n）之间，对于足够大的n。
和
O（g（n））= {f（n）：存在正常数c和n0，使得对于所有n≥n0}，0≤f（n）≤cg（n）。
和
Ω（g（n））= {f（n）：存在正常数c和n0，使得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）= O（g（n））和f（n）=时，我们才有f（n）=Θ（g（n）） Ω（G（N））。
因此，f（n）不在Θ（n ^ 3），而在O（n ^ 3）和Ω（n ^ 2）
在非常简单的语言中，差异将是这样的：
Big O表示法用于算法的最坏情况分析。 Big Omega用于算法的最佳案例分析。当最佳案例和最差案例分析相同时，Big Theta用于分析算法。
假设您正在使用二进制搜索算法在排序数组中查找数字。
[1 2 3 4 5 6 7]
在最坏的情况下，例如当目标为1时，它必须执行log（n）拆分检查，在我们的例子中是log（7）。它可以表示为O（n）。
在最好的情况下，当目标是3时，它只执行一个操作。它可以表示为Ω（1）