Is n log n= O(n)和is n log n= Omega(n)

Question

嘿，伙计们，我已经被问到了上面两个问题，并解释了为什么。我很困惑，我知道O(nlogn)算法运行的时间比线性O(n)算法增长得更快，但我不太确定这些问题的答案。我相当确定n log n不等于O(n)，但我不太确定如何解释它。(我不认为我们需要做一个确切的证明)

Answer 1

声明：n*log(n)不是O(n)证明:证明是矛盾的。假设n*log(n)是O(n)。然后，根据O的定义，必须存在常量n0和c，使得对于所有n > n0，n*log(n) <= c * n。用n除以两边得到log(n) <= c。然而，不存在对所有n > n0都适用的常量c；考虑序列n = 2^0, 2^1, 2^2, …, 2^k, …这是矛盾的；因此，假设是不正确的。换句话说，n*log(n)不能为O(n)。

声明：n*log(n)是Omega(n)证明:证明是直接的。选择n0 = 1和c = 1。然后根据需要使用n*log(n) >= n = 1*n = c*n。

Answer 2

简单答案：

忽略一些细节，你可以说f(n) = O( g(n) )意味着f(n) <= g(N)(不是一个实际的不等式，而只是增长)。也可以说f(n)=Omega( g(n) )表示f(n) >= g(N)。(我们可以将其扩展到Theta，little o和little omega )。

所以基本上，如果你有一种直觉，认为nlogn是一个比n更大的函数，那么你可以说:n log n= Omega(n)或者等价地n= O(n log n)。但不是反过来。

因此，nlogn=O(n)是一个错误的陈述。

高级答案：

如果你想证明f(n)=O(g(n))，那么你需要找到满足Big-O定义的某些常数。你可以查一查，但我不打算详细说明。

然而，如果你想证明f(n)不在O( g(n) )中，那么简单地说你想证明f(n) <= g(N)是一个错误的陈述。因此，应该是f(n) > g(n)的情况。现在，您可以将严格较大(较小)的比较表示为-o或little-omega。因此，要证明f(n)不在O( g(n) )中，实际上应该证明f(n) >g(N)，这意味着f(n) = little-omega(g(n))。要证明小o和小omega关系，您必须使用限制。

要详细了解这些形式证明，一个非常好的参考资料是由Cormen编写的“算法简介，第三版”。

Answer 3

n logn不是O(n)，因为它比n增长得更快，这意味着n不是它的上限。

另一方面，n log n是Ω(n)，因为n是它的下限。Ω的定义就是for f(n)=Ω(g(n)) means that for any c there exists an n such that 0<=cg(n)<=f(n)。