確定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))