如何证明 n*log n 在 O(n) 中？
How to you prove that n*log n is in O(n)?
我正在研究 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))
你不能证明 n*log n 是 O(n)，因为它不是。
你的证明中至少有一个缺陷是 n * log n <= 1*n 不正确。
你可以很容易地在 O(n) 中证明它 不是 。
假设声明是真实的，那么 definition of big O:
There are constants N, c such that for all 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) 中。
我正在研究 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))
你不能证明 n*log n 是 O(n)，因为它不是。
你的证明中至少有一个缺陷是 n * log n <= 1*n 不正确。
你可以很容易地在 O(n) 中证明它 不是 。
假设声明是真实的，那么 definition of big O:
There are constants N, c such that for all 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) 中。