algorithm - 如何证明一般多项式情况下的 Big-omega？

Question

大欧米茄(Ω)的定义是这样的。

函数 f(n) = Ω(g(n)) ，当且仅当存在正常数 c 和 n0 使得 f(n) >= c*g(n) 对于所有 n，n>=n0.

这里有一个定理。

我想证明这一点，不使用“极限”。我可以找到易于使用的限制。

我想了很多时间并在互联网上搜索，但我找不到它。只是限制...请帮助我!

Answer 1

|Am.n^m + Am-1.n^m-1 + … A1.n + A0| <= n^m (|Am| + |Am-1|/n + … + |A1|/n^m-1 + |A0|/n^m)

选择一些 n0并设置

c = (|Am| + |Am-1|/n0 + … + |A1|/n0^m-1 + |A0|/n0^m).

这保证

n >= n0 implies |f(n)| <= c.n^m

因为c(n) < c(n0) .