大Ө符号究竟代表什么？

Question

我真的很困惑大O,大欧米茄和大Theta符号之间的差异.

我知道大O是上界,大欧米茄是下界,但大Ө(theta)究竟代表什么？

我读过它意味着紧张,但这意味着什么？

Answer 1

首先让我们了解大O,大Theta和大欧米茄是什么.他们都是集的功能.

大O给出上渐近界限,而大欧米茄给出下界.Big Theta给出了两者.

一切,这是?(f(n))也O(f(n)),而不是周围的其他方法.
T(n)据说?(f(n))如果它在里面O(f(n))和里面都存在Omega(f(n)).
在套的术语,?(f(n))是相交的O(f(n))和Omega(f(n))

例如,合并排序最坏情况是O(n*log(n))和Omega(n*log(n))- 并且因此也是?(n*log(n)),但它也是O(n^2),因为n^2渐近"大"而不是它.但是,它不是 ?(n^2),因为算法不是Omega(n^2).

更深入的数学解释

O(n)是渐近上界.如果T(n)是O(f(n)),则意味着从某个n0,有一个恒定的C,使得T(n) <= C * f(n).另一方面,大欧米茄说有一个常数C2这样的T(n) >= C2 * f(n))).

不要混淆!

不要与最差,最好和平均情况分析混淆:所有三个(欧米茄,O,西塔)符号是不相关的算法最好,最差,平均情况分析.这些中的每一个都可以应用于每个分析.

我们通常用它来分析算法的复杂性(比如上面的合并排序示例).当我们说"算法A是O(f(n))"时,我们真正的意思是"最差^1个案例分析下的算法复杂性O(f(n))" - 意思是 - 它缩放"相似"(或正式,不差)函数f(n).

为什么我们关心算法的渐近界？

嗯,有很多原因,但我相信其中最重要的是:

1. 确定确切的复杂度函数要困难得多,因此我们在大O/big-Theta符号上"妥协",这在理论上足够丰富.
2. 操作的确切数量也取决于平台.例如,如果我们有一个16个数字的向量(列表).需要多少操作？答案是:这取决于.一些CPU允许向量添加,而其他CPU则不允许,因此答案在不同的实现和不同的机器之间变化,这是不期望的属性.然而,大O符号在机器和实现之间更加恒定.

要演示此问题,请查看以下图表:

很明显,它f(n) = 2*n比"更糟糕" f(n) = n.但差异并不像其他功能那么激烈.我们可以看到,它f(n)=logn很快就会比其他功能低得多,而且f(n) = n^2很快就会比其他功能高得多.
所以 - 由于上述原因,我们"忽略"常数因子(图中的2*),并且只采用big-O表示法.

在上面的例子中,f(n)=n, f(n)=2*n两者都在O(n)和Omega(n)- 并且因此也将在Theta(n).
另一方面 - f(n)=logn将进入O(n)(它比"更好" f(n)=n),但不会进入Omega(n)- 因此也不会进入Theta(n).
对称的,f(n)=n^2将在Omega(n),但不在,O(n)因此 - 也不是Theta(n).

¹通常,虽然并非总是如此.当分析类(最差,平均和最佳)缺失时,我们的确意味着最坏的情况.

Answer 2

这意味着该算法在给定函数中既是大O又是大Omega.

例如,如果是?(n),则存在一些常量k,使得您的函数(运行时,无论如何)大于n*k足够大的函数n,以及一些其他常量K,使得您的函数小于n*K足够大的函数n.

换句话说,对于足够大n,它夹在两个线性函数之间:

对于k < K和n足够大,n*k < f(n) < n*K

Answer 3

THETA(N):一个函数f(n)属于Theta(g(n)),如果存在正的常数c1并且c2使得f(n)能够之间被夹c1(g(n))并c2(g(n)).即它既给出了上限,也给出了下限.

Theta(g(n))= {f(n):存在正常数c1,c2和n1,使得0 <= c1(g(n))<= f(n)<= c2(g(n))对于所有n> = n1}

当我们说f(n)=c2(g(n))或f(n)=c1(g(n))它代表渐近紧束缚.

O(n):它只给出上限(可能或可能不紧)

O(g(n))= {f(n):存在正常数c和n1,使得对于所有n> = n1,0 <= f(n)<= cg(n)

例如:边界2*(n^2) = O(n^2)是渐近紧的,而边界2*n = O(n^2)不是渐近紧的.

o(n):它只给出上限(从不紧束)

对于所有n> = n1,O(n)和o(n)之间的显着差异是f(n)小于cg(n),但是与O(n)中的不相等.

例如:2*n = o(n^2)但是2*(n^2) != o(n^2)

Answer 4

我希望这是您可能想在经典CLRS（第 66 页）中找到的内容：