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

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

我读到过它的意思是紧束缚,但那是什么意思呢?


当前回答

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

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

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

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

其他回答

大符号:

伙计,别搞砸了!!

如果我们有一个正值函数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)的增长率。

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

我希望这是你想在经典CLRS(第66页)中找到的东西:

我不知道为什么没有简单的答案来解释大theta(似乎这就是问题),所以它就在这里

大Theta是值的范围或精确值(如果大O和大Omega相等),函数所需的操作将在该范围内增长