"对于任意比较排序算法,最坏情况下排序n个元素的比较次数必须达到Ω(nlogn)。基于这个事实,请问构建一个n个节点的二叉搜索树的复杂度会是多少?为什么?"
根据这个问题,我认为构建复杂度至少为O(nlogn)。但是,我似乎无法找出构建总复杂度的方法。
"对于任意比较排序算法,最坏情况下排序n个元素的比较次数必须达到Ω(nlogn)。基于这个事实,请问构建一个n个节点的二叉搜索树的复杂度会是多少?为什么?"
根据这个问题,我认为构建复杂度至少为O(nlogn)。但是,我似乎无法找出构建总复杂度的方法。
问题的标题和你引用的文本在询问不同的事情。我将回答引语所说的内容,因为通过查看算法就可以找到构建BST的昂贵程度。
假设有一种方法可以以优于Ω(nlogn)的速度构建BST。使用二叉搜索树,您可以在Θ(n)的时间内读取排序列表。这意味着我可以创建以下排序算法。
Algorithm sort(L)
B <- buildBST(L)
Sorted <- inOrderTraversal(B)
return Sorted
BST的构建将是O(n(log(n)))
。
您需要插入每个节点,这是一个O(n)
操作。
要插入那n
个节点,您至少需要进行O(log(n))
次比较。
因此,最小值将是O(n(log(n)))
。
仅在数组已经排序的最佳情况下,时间复杂度才为O(n)