我正在为一次考试学习,我知道单个插入操作的时间复杂度是O(logn),而树的高度为n,则比较操作的时间复杂度将为 Ω(n log n)。在最坏情况下,如何证明对于一个包含n个元素的未排序数组A,构建BST所需的时间是 Ω(n log n)?(注:BST是二叉搜索树的缩写)
遍历二叉搜索树可以在线性时间内完成,因此如果您可以从未排序的数组中“更快地”构建二叉搜索树,那么这意味着您可以比O(n * log(n))更快地对未排序的数组进行排序,而我们知道这是不可能的(除非您有关于元素排序的其他信息)。另一方面,您可以在Ω(n * log(n))中对数组进行排序,并且可以在线性时间内从已排序的数组中构建二叉搜索树(例如构建类似列表的树)。