不同渐近符号的相乘和相加
有谁知道如何进行这样的计算 示例：
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或
O(n^2) * THETA(n) * OMEGA(n^3) ) = ?
一般来说，如何对不同的渐近符号进行加法和乘法？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
有谁知道如何进行这样的计算 示例：
O(n^2) + THETA(n) + OMEGA(n^3) = ?
或
O(n^2) * THETA(n) * OMEGA(n^3) ) = ?
一般来说，如何对不同的渐近符号进行加法和乘法？
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
O给出上限；Ω给出下限；θ给出渐近界；维基百科有一个很好的图表来解释这些。
因此，这些在一般情况下确实没有可比性。
对于第一个案例，
我们首先处理
O。第一项告诉我们O(n^2)，第二项告诉我们O(n)。仅基于这两个，我们就知道到目前为止我们有O(n^2)作为上限。然而，第三项没有告诉我们任何关于上限的信息！所以我们真的无法得出关于O的任何结论。这里的要点是，
O和θ只提供有关O的信息，以及Ω和θ 的信息仅向您提供有关Ω的信息。这是因为θ(g(n))意味着O(g(n))和Ω(g(n))，所以我们可以将θ更改为O和Ω中适合给定分析的那个。然而，这三者在一起，甚至只是
O和Ω，都会让你一无所知，因为O和Ω都不暗示关于对方的任何事情。Ogives an upper bound;Ωgives a lower bound;Θgives an asymptotic bound;Wikipedia has a nice chart to explain these.
Therefore these really aren't comparable in general.
For your first case,
Let's first tackle
O. The first term tells usO(n^2), and the second term tells usO(n). Based on just these two, we know so far we haveO(n^2)for an upper bound. However, the third term tells us nothing whatsoever about an upper bound! So we really cannot conclude anything aboutO.The point here is that
OandΘgives you information aboutOonly, andΩandΘgives you information aboutΩonly. This is becauseΘ(g(n))implies bothO(g(n))andΩ(g(n)), so we can changeΘinto whichever ofOandΩis appropriate for the given analysis.However, the three together, or even just
OandΩ, leaves you clueless since neitherOnorΩimplies anything about the other.你不能。假设您知道
a > 0和b < 10..那么你就没有关于a+b的信息。它可以是任何东西。Big-O 和 Big-Omega 的功能类似。
You can't. Suppose you know that
a > 0andb < 10. Then you have no information abouta+b. It could be anything.Big-O and Big-Omega act similarly for functions.
虽然我的上述答案对于一般函数和界限是正确的，但在计算机科学中我们通常只考虑正函数。因此，在你的第一个例子中，我们有：
这源于函数都是正的假设。也就是说，所有函数都是
Omega(1)。While my above answer is correct for general functions and bounds, in computer science we typically consider only positive functions. Thus in your first example, we have:
This stems from the assumption that the functions are all positive. That is, all functions are
Omega(1).