我正在为一次考试学习，我知道单个插入操作的时间复杂度是O(logn)，而树的高度为n，则比较操作的时间复杂度将为 Ω(n log n)。
在最坏情况下，如何证明对于一个包含n个元素的未排序数组A，构建BST所需的时间是 Ω(n log n)？
（注：BST是二叉搜索树的缩写）
在最坏情况下，如何证明对于一个包含n个元素的未排序数组A，构建BST所需的时间是 Ω(n log n)？
（注：BST是二叉搜索树的缩写）
BST O(NLogN)建树证明
4
- Annie Hua
5
1你无法证明它，因为这不是真的。 - Gene
在最坏的情况下，树会像一个链接列表一样增长为一个长字符串，其中每个节点都添加在末尾。构建这需要与n^2成比例的时间。说这个列表是未排序的不足以避免这种情况。你可以证明，平均而言，构建一个简单的BST需要O(n log n)次比较。你也可以证明，像AVL或红黑树这样的自平衡树可以用O(n log n)次比较来构建。但这些证明并不是很简单。 - Gene
你能告诉我，如果数组是未排序的，它会如何达到最坏情况？ - Luai Ghunim
不要混淆Omega和Big-O，它们是两个不同的概念。 - Luai Ghunim
@Gene 你为什么这样认为？从任何BST构建平衡BST可以在线性时间内完成，但这与问题无关。此外，如果您有一个排序的数组，您可以轻松地从中构建BST。 - Ivaylo Strandjev
1个回答
3
遍历二叉搜索树可以在线性时间内完成，因此如果您可以从未排序的数组中“更快地”构建二叉搜索树，那么这意味着您可以比O（n * log（n））更快地对未排序的数组进行排序，而我们知道这是不可能的（除非您有关于元素排序的其他信息）。
另一方面，您可以在Ω（n * log（n））中对数组进行排序，并且可以在线性时间内从已排序的数组中构建二叉搜索树（例如构建类似列表的树）。
另一方面，您可以在Ω（n * log（n））中对数组进行排序，并且可以在线性时间内从已排序的数组中构建二叉搜索树（例如构建类似列表的树）。
- Ivaylo Strandjev
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接