建立BST时间复杂度

Question

我如何证明构建BST的复杂性是Ω(nlogn)？是Ω(n)用于数组，Ω(logn)用于插入每个元素？

Answer 1

遍历数组所有元素的最佳情况是Ω(n)，其中数组的大小是n。

现在要在BST中插入元素的是log(n)。因此，总体时间复杂度变为：Ω(nlogn)

在BST中插入总是log(n)

具有n个节点的完整二叉树的高度h最多为O（log n）。假设每个级别具有最大数量的节点，可以通过从根开始计算每个级别的节点来轻松证明这一点：

n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1

解决关于h的问题，我们得到

h = O(log n)

阅读here了解更多详细信息。