Может ли кто-нибудь объяснить мне, как наихудшее время работы при построении BST составляет n^2? Я спросил своего профессора, и я получил только одну обратную связь:Худшее время работы при построении BST?
«Потому что дерево линейно зависит от размера ввода. Стоимость 1 + 2 + 3 + 4 + ... + (n-1)».
Может кто-нибудь объяснить это по-другому? Ее объяснение заставляет меня думать, что его O (n) ....
Я думаю, что худший случай случается, когда вход уже отсортирован: A, B, C, D, E, F, G, H. Вот почему вам может потребоваться случайная перестановка входной последовательности, если она применима.
В худшем случае время работы пропорционально квадрату входа, поскольку BST не сбалансирован. Уквалифицированный BST может иметь вырожденную структуру: в худшем случае - одиночный список. Для создания этого списка потребуется, чтобы каждая вставка маршировала по всей длине растущего списка, чтобы добраться до листового узла, чтобы добавить новый лист.
Например, попробуйте запустить алгоритм на данных, которые находятся точно в обратном порядке, так что каждый новый узел должен стать новым самым левым узлом дерева.
BST (даже сбалансированный!) Может быть построен в линейном времени только в том случае, если входные данные уже отсортированы. Более того, это делается с использованием специального алгоритма, который использует порядок; не выполняя N вставок.
Я предполагаю, что шаги вставки 1 + 2 + 3 + 4 + ... + (n-1) понятны (для измененного упорядоченного списка).
Вам должно быть удобно, что это число шагов квадратично. Подумайте о запуске алгоритма дважды и посчитайте количество шагов:
[1 + 2 + 3 + 4 + ... + (n-1)] + [1 + 2 + 3 + 4 + ... + (n-1)] = [1 + 2 + 3 + 4 + ... + (n-1)] + [(n-1) + ... + 4 + 3 + 2 + 1] = n + n + ... n = n^2
Таким образом, один запуск занимает 0,5 * n^2 шага.