帮助了解 Big Omega 证明吗？

发布于 2024-10-19 15:37:29 字数 387 浏览 2 评论 0原文

我在解决证明时遇到困难。其中 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)

任何人都可以提供有关如何执行此类型的一些见解的问题？提前致谢！

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

手心的海 2024-10-26 15:37:29

Big-Omega 的定义： f(n)=Omega(g(n)) iff 常数 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 < ...”

Definition of Big-Omega: f(n)=Omega(g(n)) iff constants C and K exist such that for all n > K, f(n) > C * g(n)

In other words, you need to be able to say something like this: "I choose C = 5, and now for all n > 1000, f(n) > 5 * g(n), so there."

Let's look at your problem now.

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

Divide by 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

So let's look at these three terms one by one (more formal proof would be needed, of course, but these are straightforward).

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

So we see that for any n > 2, C < 1 + 5 + 1 = 7

Now you get to say "I choose C=7, and for any n > 2, C*n^1.6 < ..."

回复收藏 0 原文

~没有更多了~