用 N 个给定元素构建 BST 是 O(n lg n) 吗? [英] Is building a BST with N given elements is O(n lg n)?

问题描述

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

What would be the worst case time complexity to build binary search tree with given arbitrary N elements ?

我认为 N 个给定元素和 一个一个接一个地出现的元素之间是有区别的，从而形成一个总共 N 个元素的 BST.

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

In the former case, it is O(n log n) and in second one is O(n^2) . Am i right ?

推荐答案

If 二叉搜索树 (BST) 不是完全平衡的，那么最坏情况下的时间复杂度是 O(n^2).通常，BST 是通过重复插入构建的，因此最坏的情况将是 O(n^2).但是如果可以对输入进行排序(在O(nlogn)中)，则可以在O(n)中构建，从而导致O(nlogn)的整体复杂度)

If Binary Search Tree (BST) is not perfectly balanced, then the worst case time complexity is O(n^2). Generally, BST is build by repeated insertion, so worst case will be O(n^2). But if you can sort the input (in O(nlogn)), it can be built in O(n), resulting in overall complexity of O(nlogn)

BST 是 自我平衡，那么最坏情况下的时间复杂度是 O(nlog n) 即使我们重复插入.

It BST is self-balancing, then the worst case time complexity is O(nlog n) even if we have repeated insertion.

这篇关于用 N 个给定元素构建 BST 是 O(n lg n) 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！