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

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

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

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

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

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

使用限制

让我们考虑所有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是表达式q，那么他们也必然声称大O是表达式q, Omega是表达式q。

粗糙的类比:

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

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

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

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

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

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

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