algorithm - 树排序 : time complexity

Question

为什么平均案例时间复杂度是tree sort O(n log n)?

来自维基百科:

Adding one item to a binary search tree is on average an O(log n) process (in big O notation), so adding n items is an O(n log n) process

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

所以看起来更像

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

我错过了什么吗？

Answer 1

为什么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))