渐近符号：如何证明 n^2 = Ω(nlogn)？

Question

我被要求证明或反驳以下猜想：

n^2 = Ω(nlogn)

这个感觉应该很容易，直觉上我觉得因为Ω是下界函数，n^2根据定义比nlogn大，所以也很明显。但是，我觉得这不足以作为证明，或者可能是错误的...

例如，我知道任何属于Ω(nlogn)的东西也可以属于Ω(n)和Ω(logn)，并且它们都是<= n^2。这足以证明吗？

我在几个不同的地方看到它作为 big Omega 的例子，但没有解释为什么。

这是我在探索 HelpYou 的答案后试图证明这个猜想的尝试：

这是错误的吗？（P.S。-也许这里使用 T(n) 是错误的）

希望这个更准确...

Answer 1

方法一：

让我们采取：

f(n) = n^2

g(n) = n*logn

f(n) is in Ω(g(n)) if there is c > 0 and n0 > 0 such that:
f(n) >= c*g(n) for every n >= n0.

这意味着：

n*n >= c*n*logn          |:n ( n>=n0>0 )
n >= c*logn

让我们选择 c=1 和 n0=b^b（b - 对数底数，b > 1）：

n >= logn

对每个 n>=n0 都成立，因为 b^b >= b 当 b > 1

方法二：

          n*logn              logn      (*)        1/n *logb
   lim -------------- = lim ---------- ===== lim ------------ = 0
  n->inf   n^2         n->inf   n           n->inf    1

可以使用 l'Hospital (*) 进行演示。这就是因为结果是有限值。

对于第二种方法，以下table可能有用：

f(n) = O/Ω/Ө(g(n))

                      O                     Ω                     Ө
------------------------------------------------------------------------
       f(n)  
 lim --------       finite                > 0                 > 0 & finite
n->inf g(n)  

       g(n)  
 lim --------        > 0                 finite               > 0 & finite 
n->inf f(n)

渐近符号：如何证明 n^2 = Ω(nlogn)？

Asymptotic notation: How to prove that n^2 = Ω(nlogn)?

big-o

time-complexity

asymptotic-complexity