“在最坏的情况下，每个用于比较n个元素的基于比较的算法都必须进行Ω（nlogn）个比较。因此，构造n节点二进制搜索树的复杂性是什么？为什么？”]
基于此问题，我认为构造复杂度必须至少为O（nlogn）。就是说，我似乎无法弄清楚如何找到构造的总复杂性。
“在最坏的情况下，每个用于比较n个元素的基于比较的算法都必须进行Ω（nlogn）个比较。因此，构造n节点二进制搜索树的复杂性是什么？为什么？” ... >
BST的结构为O(n(log(n)))。您将需要插入O(n)操作的每个节点。要插入n节点，您至少需要进行O(log(n))比较。因此，最小值将是O(n(log(n)))。仅在已经对数组进行排序的最佳情况下，时间复杂度才为O(n)