树排序：时间复杂度

Question

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

从维基百科得知：

将一个项添加到二叉搜索树上，平均情况下是O（log n）的过程（使用大O符号），因此添加n个项是O（n log n）的过程。

但是我们并不是每次向n个项的树中添加一个项。我们从一个空树开始，并逐渐增加树的大小。

所以它看起来更像：

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

我有所遗漏吗？

- rapt

Answer 1

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

https://zh.wikipedia.org/wiki/斯特劳公式

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

- wookie919

---

你不需要使用斯特林公式吗？只需使用对数规则和O定义即可。但我想知道为什么在这种情况下没有指定复杂度为O(log n!)是很常见的。通常人们使用O符号表示“大约需要的操作次数”，尽管这并不准确。换句话说，在常见用法中，O(log n!)算法可能比O(n log n)更好。 - rapt

@rapt 我认为你想表达的是 log(n!) 可能比 n log(n) 更为严格的界限。但在大O符号的世界里，这根本不是事实。正如这里所证明的那样，O(log(n!)) 确实等于 O(n log(n)): https://dev59.com/r2sz5IYBdhLWcg3wFUC_ 我猜 O(n log(n)) 更受欢迎的原因是人们更容易理解它。 - wookie919

是的。但正如我多次所说，大O符号表示时间复杂度，只是时间复杂度的上界，因此并不十分准确，通常只是一种非正式的表示方法。无论如何，这是一个很好的答案。谢谢。 - rapt

Answer 2

的原因有两个部分。首先，展开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))。

- Chris Gong

---

为什么O定义需要第二个不等式？此外，我认为维基百科上的解释是误导性的：在实践中，复杂度是log(n!)。它不能变得比log(n^n)更糟糕的事实很酷，但我们也可以说它不能变得比log(n^n^n)更糟糕。 - rapt

@rapt 因为根据大O符号表示法，下限 n/2*log(n/2) 与 nlog(n) 相同，因此您有不等式 O(nlog(n)) <= O(log(n!) <= O(nlog(n))。 - Chris Gong

这是正确的，但当我查看大O符号的正式定义时，似乎第一个不等式就足以表明 log(n!) = O(n log(n))。无论如何，这是一个好的简单解释，提醒了我一些细节，并确认当前的维基百科“树排序”条目并不那么准确。 - rapt