algorithm - 重建二叉搜索树/四叉树/八叉树的时间复杂度？

Question

假设我有一个包含 N 个节点的二叉搜索树。或四叉树或八叉树，如果它们有任何区别的话。

然后假设我运行一个算法来更改树中的所有键。移动东西似乎很复杂。也许实际上有一个很好的算法，但假设我采用了简单的路线:我迭代树，将键存储在列表中，然后通过重复重新插入从头开始重建树。即，完全重建。

进行这种重建时，我期望的时间复杂度是多少？有 N 个节点，每次插入都需要 log N 时间，但我无法理解随着树的生长会发生什么。

Answer 1

因为插入(平衡)BST 需要 Θ(log n)，并且树从 0 个节点开始，然后是 1节点，然后 2 等，我们得到运行时间为:

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

从这里，我们可以直接说运行时间是 Θ(n log n) 因为:( related post )

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

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

这也与tree sort有关.

---

我们实际上可以证明我们不能比 Θ(n log n) 更快:

It's been proven平均至少需要 Θ(n log n) 时间来排序(使用基于比较的算法)。

由于我们可以在 Θ(n) 中迭代 BST，我们可以直接推断出我们至少需要 Θ(n log n) 时间来插入。

---

注意 - 对于非平衡 BST，运行时间实际上是 Θ(n²)，因为不平衡 BST 的最坏情况插入时间是 Θ(n)，所以我们有:

Θ(1 + 2 + ... + n) = Θ(n(n+1)/2) = Θ(n²)