你如何证明 n*log n 在 O(n) 中?

Question

我正在研究Big-Oh，但我坚持在证明部分。

问题是要证明

n*log n 在 O(n) 中。

鉴于有一个公式可以检查它是否在大哦 我试过了

F(n) <= c*g(n)

n*log n <= 1*n

然后我得到log(n) <= 1，其中n>n0。因此，如果我将 100 替换为 n，则结果大于 1。

(我检查了函数在 O(n) 中的答案)

Answer 1

你可以很容易证明它不是O(n)。

假设声明为真，那么根据大O的定义：

存在常数 N、c，使得对于所有 n> N> 0：n log n <= c*n

n log n <= c*n  since n > 0
log n <= c
n <= 2^c

但对于n = max {2^c+1, N+1}- 上述情况并不成立。因此，最初的假设是错误的，并且没有这样的常数。

如果没有这样的常量，根据大 O 表示法的定义，n log n不在O(n)中。

Answer 2

你不能证明 n*log n 是 O(n)，因为它不是。

你的证明中至少有一个缺陷是 n * log n <= 1*n 是不正确的。