大的Ө符号到底代表什么?

我很困惑大O和大符号之间的区别。

我知道大O是上界，大Omega是下界，但大Ө (theta)到底代表什么?

我读到它的意思是< em >紧束缚< / em >，但这是什么意思?

188242 次浏览
小开
最佳答案

这意味着在给定的函数中算法是大o和大。

例如，如果它是Ө(n)，那么存在某个常量k，使得你的函数(运行时，无论什么)对于足够大的n大于n*k，并且存在另一个常量K，使得你的函数对于足够大的n小于n*K。

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

如果k < K和n足够大，则n*k < f(n) < n*K

小开

首先让我们理解大O，大和大是什么。它们都是函数的集。

大O给出的是上界渐近绑定，而大给出的是下界。大Theta两者都有。

所有Ө(f(n))的东西也是O(f(n))，但不是反过来。
如果T(n)同时在O(f(n))和Omega(f(n))中，则认为它在Ө(f(n))中。
在集合术语中，__ABC1是__ABC2和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)。另一方面，big-Omega表示存在一个常量C2，使得T(n) >= C2 * f(n)))。

不要混淆!

不要与最差、最佳和平均情况分析混淆:所有三个(Omega, O, Theta)符号都是不，与算法的最佳、最差和平均情况分析相关。每一个都可以应用于每一个分析。

我们通常用它来分析算法的复杂性(类似于上面的归并排序示例)。当我们说“算法A是__abc0”时，我们真正的意思是“最坏的__abc4案例分析下的算法复杂度是__abc0”。-意思是-它的规模“相似”;(或者正式地说，不会比f(n)差)函数。

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

嗯，有很多原因，但我认为最重要的是:

  1. 确定确切的复杂度函数要困难得多，因此我们“妥协”;大o /大theta符号，这在理论上已经足够丰富了。
  2. 操作的确切数量也是平台的依赖。例如，如果我们有一个16个数字的向量(列表)。需要多少行动?答案是:视情况而定。一些cpu允许向量加法，而另一些不允许，因此答案因不同的实现和不同的机器而异，这是一个不希望看到的属性。然而，大o符号在机器和实现之间更加稳定。
为了说明这个问题，请看下面的图表: enter image description here

很明显，f(n) = 2*n是"更糟"f(n) = n。但是这个区别并不像另一个函数那么明显。我们可以看到f(n)=logn很快地比其他函数低得多，而f(n) = n^2很快地比其他函数高得多。
因此，由于上述原因，我们“忽略”;常数因子(图中为2*)，只取大o符号。

在上面的例子中，f(n)=n, f(n)=2*n将同时在O(n)和Omega(n)中，因此也将在Theta(n)中。
另一方面- f(n)=logn将在O(n)中(它是"better";而不是f(n)=n)，但不会在Omega(n)中-因此也不会在Theta(n)中。
对称地，f(n)=n^2将在Omega(n)中，但不在O(n)中，因此-也不是Theta(n)。

__abc0通常，但不总是。当分析类(最差，平均和最佳)缺失时，我们真正的意思是最坏的情况。

小开

θ(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 & lt; = c1 (g (n)) & lt; = f (n) & lt; = c2 (g (n))为所有n > = n1} < / em > < / p >

当我们说f(n)=c2(g(n))或f(n)=c1(g(n))时，它表示渐近紧界。

O (n):它只给出上界(可能紧也可能不紧)

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

前女友:界2*(n^2) = O(n^2)渐近紧，而界2*n = O(n^2)不渐近紧。

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

O(n) &之间差异显著;O (n)等于f(n)小于cg(n) >=n1，但不等于O(n).

前女友: 2*n = o(n^2)，但是2*(n^2) != o(n^2)

小开

大符号:

伙计，别搞砸了!!

如果我们有一个正值函数f(n)和g(n)取一个正值参数n，那么ϴ(g(n))定义为{f(n):存在常数c1,c2和n1对于所有n>=n1}

其中c1 g(n)<=f(n)<=c2 g(n)

让我们举个例子:

让f (n) = .

g (n) = .

C1 =5 c2=8 n1=1

在所有的表示法中，ϴ表示法对函数的增长率给出了最好的直观印象，因为它给了我们一个不像big-oh和big -omega的紧边界 分别给出上界和下界。

ϴ告诉我们g(n)与f(n)非常接近，g(n)的增长率尽可能接近f(n)的增长率。

see the image to get a better intuition

小开

我希望这是你可能想在经典clr(第66页)中找到的: enter image description here < / p >

小开

首先是理论

  1. 大O =上限O(n)

  2. Theta =阶函数- Theta (n)

  3. ω = Q符号(下限)Q(n)

为什么人们如此困惑?

在许多博客&这句话是怎样强调的呢

“This is Big O(n^3)”;等。

和人们经常混淆喜欢天气

O(n) == theta(n) == Q(n)

但是值得记住的是它们只是名字为O和amp的数学函数;ω

所以它们有相同的多项式通式，

让,

F (n) = 2n4 + 100n2 + 10n + 50，

g(n) = n4，则g(n)为以函数为输入，返回最大幂变量的函数，

相同的f(n) &g(n)表示以下所有解释

大O(n) -提供上限

大O(n4) = 3n4，因为3n4 >2陶瓷

3n4是大O(n4)就像f(x) = 3x一样

陶瓷在这里扮演了x的角色，

用x'代替n4，那么大O(x') = 2x'，现在我们都很满意一般概念是

0≤f(n)≤O (x ')

O(x') = cg(n) = 3n4

把价值,

0≤2n4 + 100n2 + 10n + 50≤3n4

3n4是我们的上界

大ω (n) -提供下界

Theta(n4) = cg(n) = 2n4因为2n4≤我们的例子f(n)

2n4是(n4)的值

0≤cg(n)≤f(n)

0≤2n4≤2n4 + 100n2 + 10n + 50

2n4是我们的下界

Theta(n) -提供紧边界

计算结果表明，天气下界与上界相似，

情况1).上界与下界相似

if Upper Bound is Similar to Lower Bound, The Average Case is Similar


Example, 2n4 ≤ f(x) ≤ 2n4,
Then Theta(n) = 2n4

情况2).如果上界与下界不相似

In this case, Theta(n) is not fixed but Theta(n) is the set of functions with the same order of growth as g(n).


Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Theta(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3

希望能解释清楚!!


提交答案