有时我看到Θ(n)中间有一个奇怪的Θ符号，有时只是O(n)。只是因为没人知道如何输入这个符号而懒惰打字，还是它有别的意思?
当前回答
有一种简单的方法(我猜是一种技巧)来记住哪个符号意味着什么。
所有的大o符号都可以被认为有一个条形。
当查看Ω时，条在底部，所以它是一个(渐近的)下界。
在看Θ的时候，条显然是在中间。所以这是一个(渐近的)紧边界。
当书写O字时，你通常在顶部完成，然后画一圈。因此O(n)是函数的上界。公平地说，这个方法不适用于大多数字体，但它是名称的最初理由。
其他回答
是一种表示特殊情况的简写方式 O和是一样的。
因此，如果有人声称Theta是表达式q，那么他们也必然声称大O是表达式q, Omega是表达式q。
粗糙的类比:
如果: Theta说，那个动物有5条腿 然后是: 大O是正确的(“那个动物的腿少于或等于5条。”) 而且 Omega是正确的(“那个动物有超过或等于5条腿。”)
这只是一个粗略的类比，因为表达式不一定是特定的数字，而是不同数量级的函数，如log(n)， n, n²，(等等)。
有一种简单的方法(我猜是一种技巧)来记住哪个符号意味着什么。
所有的大o符号都可以被认为有一个条形。
当查看Ω时，条在底部，所以它是一个(渐近的)下界。
在看Θ的时候，条显然是在中间。所以这是一个(渐近的)紧边界。
当书写O字时，你通常在顶部完成，然后画一圈。因此O(n)是函数的上界。公平地说，这个方法不适用于大多数字体，但它是名称的最初理由。
我不打算提供一个理论定义，这里已经总结得很好了，我将给出一个简单的例子:
假设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);
}
图表可以让之前的答案更容易理解:
Θ-Notation -同阶| o符号-上限
在英语中,
在左边，注意有一个上界和下界，它们都是同一个数量级(即g(n))。忽略常数，如果上界和下界具有相同的数量级，我们可以有效地说f(n) = Θ(g(n))或者f(n)在大(g(n))。
从右边开始，一个更简单的例子，它说上限g(n)只是一个数量级，忽略了常数c(就像所有大O符号一样)。
一个是大O
一个是大Theta
http://en.wikipedia.org/wiki/Big_O_notation
大O表示算法的执行步数不会超过给定表达式(n^2)
大意味着你的算法执行的步骤不会少于给定表达式(n^2)
对于同一个表达式，当两个条件都为真时，您可以使用大theta符号....
