algorithm - 构建二叉树的渐近复杂度

Question

从头开始构建大小为 n 的平衡二叉树的复杂性是多少？

节点插入是O(log n)。

但是，随着时间的推移，累计的时间是

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

这“加起来”是什么？

它是o(n log(n))，小'o'，我不知道小到什么程度。

Answer 1

log(1) + log(2) + ... + log(n) = log(1*2*..*n) = log(n!) 在 Theta(nlogn)

因此，从头开始构建一棵(平衡的)树具有 Theta(nlogn)

的严格渐近界限

---

编辑:
我还想向您展示一个证明，证明您无法使用任何算法构建比 O(nlogn) 更好的 BST。基本上 - 这是因为它允许比 O(nlogn) 更好的排序，只需使用“更好”的算法构建你的树，然后 - 在树上按顺序遍历并输出元素。结果将是一个排序数组。
中序遍历的复杂度是 O(n)，并且由于假设树的构建速度比 O(nlogn) 快 - 我们与以下事实相矛盾排序是 Omega(nlogn) 问题。