有时我看到Θ(n)中间有一个奇怪的Θ符号,有时只是O(n)。只是因为没人知道如何输入这个符号而懒惰打字,还是它有别的意思?


当前回答

简短说明:

如果一个算法是Θ(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)。

其他回答

简短说明:

如果一个算法是Θ(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符号....

使用限制

让我们考虑所有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和是一样的。

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


粗糙的类比:

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

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