algorithm - 证明/反驳 Big O 和 Big Theta

Question

我在完全理解如何证明以下某些陈述时遇到了问题。

例如我有一个声明:n^2logn = O(n^2) .如果我错了请纠正我，但这表明 n^2是bigO的 n^2logn .意思是n^2增长速度超过 n^2logn .现在我们将如何证明这一点？我假设我需要使用归纳法证明，我曾尝试使用但陷入了这个过程。我可以将此语句重写为 n^2logn <= n^2 ？

是否可以使用归纳来反驳某事？例如，反证n!=O(n^n) .还是通过简单地证明任意值(比方说大于 2)不满足该陈述来反驳该陈述是否有效？

最后，为了清楚起见，bigTheta 指出当增长正确时，方程是等价的？

Answer 1

claim n^2logn在O(n^2)直觉上意味着 n^2logn 的增长速度最多与 n^2 一样快-渐近(这种说法是错误的)。

根据定义，这意味着存在一些常量 c,N，使得对于每个 n>N : c*n^2logn <= n^2

反驳它非常简单。
假设(错误地)声明是真实的，并且让N,c成为我们的常量:

c*n^2logn <= n^2
c*logn <= 1
logn <= 1/c

但是c是常数，并且有一些 n>N这样 logn > 1/c - 矛盾。

您可以通过展示其他东西来反驳归纳法，例如 - 如果您通过归纳法证明 n! < n^n - 你实际上反驳了声明n! = n^n

关于big theta，我试图在线程Big Theta Notation - what exactly does big Theta represent?中详细解释这个问题