有人知道如何进行这样的计算吗例子:
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或
O(n^2) * THETA(n) * OMEGA(n^3) = ?
一般来说，如何将不同的渐近符号相加和相乘?
O给出上界;
Ω给下界,
Θ给出了渐近界;
维基百科有一个很好的图表来解释这些。
因此，它们通常是不可比较的。
对于第一个案例，
O(n^2) + Θ(n) + Ω(n^3)
让我们先解决O。第一项告诉我们O(n^2)，第二项告诉我们O(n)。根据这两个，我们知道上界是O(n^2)。然而，第三项没有告诉我们任何关于上界的信息!所以我们真的不能得出任何关于O的结论。
这里的重点是O和Θ只给你关于O的信息，Ω和Θ只给你关于Ω的信息。这是因为Θ(g(n))意味着O(g(n))和Ω(g(n))，所以我们可以将Θ更改为O和Ω中适合给定分析的任何一个。
然而，这三个放在一起，甚至只是O和Ω，让你毫无头绪，因为O和Ω都没有暗示任何关于对方的信息。
你不能。假设您知道a > 0和b < 10。那么你没有关于a+b的信息。可以是任何东西
Big-O和Big-Omega对于函数的作用类似。
虽然我上面的答案对一般函数和界是正确的，但在计算机科学中，我们通常只考虑正函数。因此，在第一个示例中，我们有:
O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)
这源于函数都是正的假设。也就是说，所有函数都是Omega(1)。