0

如何证明这一点:

x^7 = O(x^10)
x^10 = O(x^7)?

我无法证明这个说法。

4

1 回答 1

2

让我们看一下大O符号的定义。

f ∈ O(g) <=> (∃ x) (∃ c > 0) (∀ y > x) (|f(y)| <= c⋅|g(y)|)

右手边可以表述为“商f/g有界足够大x”。

因此,为了证明f ∈ O(g),查看商,选择一个(较大的)x并尝试找到一个界限。对于第一种情况,商是

x⁷ / x¹⁰ = 1/x³

一个界限x ≥ 1是显而易见的。

要反驳f ∈ O(g),请查看商并证明它在每个区间上假定任意大模值[x, ∞)。假设一个任意的c > 0,并证明对于任意的x,存在一个y > xwith |f(y)/g(y)| > c

这应该给出足够的提示。

如果不是:x³ > c对于x ≥ c+1.

于 2012-11-13T21:26:51.570 回答