大符号:

伙计，别搞砸了!!

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

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

让我们举个例子:

让f (n) = 5 n ^ 2 + 2 n + 1

g (n) = n ^ 2

C1 =5 c2=8 n1=1

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

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

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

大O给出了渐近上界，而大给出了下界。大Theta两者都有。

所有Ө(f(n))也是O(f(n))，但不是反过来。 T(n)在Ө(f(n))，如果它同时在O(f(n))和(f(n))中。在集合术语中，Ө(f(n))是O(f(n))和(f(n))的交集

例如，归并排序最坏的情况是O(n*log(n))和Omega(n*log(n)) -因此也是Ө(n*log(n))，但它也是O(n²)，因为n²渐近地“大于”它。然而，它不是Ө(n²)，因为算法不是Omega(n²)。

更深入的数学解释

O(n)是渐近上界。如果T(n)是O(f(n))，这意味着从某个n0开始，存在一个常数C，使得T(n) <= C * f(n)。另一方面，大表示存在一个常数C2使得T(n) >= C2 * f(n)))。

不要混淆!

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

我们通常使用它来分析算法的复杂性(如上面的归并排序示例)。当我们说“算法A是O(f(n))”时，我们真正的意思是“在最坏情况下分析的算法复杂度是O(f(n))”-意思是-它的缩放“类似”(或正式地，不差于)函数f(n)。

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

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

It is much harder to determine the exact complexity function, thus we "compromise" on the big-O/big-Theta notations, which are informative enough theoretically. The exact number of ops is also platform dependent. For example, if we have a vector (list) of 16 numbers. How much ops will it take? The answer is: it depends. Some CPUs allow vector additions, while other don't, so the answer varies between different implementations and different machines, which is an undesired property. The big-O notation however is much more constant between machines and implementations.

为了说明这个问题，请看下面的图表:

很明显，f(n) = 2*n比f(n) = n“更糟糕”。但差异并不像另一个函数那样剧烈。我们可以看到f(n)=logn很快地比其他函数低很多，而f(n)= n²很快地比其他函数高很多。 因此，由于上述原因，我们“忽略”常数因子(图中为2*)，只采用大o符号。

在上面的例子中，f(n)=n, f(n)=2*n将在O(n)和(n)中，因此也在(n)中。 另一方面- f(n)=logn将在O(n)中(它比f(n)=n“更好”)，但不会在(n)中-因此也不会在(n)中。 对称地，f(n)=n²在(n)中，但不在O(n)中，因此-也不是(n)

---

1通常是这样，虽然不总是这样。当分析类(最差、平均和最佳)缺失时，我们实际上是指最坏的情况。

Theta(n):函数f(n)属于Theta(g(n))，如果存在正常数c1和c2，使得f(n)可以夹在c1(g(n))和c2(g(n))之间。也就是说，它给出了上界和下界。

(g(n)) = {f(n)存在正常数c1 c2 n1使得 0<=c1(g(n))<=f(n)<=c2(g(n)) for all n>=n1}

当我们说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²)= O(n²)是渐近紧的，而界2*n = O(n²)则不是渐近紧的。

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

O(n)和O(n)的显著区别是f(n)小于cg(n) 对于所有n>=n1，但不等于O(n)。

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

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

例如，如果它是Ө(n)，那么有一个常数k，使得你的函数(运行时，无论什么)在足够大的n下大于n*k，还有一个常数k，使得你的函数在足够大的n下小于n*k。

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

当k < k且n足够大时，n*k < f(n) < n*k

首先是理论

大O =上限O(n) =阶函数- (n) = Q符号(下限)Q(n)

为什么人们如此困惑?

在许多博客和书籍中，这句话是如何被强调的

这是O(n^3)等等。

和人们经常混淆喜欢天气

O(n)

但值得记住的是，它们只是名字为O、Theta和Omega的数学函数

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

Let,

f（n） = 2n4 + 100n2 + 10n + 50，

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

对于下面的所有解释，f(n)和g(n)相同

大O(n) -提供上限

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

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

N4在这里扮演x的角色，

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

所以 0 ≤ f（n） ≤ O（x'）

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

把价值,

0≤2n4 + 100n2 +他+ 50≤3n4

3n4是我们的上界

大ω (n) -提供下界

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

2n4是(n4)的值

因此，0≤cg(n)≤f(n)

0≤2n4≤2n4 + 100n2 +他+ 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

希望能解释清楚!!

大符号:

伙计，别搞砸了!!

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

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

让我们举个例子:

让f (n) = 5 n ^ 2 + 2 n + 1

g (n) = n ^ 2

C1 =5 c2=8 n1=1

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

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