构造二叉搜索树的时间复杂度是多少? [英] What is the time complexity of constructing a binary search tree?
问题描述
在最坏的情况下,每个用于比较n个元素的基于比较的算法都必须进行Ω(nlogn)个比较.因此,构造n节点二进制搜索树的复杂性是什么?为什么?"
"Every comparison-based algorithm to sort n elements must take Ω(nlogn) comparisons in the worst case. With this fact, what would be the complexity of constructing a n-node binary search tree and why?"
基于这个问题,我认为构造复杂度必须至少为O(nlogn).就是说,我似乎无法弄清楚如何找到构造的总复杂性.
Based on this question, I am thinking that the construction complexity must be at least O(nlogn). That said, I can't seem to figure out how to find the total complexity of construction.
推荐答案
问题的标题和您引用的文本问的是不同的问题.我要解决报价中所说的问题,因为仅通过查看算法就可以确定BST构建的成本是多少.
The title of the question and the text you quote are asking different things. I am going to address what the quote is saying because finding how expensive BST construction is can be done just by looking at an algorithm.
假设有一秒钟可以构造出比Ω(nlogn)更好的BST.使用二叉搜索树,您可以在Θ(n)时间中读出排序的列表.这意味着我可以创建如下的排序算法.
Assume that for a second it was possible to construct a BST in better than Ω(nlogn). With a binary search tree you can read out the sorted list in Θ(n) time. This means I could create a sorting algorithm as follows.
Algorithm sort(L)
B <- buildBST(L)
Sorted <- inOrderTraversal(B)
return Sorted
使用这种算法,我能够以比Ω(nlogn)更好的方式对列表进行排序.但是正如您所说,这是不可能的,因为Ω(nlogn)是一个下限.因此,不可能创建比Ω(nlogn)时间更好的二叉搜索树.
With this algorithm I would be able to sort a list in better than Ω(nlogn). But as you stated this is not possible because Ω(nlogn) is a lower bound. Therefor it is not possible to create a binary search tree in better than Ω(nlogn) time.
此外,由于存在一种算法以在O(nlogn)时间创建BST,您实际上可以说该算法在基于比较的模型下是最佳的
Furthermore since an algorithm exits to create a BST in O(nlogn) time you can actually say that the algorithm is optimal under the comparison based model
这篇关于构造二叉搜索树的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!