我很困惑大O和大符号之间的区别。
我知道大O是上界，大Omega是下界，但大Ө (theta)到底代表什么?
我读到过它的意思是紧束缚，但那是什么意思呢?
当前回答
大符号:
伙计，别搞砸了!!
如果我们有一个正值函数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)的增长率。
其他回答
大符号:
伙计，别搞砸了!!
如果我们有一个正值函数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²)
我希望这是你想在经典CLRS(第66页)中找到的东西:
首先是理论
大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
希望能解释清楚!!
我不知道为什么没有简单的答案来解释大theta(似乎这就是问题)，所以它就在这里
大Theta是值的范围或精确值(如果大O和大Omega相等)，函数所需的操作将在该范围内增长
