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

Question

大欧米茄（Ω）定义是这个。

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

这里有一个定理。

我想证明这一点，而不使用 'limit'。我可以找到易于使用的限制。

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

标签： algorithmmath

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).