我们刚刚开始在课堂上学习大O。我理解这样一个一般概念：如果存在两个常数 c,k，那么对于所有 x>k |f(x)|<=c|g(x)| ， f(x) 是 g(x) 的大 o 。我有一个问题是否需要我们包含 <= 来签名，或者是否只需将 <= 就足够了？符号？
例如：
假设f(x)=17x+11，我们要证明这是O(x^2)。
然后，如果我们取 c=28 且 x>k=1，我们就知道 17x+11<=28x^2。因此，既然我们知道 x 将始终大于 1，这意味着 28x^2 将始终大于 17x+11。那么，我们真的需要包含等号（<=）还是只写（<）就可以了？
提前致谢。
We just started learning big-o in class. I understand the general concept that f(x) is big-o of g(x) if there exists two constants c,k such that for all x>k |f(x)|<=c|g(x)|. I had a question whether or not it is required that we include the <= to sign or whether it is just sufficient to put the < sign?
For example:
suppose f(x)=17x+11 and we are to prove that this is O(x^2).
Then if we take c=28 and x>k=1 we know that 17x+11<=28x^2. So since we know that x will always be greater than 1 this implies that 28x^2 will always be greater than 17x+11. So, do we really need to include the equal sign (<=) or is it okay if we just write (<)?
Thanks in advance.
发布评论
评论（5）
来自 |f (x)| ≤ c |g (x)|对于某些实值c，可以得出|f (x)| < (c + e) |g (x)|对于所有e> 0.
由此可见，存在 c' = (c + e) 使得 |f ( x)| < c' |g (x)|，因此您可以使用 而不是 ≤。
更实际的是，如果你能证明 |f (x)| < c |g (x)|，≤ 部分很简单。
From |f (x)| ≤ c |g (x)| for some real-valued c, it follows that |f (x)| < (c + e) |g (x)| for all e > 0.
From that it follows that there exists c' = (c + e) such that |f (x)| < c' |g (x)|, so you can use < instead of ≤.
More practically, if you can prove |f (x)| < c |g (x)|, the ≤ part follows trivially.
如果您显示 x < y 那么你也显示了 x <= y。所以这没有什么区别。
If you have shown x < y then you have also shown x <= y. So it makes no difference.
我认为，您在这里问的问题有两个略有不同的问题：
如果您可以演示
c和k，使得对于所有x > ； k|f(x)| <= c|g(x)|，那么简单地说，您也演示了c和k，这样对于所有<代码>x> k|f(x)| < c|g(x)|。因此，显示<就足够了，但是：正如您所说，能够说出
的实际要求f(x) = O(g(x))是找到一个c和k使得对于所有x > k|f(x)| <= c|g(x)|。如果我们能做的最好的事情就是找到一个c和k，这样对于所有x > k|f(x)| = c|g(x)|，那么我们还没有满足您的<条件，但我们已经做了足够的工作来显示f( x) = O(g(x))。因此，显示<并不是必要There are two slightly different things you're asking here, I think:
If you can demonstrate a
candksuch that for allx > k|f(x)| <= c|g(x)|, then trivially you have also demonstrated acandksuch that for allx > k|f(x)| < c|g(x)|. So showing<is sufficient, but:As you've stated, the actual requirement for being able to say
f(x) = O(g(x))is to find acandksuch that for allx > k|f(x)| <= c|g(x)|. If the best we can do is find acandksuch that for allx > k|f(x)| = c|g(x)|, then we haven't met your<condition, but we have done enough to showf(x) = O(g(x)). So showing<is not necessary您不能将 <= 替换为 <在定义中。
任何经常无限为零的函数 f 都是 O(f)，但如果将 <= 替换为 <，则不是。
例如，如果 x 是奇数，则令 f(x) = x；如果 x 是偶数，则令 f(x) = x。那么 f 是 O(f)，因为对于所有 x，f(x) <= f(x)。然而，不存在满足 f(x) < 的 c。 cf(x) 对于所有大的 x，因为对于所有偶数 x 两边都是 0。
You can't replace <= with < in the definition.
Any function f that's infinitely often zero is O(f), but not if you replace <= with <.
For example, let f(x) = x if x is odd, 0 if x is even. Then f is O(f) because f(x) <= f(x) for all x. However, there's no c such that f(x) < cf(x) for all large x, because both sides are 0 for all even x.
使用
<代替≤是不的，尽管很明显它们在某些情况下是相同的，因为≤是 Big-O 表示法定义的一部分。另一方面，定义：
0 ≤ f(n) < cg(n)属于不同的类（Little-o 表示法），该类包含在 Big-O 类中It is not ok to use
<instead of≤, although it is obvious that they are -in some cases- identical, because≤is part of the Big-O notation definition.On the other hand, the definition:
0 ≤ f(n) < cg(n)belongs to a different class (the Little-o notation) which is included in the Big-O class