一个是大O

一个是大Theta

http://en.wikipedia.org/wiki/Big_O_notation

大O表示算法的执行步数不会超过给定表达式(n^2)

大意味着你的算法执行的步骤不会少于给定表达式(n^2)

对于同一个表达式，当两个条件都为真时，您可以使用大theta符号....

一个是大O

一个是大Theta

http://en.wikipedia.org/wiki/Big_O_notation

大O表示算法的执行步数不会超过给定表达式(n^2)

大意味着你的算法执行的步骤不会少于给定表达式(n^2)

对于同一个表达式，当两个条件都为真时，您可以使用大theta符号....

f(n)<=k*n时，如果正k存在，则f(n)属于O(n)

当k1*n<= F (n)<=k2*n时，F (n)属于Θ(n)

维基百科上关于大O符号的文章

我不打算提供一个理论定义，这里已经总结得很好了，我将给出一个简单的例子:

假设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);
}

Conclusion: we regard big O, big θ and big Ω as the same thing. Why? I will tell the reason below: Firstly, I will clarify one wrong statement, some people think that we just care the worst time complexity, so we always use big O instead of big θ. I will say this man is bullshitting. Upper and lower bound are used to describe one function, not used to describe the time complexity. The worst time function has its upper and lower bound; the best time function has its upper and lower bound too. In order to explain clearly the relation between big O and big θ, I will explain the relation between big O and small o first. From the definition, we can easily know that small o is a subset of big O. For example：

T (n) = n ^ 2 + n,我们可以说T (n) = O (n ^ 2)、T (n) = O (n ^ 3)、T (n) = O (n ^ 4)。但对于小o, T(n)=o(n²)不符合小o的定义，所以T(n)=o(n³)，T(n)=o(n²)对小o是正确的，多余的T(n)=o(n²)是什么?太大了θ!

一般来说，我们说大O是O(n²)而不是T(n)=O(n³)T(n)=O(n²)为什么?因为我们潜意识里把大O看成大θ。 同样，我们也在潜意识中将大Ω视为大θ。 总而言之，大O、大θ和大Ω从定义上看是不同的，但在我们的口中和大脑中却是一样的。

有一种简单的方法(我猜是一种技巧)来记住哪个符号意味着什么。

所有的大o符号都可以被认为有一个条形。

当查看Ω时，条在底部，所以它是一个(渐近的)下界。

在看Θ的时候，条显然是在中间。所以这是一个(渐近的)紧边界。

当书写O字时，你通常在顶部完成，然后画一圈。因此O(n)是函数的上界。公平地说，这个方法不适用于大多数字体，但它是名称的最初理由。