algorithm - 用 N 个给定元素构建 BST 是 O(n lg n) 吗？

Question

用给定的任意 N 个元素构建二叉搜索树的最坏情况时间复杂度是多少？

我认为 N 个给定元素 和元素一个接一个地生成一个包含 N 个元素的 BST 是有区别的。

在前一种情况下，它是 O(n log n) 而在第二种情况下是 O(n^2) 。我说得对吗？

Answer 1

如果Binary Search Tree (BST)不是完美平衡的，那么最坏情况下的时间复杂度是O(n^2)。通常，BST 是通过重复插入构建的，因此最坏情况将是 O(n^2)。但是如果你可以对输入进行排序(在O(nlogn)中)，它可以在O(n)中构建，导致整体复杂度为O(nlogn )

BST 是self-balancing ，那么即使我们重复插入，最坏情况下的时间复杂度也是 O(nlog n)。