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