使用极限方法证明一个函数是大的

Question

您好，我面临着证明函数是大 theta 元素的问题。题目如下：是4n^3+23n^2+1（是）Theta(n^3)的一个元素，证明你的答案。我的回答如下：基本上，我证明它在大 oh 和大 omega 中都存在，如果是这样的话，它也在 big theta 中。这个对吗？另外，使用极限证明给定函数在大 theta 中的最佳方法是什么？

Answer 1

在 Big-Omega 的计算中，您需要找到函数的极限除以 n³（这与您所做的相反）。由于它等于 4（显然小于无穷大），因此您的函数属于 Omega(n³).

Answer 2

为了显示 f(n) = 4n^3 + 23n^2 - 1 属于 Theta(n^3)，你必须将它限制在 k1.n^3 和 k2.n^3 之间，因为一些正常数 k1 和k2 当 n 足够大时（意思是 n >= n0 对于某个常数 n0）

让我们看看有无限制和有限制。

无限制

鉴于

1 < 23n^2

对于所有 n >= 1，我们得到

0 < 23n^2 - 1

因此

4n^3 = 4n^3 + 0
     < 4n^3 + 23n^2 - 1

因此，您可以k1 = 4。

现在是上限。

4n^3 + 23n^2 - 1 < 4n^3 + 23n^2
                 < 23n^3 + 23n^2
                 <= 23n^3 + 23n^3
                 = 46n^3

你可以选择 k2 = 46 和 n0 = 1。

有限制

lim f(n)/n^3 = lim 4 + 23/n - 1/n^3 = 4

因此，给定 epsilon > 0 存在 n0 这样

| f(n)/n^3 - 4 | < epsilon

为 n >= n0。拿epsilon = 1。我们得到

-1 < f(n)/n^3 - 4 < 1

或

3 < f(n)/n^3 < 5

或

3n^3 < f(n) < 5n^3

并且您可以使用 k1=3、k2=5 和 epsilon = 1.

存在的 n0 的值

使用极限方法证明一个函数是大的

Proving a function is in big theta using limit method

complexity-theory

proof

time-complexity