1

我们刚开始在课堂上学习big-o。我理解如果存在两个常数 c,k 使得对于所有 x>k |f(x)|<=c|g(x)|，f(x) 是 g(x) 的 big-o 的一般概念。我有一个问题，是否需要我们包含 <= 来签名，或者放置 < 符号是否就足够了？

例如：假设 f(x)=17x+11，我们要证明这是 O(x^2)。那么如果我们取 c=28 和 x>k=1，我们知道 17x+11<=28x^2。因此，由于我们知道 x 将始终大于 1，这意味着 28x^2 将始终大于 17x+11。那么，我们真的需要包含等号 (<=) 还是只写 (<) 就可以了？

提前致谢。

4

5 回答 5

2

从 | 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 )|, ≤ 部分紧随其后。

于 2011-02-02T15:35:09.283 回答
0

如果你显示了 x < y，那么你也显示了 x <= y。所以没有区别。

于 2011-02-02T15:35:14.857 回答
0
于 2015-01-29T14:40:50.900 回答
0

是否需要我们包含 <= 符号或者放置 < 符号是否足够？

我认为您在这里问的事情有两点略有不同：

  • 如果您可以为所有人证明 a cand ksuch that x > k |f(x)| <= c|g(x)|，那么您也很简单地为所有人证明了 a cand ksuch that x > k |f(x)| < c|g(x)|。所以显示<就足够了，但是：

  • 正如您所说，能够说的实际要求f(x) = O(g(x))是找到 a cand ksuch that for all x > k |f(x)| <= c|g(x)|。如果我们能做的最好的就是为所有人找到一个c和k这样的x > k |f(x)| = c|g(x)|，那么我们还没有满足你的<条件，但我们已经做了足够的事情来证明f(x) = O(g(x))。所以不需要展示_<

于 2011-02-03T08:52:15.447 回答
0

您不能在定义中将 <= 替换为 <。

任何经常为零的函数 f 都是 O(f)，但如果将 <= 替换为 < 则不是。

例如，如果 x 是奇数，则令 f(x) = x，如果 x 是偶数，则令 f(x) = x。那么 f 是 O(f)，因为对于所有 x，f(x) <= f(x)。然而，对于所有大的 x，不存在 f(x) < cf(x) 的 c，因为对于所有偶数 x，两边都为 0。

于 2015-01-29T14:29:43.540 回答