如何证明这一点:
x^7 = O(x^10)
x^10 = O(x^7)?
我无法证明这个说法。
让我们看一下大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 > x
with |f(y)/g(y)| > c
。
这应该给出足够的提示。
如果不是:
x³ > c
对于x ≥ c+1
.