在试图理解 Theta 和 O 符号之间的区别时,我遇到了以下声明:
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
但我不理解这个。书里用数学方式解释,但过于复杂,当我真的无法理解时阅读起来非常枯燥。
有人能用简单而又有效的例子来解释两者之间的区别吗?
大O表示的是渐进上界,而大Theta同时也提供了一个下界。
所有的Theta(f(n))
都是O(f(n))
,但反过来则不成立。
如果T(n)
既是O(f(n))
又是Omega(f(n))
,那么它被称为Theta(f(n))
因此,大Theta符号比大O符号更具信息量,如果我们可以说某个东西是大Theta,通常会更好。然而,证明某个东西是大Theta比证明它是大O要困难得多。
例如,归并排序既是O(n*log(n))
,也是Theta(n*log(n))
,但它也是O(n2),因为n2在渐进意义下“更大”。但是,它不是Theta(n2),因为该算法不是Omega(n2)。
Omega(n)
是一种渐进下限。如果 T(n)
是 Omega(f(n))
,则意味着从某个特定的 n0
开始,存在一个常数 C1
,使得 T(n) >= C1 * f(n)
。而大O表示存在一个常数 C2
,使得 T(n) <= C2 * f(n))
。Omega(n)
是渐近下界。如果 T(n)
是 Omega(f(n))
,意味着从某个 n0
开始,存在一个常数 C
,使得 T(n) >= C * f(n)
(其中大O表示存在一个常数 C2
,使得 T(n) <= C2 * f(n)
)。Omega、O、Theta 这三者只提供渐近信息(“对于大输入”),Big O 提供上界,大 Omega 提供下界,而大 Theta 两者都提供。请注意,此符号与算法的最佳/最坏/平均情况分析无关。每个分析都可以应用这三种符号。 - amitTheta(n ^ 2)
函数是O(n ^ 2)
并不是错误的 - 因此维基百科的声明 - 虽然不准确,但并不是错误的。 - amit我将直接引用 Knuth 的《计算机程序设计艺术》第一卷 - 第110页(我有印度版)。我建议阅读107-110页(1.2.11 节“渐近表示”)。
人们经常会混淆 O表示法,认为它给出了精确的增长顺序;他们使用它时好像它同时指定了下限和上限。例如,一个算法可能因其运行时间为O(n^2)而被称为低效率。但是,O(n^2)的运行时间并不一定意味着运行时间不是O(n)
在第107页中,
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^4) 和
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^3) 和
1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)
大 O 表示法用于估算。它可以让您使用 ~ 替换等号 = 符号。在上面的例子中,对于非常大的n,我们可以确定该数量将保持在 n^4、n^3 和 (1/3)n^3 + n^2 [而不仅仅是 n^2] 以下。
大 Omega 表示法用于下限 - 一个具有Omega(n^2)的算法对于大N来说不会像O(N logN)一样高效。但是,我们不知道在哪些N值处(在这个意义上,我们只知道近似值)。
大 Theta 表示法用于精确的增长顺序,既有下限也有上限。
if n is odd f(n) = n^3
if n is even f(n) = n^2
来自CLRS
如果存在正常数c1和c2,使得对于足够大的n,函数f(n)可以被"c1g(n)"和"c2g(n)"夹在中间,则函数f(n)属于集合Θ(g(n))。
AND
O(g(n)) = {f(n):存在正常数c和n0,使得对所有n ≥ n0有0 ≤ f(n) ≤ cg(n)}。
AND
Ω(g(n)) = {f(n):存在正常数c和n0,使得对所有n ≥ n0有0 ≤ cg(n) ≤ f(n)}。
f(n)的上界是n^3。因此,我们的函数f(n)显然是O(n^3)。
但它是否是Θ(n^3)?
对于f(n)属于Θ(n^3),它必须夹在两个函数之间,一个形成下界,另一个形成上界,两个函数都以n^3增长。尽管上界很明显,但下界不能是n^3。事实上,下界是n^2;f(n)为Ω(n^2)。
来自CLRS
对于任意两个函数f(n)和g(n),当且仅当f(n) = O(g(n)) 且f(n) = Ω(g(n)) 时,我们有f(n) = Θ(g(n))。
因此,f(n)不属于Θ(n^3),但它属于O(n^3)和Ω(n^2)。
Theta(f(n))
,相反,我们会说它在最坏情况下是Theta(f(n))
(例如),如果最坏情况既是O(f(n))
又是Omega(f(n))
,而不管最好情况的行为如何。 - amitTheta(n^2)
,因为你可以在最坏情况下的输入(反向排序数组)上给出需要多少操作的下限,并且它将与元素数量的平方成比例。在没有指明分析方式的情况下谈论算法的复杂度是没有意义的。通常情况下,如果省略了分析,那么它隐含地意味着复杂度是在最坏情况分析下计算的。如果我们使用这个约定,插入排序是Theta(n^2)
[最坏情况分析隐含在这个说法中]。 - amit