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

让我们为 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

我们现在可以注意到 LHS 上的表达式在 n > 1 时单调递增，并使用 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 会怎样？