asymptotic-complexity - 确定渐近符号

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)

score 1 · Accepted Answer

您需要将 f(n) 简化为易于与 g(n) 进行比较的形式。对于您的情况：

f(n) = log(n ² )
f(n) = 2 log(n)

对于该示例，这应该足以回答您的问题-该过程对于该集合的其余部分几乎相同。

score 1 · Accepted Answer

您可以使用限制执行此操作，如下所示

极限，因为 n 趋于无穷大（对不起，我不知道如何在这里产生数学方程） f(n)/g(n)

如果得到的值为

一个常数然后f(n) = Θ(g(n))

那么无穷大f(n) = Ω(g(n))

那么零f(n)= O(g(n))

2 回答 2