使用限制

让我们考虑所有n的f(n) > 0和g(n) > 0。这样考虑是可以的，因为最快的实算法至少有一个操作，并且在开始后完成执行。这将简化微积分，因为我们可以使用值(f(n))而不是绝对值(|f(n)|)。

f(n) = O(g(n)) General: f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n) For g(n) = n: f(n) 0 ≤ lim ──────── < ∞ n➜∞ n Examples: Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0 Counterexamples: Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞ f(n) = Θ(g(n)) General: f(n) 0 < lim ──────── < ∞ n➜∞ g(n) For g(n) = n: f(n) 0 < lim ──────── < ∞ n➜∞ n Examples: Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1 Counterexamples: Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0

使用限制

让我们考虑所有n的f(n) > 0和g(n) > 0。这样考虑是可以的，因为最快的实算法至少有一个操作，并且在开始后完成执行。这将简化微积分，因为我们可以使用值(f(n))而不是绝对值(|f(n)|)。

f(n) = O(g(n)) General: f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n) For g(n) = n: f(n) 0 ≤ lim ──────── < ∞ n➜∞ n Examples: Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0 Counterexamples: Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞ f(n) = Θ(g(n)) General: f(n) 0 < lim ──────── < ∞ n➜∞ g(n) For g(n) = n: f(n) 0 < lim ──────── < ∞ n➜∞ n Examples: Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1 Counterexamples: Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0

简短说明:

如果一个算法是Θ(g(n))，这意味着当n(输入大小)变大时，算法的运行时间与g(n)成正比。 如果一个算法是O(g(n))，这意味着当n变大时，算法的运行时间最多与g(n)成正比。

通常，当人们谈论O(g(n))时，他们实际上指的是Θ(g(n))，但从技术上讲，这是有区别的。

更多的技术:

O(n)表示上界。Θ(n)表示紧绑定。 Ω(n)为下界。

F (x) = Θ(g(x)) iff F (x) = O(g(x))和f(x) = Ω(g(x))

基本上，当我们说一个算法是O(n)时，它也是O(n2)， O(n1000000)， O(2n)，…但是Θ(n)算法不是Θ(n2)算法。

事实上，由于f(n) = Θ(g(n))意味着n足够大，对于c1和c2的某些值，f(n)可以被限制在c1g(n)和c2g(n)之间，即f的增长速度渐近等于g: g可以是f的下界和上界。这直接意味着f也可以是g的上界和下界。因此,

F (x) = Θ(g(x)) iff g(x) = Θ(F (x))

类似地，要显示f(n) = Θ(g(n))，就足以显示g是f的上界(即f(n) = O(g(n)))， f是g的下界(即f(n) = Ω(g(n))，这与g(n) = O(f(n))完全相同)。简洁,

f (x) =Θ(g (x))敌我识别f (x) = O (g (x))和g (x) = O (f (x))

也有little-oh和little-omega (ω)符号表示函数的松散上界和松散下界。

总结:

f(x) = O(g(x)) (big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x). f(x) = Ω(g(x)) (big-omega) means that the growth rate of f(x) is asymptotically greater than or equal to the growth rate of g(x) f(x) = o(g(x)) (little-oh) means that the growth rate of f(x) is asymptotically less than the growth rate of g(x). f(x) = ω(g(x)) (little-omega) means that the growth rate of f(x) is asymptotically greater than the growth rate of g(x) f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)

要了解更详细的讨论，您可以在维基百科上阅读定义，或参考Cormen等人撰写的经典教科书《算法介绍》(Introduction to Algorithms)。

一个是大O

一个是大Theta

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

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

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

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

是一种表示特殊情况的简写方式 O和是一样的。

因此，如果有人声称Theta是表达式q，那么他们也必然声称大O是表达式q, Omega是表达式q。

粗糙的类比:

如果: Theta说，那个动物有5条腿 然后是: 大O是正确的(“那个动物的腿少于或等于5条。”) 而且 Omega是正确的(“那个动物有超过或等于5条腿。”)

这只是一个粗略的类比，因为表达式不一定是特定的数字，而是不同数量级的函数，如log(n)， n, n²，(等等)。

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、大θ和大Ω从定义上看是不同的，但在我们的口中和大脑中却是一样的。