Какова временная сложность построения бинарного дерева поиска?

Question

"Каждый основанный на сравнении алгоритм для сортировки n элементов должен принимать Ω (nlogn) сравнений в худшем случае. С этим фактом, какова будет сложность построения дерева двоичного поиска с n-узлами и почему?"

Исходя из этого вопроса, я думаю, что сложность конструкции должна быть не менее O (nlogn). Тем не менее, я не могу понять, как найти общую сложность конструкции.

Answer 1

Название вопроса и текст, который вы цитируете, задают разные вещи. Я собираюсь обратиться к тому, что говорится в цитате, потому что выяснить, как дорого стоит построение BST, можно, просто взглянув на алгоритм.

Предположим, что за секунду можно было построить BST лучше, чем Ω (nlogn). С помощью двоичного дерева поиска вы можете прочитать отсортированный список за Θ (n) времени. Это означает, что я мог бы создать алгоритм сортировки следующим образом.

Algorithm sort(L) 
  B <- buildBST(L)
  Sorted <- inOrderTraversal(B)
  return Sorted

С помощью этого алгоритма я смогу отсортировать список лучше чем Ω (nlogn). Но, как вы сказали, это невозможно, потому что Ω (nlogn) является нижней границей. Таким образом, невозможно создать двоичное дерево поиска за время, превышающее Ω (nlogn).

Кроме того, поскольку алгоритм завершает работу, чтобы создать BST за O (nlogn), можно фактически сказать, что алгоритм является оптимальным по модели сравнения на основе

Answer 2

Конструкция BST будет O(n(log(n))).
. Вам нужно будет вставить каждый узел, который является операцией O(n).
Чтобы вставить эти n узлы, которые вам нужно будет сделать в наименьшее O(log(n)) сравнение.
Следовательно, минимум будет O(n(log(n))).
Только в лучшем случае, когда массив уже отсортирован, сложность времени будет O(n)