3

我无法解决证明问题。其中 t(n) <= cn^1.6，c 是一个常数。一般来说，Big Omega 与 Big O 相反，因为它是最好的情况，并寻找下限。所以存在 ac 和 n0 使得 n >= n0。但我不确定如何将其应用于证明以及如何操纵方程中的常数以找到 c 和 n0 并证明 t(n) 是 Omega(n^1.6)。

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7是Omega(n^1.6)

谁能提供一些有关如何解决此类问题的见解？提前致谢！

同样，所以我没有从我下面的评论中收到任何批评，这不是家庭作业问题，而是从一组练习中提取的示例，以便某人更容易解释此类问题背后的一般概念。

4

1 回答 1

2

Big-Omega 的定义：f(n)=Omega(g(n)) 如果存在常数 C 和 K，使得对于所有 n > K，f(n) > C * g(n)

换句话说，你需要能够说这样的话：“我选择 C ​​= 5，现在对于所有 n > 1000，f(n) > 5 * g(n)，就这样。”

现在让我们看看你的问题。

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 is Omega(n^1.6)

C * n^1.6 < (n-3logn)^1.6 + 5n^1.5 + 7

除以 n^1.6

C < ((n-3logn)/n)^1.6 + 5n^-0.1 + 7/n^1.6
C < (1 - 3logn/n)^1.6 + 5n^-0.1 + 7/n^1.6

因此，让我们一一看这三个术语（当然，需要更正式的证明，但这些很简单）。

1. (1 - 3logn/n)^1.6 = (1 - 0.smth)^1.6 = (0.smth)^1.6 < 1 for n > 2
2. 5n^-0.1 = 5/n^0.1 = 5/smth greater than 1 < 5 for n > 2
3. 7/n^1.6 = 7/smth large < 1 for n > 2

所以我们看到对于任何 n > 2，C < 1 + 5 + 1 = 7

现在你可以说“我选择 C=7，对于任何 n > 2，C*n^1.6 < ...”

于 2011-02-25T10:18:02.240 回答