Асимптотическая сложность построения двоичного дерева

Question

В чем заключается сложность building сбалансированное двоичное дерево размером n с нуля?

Узел ввода O (log n).

Однако, как вы идете вперед, кумулятивное время

O ((срубы 1) + (2 входа) + ... + (журнал (п-1)) + (срубы п)).

Что это значит?

Это o (n log (n)), small 'o', я не знаю, насколько далеко.

Answer 1

log(1) + log(2) + ... + log(n) = log(1*2*..*n) = log(n!) который находится в Theta(nlogn)

Итак, строительство (сбалансированное) дерево с нуля имеет плотно асимптотику граница Theta(nlogn)

---

EDIT:
Я также хотел бы показать вам что вы не можете построить BST лучше, чем O(nlogn) с любым алгоритмом. В основном - это потому, что он позволит сортировать лучше, чем O(nlogn), просто создавая дерево с помощью алгоритма «лучше», а затем - делая обход в порядке на дереве и выводить элементы. Результатом будет отсортированный массив.
Сложность в порядке прохождения - O(n), и поскольку предполагается, что дерево построено быстрее, то O(nlogn) - мы получаем противоречие с тем, что сортировка Omega(nlogn) problen.