假设我有一个包含 N 个节点的二叉搜索树。或四叉树或八叉树，如果它们有任何区别的话。
然后假设我运行一个算法来更改树中的所有键。移动东西似乎很复杂。也许实际上有一个很好的算法，但假设我采用了简单的路线:我迭代树，将键存储在列表中，然后通过重复重新插入从头开始重建树。即，完全重建。
进行这种重建时，我期望的时间复杂度是多少？有 N 个节点，每次插入都需要 log N 时间，但我无法理解随着树的生长会发生什么。
最佳答案
因为插入(平衡)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²)
关于algorithm - 重建二叉搜索树/四叉树/八叉树的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23529900/