构建二叉搜索树的时间复杂度是多少？

“在最坏的情况下，每个基于比较的 n 元素排序算法都必须进行 Ω(nlogn) 比较。基于这一事实，构建 n 节点二叉搜索树的复杂性是多少？为什么？”

基于这个问题，我认为构造复杂度至少必须是O(nlogn)。也就是说，我似乎不知道如何找到构造的总复杂性。

问题的标题和您引用的文字问的是不同的事情。我将解决引文所说的内容，因为只需查看算法就可以找到 BST 构建的成本。

假设有一秒钟可以用比 Ω(nlogn) 更好的值构造 BST。使用二叉搜索树，您可以在 θ(n) 时间内读出排序列表。这意味着我可以创建一个排序算法，如下所示。

Algorithm sort(L) 
  B <- buildBST(L)
  Sorted <- inOrderTraversal(B)
  return Sorted

使用这个算法，我将能够比 Ω(nlogn) 更好地对列表进行排序。但正如您所说，这是不可能的，因为 Ω(nlogn) 是下界。因此，不可能在比 Ω(nlogn) 时间内创建二叉搜索树。

此外，由于算法在 O(nlogn) 时间内创建 BST，因此您实际上可以说该算法在基于比较的模型下是最优的