有谁知道如何执行这样的计算示例：
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或者
O(n^2) * THETA(n) * OMEGA(n^3) = ?
一般来说，如何添加和乘以不同的渐近符号？
问问题
1674 次
3 回答
5
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Ω
然而，这三个在一起，甚至只是Oand Ω，让你一无所知，因为既不O也不Ω暗示关于另一个的任何事情。
于 2011-10-11T22:26:28.843 回答
4
你不能。假设你知道a > 0和b < 10。那么你没有关于a+b. 它可以是任何东西。
Big-O 和 Big-Omega 对函数的作用类似。
于 2011-10-11T22:49:22.010 回答
1
虽然我的上述答案对于一般函数和界限是正确的，但在计算机科学中，我们通常只考虑正函数。因此，在您的第一个示例中，我们有：
O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)
这源于假设函数都是正的。也就是说，所有函数都是Omega(1).
于 2011-10-12T19:50:45.653 回答