为什么是 O(n/2 + 5 log n) O(log n) 而不是 O(n log n)？

Question

对于 n/2 + 5 log n，我认为 5 和 2 的低阶项将被删除，从而留下 n log n

我哪里错了？

编辑：

谢谢，我相信我现在可以改正我的错误了：

O(n/2 + 5 log n) = O(n/2 + log n) = O( n + log n) = O(n)

n/2 + 5 log n <= 2n，对于所有 n >= 1 (c = 2, n₀=1)

Answer 1

既不是 O(log n) 也不是 O(n*log n)。它将是 O(n) 因为 n 的大值 log n 比 n 小得多因此它将被删除。

Answer 2

让我们为 n >= 1 定义函数 f 如下：

f(n) = n/2 + 5*log(n)

这个函数不是O(log n)；它比那增长得更快。为了证明这一点，我们可以证明对于任何常量 c > 0，可以选择 n0 使得对于 n > n0，f(n) > c * log(n)。对于 0 < c <= 5，这是微不足道的，因为根据定义 f(n) > [5log(n)]。对于 c > 5，我们得到

    n/2 + 5*log(n) > c*log(n)
<=> n/2 > (c - 5)*log(n)
<=> (1/(2(c - 5))*n/log(n) > 1

我们现在可以注意到，对于 n > 1，LHS 上的表达式是单调递增的，并使用 l'Hopital 找到 n 无限增长时的极限：

  lim(n->infinity) (1/(2(c - 5))*n/log(n)
= (1/(2(c - 5))* lim(n->infinity) n/log(n)
= (1/(2(c - 5))* lim(n->infinity) 1/(1/n)
= (1/(2(c - 5))* lim(n->infinity) n
-> infinity

使用 l'Hopital，我们发现随着 n 无限增长，没有限制； LHS 的价值也无限制地增长。因为LHS单调递增，无界增长，所以必须有一个n0之后LHS的值超过值1，按要求。

这一切都证明了f不是O(log n)。

f确实是O(n log n)。这一点也不难证明：选择 c = (5+1/2)，很明显

f(n) = n/2 + 5log(n) <= nlog(n)/2 + 5nlog(n) = (5+1/2)nlog(n) for all n.

但是，这不是我们可以为您的函数获得的最佳范围。您的功能实际上也是 O(n) 。为 c 选择与之前相同的值，我们只需要注意 n > log(n) 对于所有 n >= 1，所以

f(n) = n/2 + 5log(n) <= n/2 + 5n = (5+1/2)n

因此，f 也是 O(n)。我们可以证明 f(n) 是 Omega(n)，这证明它也是 Theta(n)。这留作练习，但也不难做到。提示：如果选择 c = 1/2 会怎样？

Answer 3

既不是 O(log n) 也不是 O(n*log n)。它将是 O(n)，因为对于较大的 n log(n) 比 n 小得多，因此它将被删除。

Consider n=10000, now 5log(n) i.e 5*log(10000)=46(apprx) which is less than n/2(= 5000).

为什么是 O(n/2 + 5 log n) O(log n) 而不是 O(n log n)？

Why is O(n/2 + 5 log n) O(log n) and not O(n log n)?

complexity-theory