给定两个函数，一个函数是另一个函数的大O吗？
我的问题涉及算法分析中的大哦符号。虽然 Big-Oh 看起来是一道数学题，但它在算法分析中非常有用。
假设两个函数定义如下：
- f(n) = 2( n 次方) 当 n 为偶数时
- f(n) = n 当 n 为奇数时
- g(n) = n 当 n 为偶数时
- g(n) = 2( n 次方）当 n 为奇数时。
对于以上两个函数，哪一个是其他的大哦？或者某个函数是否不是另一个函数的 Big-Oh。
谢谢！
My question refers to the big-Oh notation in algorithm analysis. While Big-Oh seems to be a math question, it's much useful in algorithm analysis.
Suppose two functions are defined below:
- f(n) = 2( to the power n) when n is even
- f(n) = n when n is odd
- g(n) = n when n is even
- g(n) = 2( to the power n) when n is odd.
For the above two functions which one is big-Oh of other? Or whether any function is not a Big-Oh of another function.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在这种情况下，
这是因为无论您选择什么常数 N 和 k，
In this case,
This is because no matter what constants N and k you pick,
Big-Oh 关系非常具体，因为一个函数在有限 n 之后总是大于另一个函数。
这是真的吗？如果是这样，请给出这样的
n。如果不是，你应该证明这一点。The Big-Oh relationship is quite specific in that one function is, after a finite n, always larger than the other.
Is this true here? If so, give such a
n. If not, you should prove it.通常 Big-O 和 Big-Theta 符号会混淆。
外行人的定义可能是 Big-O 意味着一个函数的增长速度与另一个函数一样快或更快，即给定足够大的 n，
f(n)<= k*g(n)其中 k 是某个常数。这意味着如果 f(x) = 2x^3，那么它就是 O(x^3)、O(x^4)、O(2^x)、O(x!) 等。Big-Theta 意味着一种功能的增长速度与另一种功能一样快，其中任何一种功能都无法“超越”另一种功能，或者，对于某些 k1 和 k2，
k1*g(n)<=f(n)<=k2*g(n)。用编程术语来说，这意味着这两个函数具有相同的复杂程度。如果 f(x) = 2x^3，那么它在 θ(x^3) 中，例如，如果 k1=1，并且 k2=3，则 1*x^31*x^32*x^3 < 3*x^3根据我的经验，每当程序员谈论 Big-O 时，讨论实际上都是关于 Big-θ，因为我们更关心尽可能快部分，比不快于部分。
也就是说，如果组合具有不同 θ 的两个函数，如您的示例所示，较大的函数 - (θ(2^n) - 吞没较小的 - θ(n)，因此
f和 < code>g 具有完全相同的 Big-O 和 Big-θ 复杂度。在这种情况下，这都是正确的，因为它们具有相同的复杂度，因此它们是 O 和 θ 彼此绑定的。
Usually Big-O and Big-Theta notations get confused.
A layman attempt at definition could be that Big-O means that one function is growing as fast or faster than another one, i.e. that given a large enough n,
f(n)<=k*g(n)where k is some constant. That means that if f(x) = 2x^3, then it is in O(x^3), O(x^4), O(2^x), O(x!) etc..Big-Theta means that one function is growing as fast as another one, with neither one being able to "outgrow" the other, or,
k1*g(n)<=f(n)<=k2*g(n)for some k1 and k2. In programming terms that means that these two functions have the same level of complexity. If f(x) = 2x^3, then it is in Θ(x^3), as for example, if k1=1, and k2=3,1*x^3 < 2*x^3 < 3*x^3In my experience whenever programmers are talking about Big-O, the discussion is actually about Big-Θ, as we are concerned more with the as fast as part more, than in the no faster than part.
That said, if two functions with different Θ's are combined, as in your example, the larger one - (Θ(2^n) - swallows the smaller - Θ(n), so both
fandghave the exact same Big-O and Big-Θ complexities. In this case, it's both correct thatso, as they have the same complexity, they are O and Θ bound by each other.