构造二叉搜索树的时间复杂度是多少? [英] 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屋！