为什么构建二叉搜索树的时间复杂度为O(N log N)？

Question

4

准备考试了。这不是作业问题。

我发现最坏情况下是O(N²)构建二叉搜索树（每次插入需要N-1次比较，将所有比较相加0 + 1 + ... + N-1 ~ N²），这是BTS倾斜的情况。

（平衡）BST的插入是O(log N)，为什么最好情况是O(NlogN)来构建树呢?

我最好的猜测是 - 因为单个插入是log N，所以总插入总和给我们N log。

谢谢！

- newprint

2

你已经回答了这个问题 :) - Petar Minchev

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jan Zyka · Accepted Answer

正如您所写 :) 单次插入的时间复杂度为O(log N)。因为N个元素的加权树高度为log N，所以您需要进行多达log N次比较才能插入单个元素。您需要执行N次这样的插入操作。因此总时间复杂度为N*logN。