为什么两个函数的比值的限制表示一个紧密的界限？

Question

我的算法教科书有以下节选：

​

​

我很难理解它们是否存在紧界，如果两个函数之比的极限为n，则为常数。具体来说，他们从哪里得到0.5c和2c？

My thoughts:紧界表示函数T(n)在f(n)上有界，下面有g(n)的界。现在假设T(n) = n^2，f(n) = an^2，g(n) = bn^2，那么我们知道T(n)的紧界是Theta(n^2)，因为f(n)和g(n)的比值是常数，a/b。

Answer 1

语句"lim w(x) = c as x -> infinity“的正式定义如下：

对于所有的epsilon > 0，都存在一些N，因此对于所有x > N、|w(x) - c| < epsilon都是如此。

现在我们被赋予lim f(x) / g(x) = c作为x -> infinity，和c > 0。然后是c / 2 > 0。

考虑一下epsilon = c / 2。然后是epsilon > 0，所以存在一些N，对于所有的x > N，我们都有|f(x) / g(x) - c| < epsilon = c / 2。这相当于说-c/2 < f(x) / g(x) - c < c / 2，这又相当于说c/2 < f(x) / g(x) < 3c / 2。

既然对于所有的x > N，我们都有c/2 < f(x) / g(x)，那么(因为我们总是假定f和g是正值的)，我们可以得出结论，对于所有的x > N，f(x) > g(x) c/2。因此，我们已经证明了f(x) = Omega(g(x))。

同样的，因为对于所有的x > N，我们都有f(x) / g(x) < 3/2 c，我们看到了对于所有的x > N，f(x) < g(x) (3/2 c)。然后我们证明了f(x) = O(g(x))。

因此，我们看到了f(x) = Theta(g(x))，视需要而定。