树排序：时间复杂度

Question

为什么树排序 的平均案例时间复杂度是O(n log n)？

来自维基百科：

向二叉搜索树添加一项平均是一个 O(log n) 过程（以大 O 表示法），因此添加 n 个项目是一个 O(n log n) 过程

但是我们不会每次都将一个项目添加到由 n 个项目组成的树中。我们从一棵空树开始，逐渐增加树的大小。

所以看起来更像

log1 + log2 + ... + logn = log (1*2*...*n) = log n!

我错过了什么吗？

Answer 1

O(log(n!)) = O(nlog(n))。

https://en.wikipedia.org/wiki/Stirling%27s_approximation

（答案必须为 30 个字符。）

Answer 2

原因O(log(n!)) = O(nlog(n))是一个两部分的答案。一是扩大O(log(n!))，

log(1) + log(2) + ... + log(n)

我们在这里都可以同意log(1)，log(2)， 和所有数字log(n-1)都小于log(n)。因此，可以进行以下不等式，

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)

现在答案的另一半取决于从 1 到 n 的一半数字大于 n/2 的事实。这意味着log(n!)将大于n/2*log(n/2)总和的前半部分log(n!)，

log(1) + log(2) + ... + log(n) => log(n/2) + log(n/2) + ... + log(n/2)

原因是，前半log(1) + log(2) + ... + log(n)是log(1) + log(2) + ... + log(n/2)，其小于n/2*log(n/2)由第一不等式作为证明所以通过将总和的后半部分log(n!)，可以表明，它是大于n/2*log(n/2)。

所以有了这两个不等式，可以证明 O(log(n!)) = O(nlog(n))