树排序：时间复杂度
Tree sort: time complexity
为什么平均案例时间复杂度是tree sortO(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!
我是不是漏掉了什么？
O(log(n!)) = O(nlog(n)).
https://en.wikipedia.org/wiki/Stirling%27s_approximation
（答案必须为 30 个字符。）
之所以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))
为什么平均案例时间复杂度是tree sortO(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!
我是不是漏掉了什么？
O(log(n!)) = O(nlog(n)).
https://en.wikipedia.org/wiki/Stirling%27s_approximation
（答案必须为 30 个字符。）
之所以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))