确定Asympotic Notation

Question

我有一组问题，我给了一个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）

Answer 1

您需要降低F（ n）转换为一种可以与g（n）进行比较的形式。对于您的情况：

F（N）=的log（n ）
F（N）= 2的log（n）

这应该是足够回答你的这个问题例如 - 这个过程对于其余的部分几乎是一样的。

Answer 2

可以按如下

极限当n趋于无穷做到这一点使用限制（对不起，我不知道如何制作这里的数学方程）F（N）/ G（N）

的 如果所获得的值是

恒定然后f(n) = Θ(g(n))

无限然后f(n) = Ω(g(n))

零然后f(n)= O(g(n))