Theta和Big O符号用简单的语言表达
在试图理解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.
但我不明白这一点。 这本书在数学上解释了它，但它太复杂了，当我真的不理解时，阅读变得很无聊。
任何人都可以用简单而强大的例子来解释两者之间的区别。
大O只给出上界渐近界，而大θ也给出下界。
所有那些Theta(f(n))也是O(f(n)) ，但不是相反。
如果它是O(f(n)) 和 Omega(f(n))则称T(n)为Theta(f(n))
出于这个原因， big-theta更具信息性，然后是big-O符号，所以如果我们可以说一些大的theta，它通常是首选。 然而，证明某些东西是大的Theta比证明它是大O更难。
例如 ，合并排序既是O(n*log(n))又是Theta(n*log(n)) ，但它也是O（n2），因为n2比它渐近地“大”。 然而，它不是Theta（n2），因为算法不是欧米茄（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）
大哦是近似值。 它可以让你用等号代替〜。 在上面的例子中，对于非常大的n，我们可以确定数量将保持在n ^ 4和n ^ 3和（1/3）n ^ 3 + n ^ 2 [而不仅仅是n ^ 2]以下，
大欧米茄是用于下界的 - 对于大N，Omega（n ^ 2）算法不会像O（N logN）那样高效。但是，我们不知道N的值是多少（从这个意义上我们知道约）
Big 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 ）是大O在上述问题之后的函数。 起初，这让我感到困惑。
那么，使用你的基本代数技巧来简化这个方程。 2^(n+1)分解为2 * 2^n 。 这样做，我们留下了：
2 * 2^n <= c(2^n)
现在它的方便，方程适用于任何值c其中c >= 2 。 所以，是的，我们可以说f(2^(n+1))是O(2^n) 。
大欧米茄的工作原理是一样的，只是它对某个常量'c'评估f(n) > = c*g(n) 。
所以，以相同的方式简化上述功能，我们留下了（注意> =现在）：
2 * 2^n >= c(2^n)
因此，该方程适用于范围0 <= c <= 2 。 所以，我们可以说f(2^(n+1))是(2^n)大欧米加。
现在，由于这两者都成立，我们可以说功能是Big Theta（ 2^n ）。 如果其中一个不能用于'c'的常数，那么它不是Big Theta。
上面的例子来自Skiena的算法设计手册，这是一本很棒的书。
希望有所帮助。 这确实是一个难以简化的概念。 不要太沉迷于'c' ，只要把它分解成简单的术语并使用你的基本代数技巧。