我有一组问题，我得到一个 f(n) 和 g(n)，我应该确定 f(n) 在哪里是 O(g(n))、Ω(g(n)) 或 Θ( g(n))
而且我还必须确定正确关系的 c(s) 和 n0。
我该如何着手解决这样的问题？
这是我遇到的问题的一个例子
f(n)= lg(n^2) g(n)=n lg(n)
问问题
69 次
2 回答
1
您需要将 f(n) 简化为易于与 g(n) 进行比较的形式。对于您的情况：
f(n) = log(n 2 )
f(n) = 2 log(n)
对于该示例，这应该足以回答您的问题-该过程对于该集合的其余部分几乎相同。
于 2012-04-07T18:05:43.500 回答
1
您可以使用限制执行此操作，如下所示
极限，因为 n 趋于无穷大（对不起，我不知道如何在这里产生数学方程） f(n)/g(n)
如果得到的值为
一个常数然后f(n) = Θ(g(n))
那么无穷大f(n) = Ω(g(n))
那么零f(n)= O(g(n))
于 2012-04-08T12:12:58.410 回答