вычисление временной сложности алгоритма дерева AVL - PullRequest
Новая
       12

вычисление временной сложности алгоритма дерева AVL

0 голосов
/ 05 мая 2018

Я хочу вычислить временную сложность следующего алгоритма. У меня есть дерево AVL и пара из двух чисел (x, y), что x<y. Цель алгоритма - вывести все числа в дереве между x и y. x и y определенно отсутствуют в дереве.

Моя цель - создать алгоритм, время выполнения которого равно O (logn + k), так что k - это число узлов между x и y, а n - общее количество узлов в дереве.

Мой алгоритм таков:

Функция, которая получает x и y, начинается с корня дерева и выглядит следующим образом:

если текущий узел находится между x и y - выведите его и рекурсивно вызовите левый узел с (x, текущее значение узла) и правый узел с (текущее значение узла, y).

если текущий узел меньше x - вызвать рекурсивный правый узел с (x, y)

если текущий узел больше чем y - вызвать рекурсивный левый узел с помощью (x, y) Функция останавливается, когда достигает листа (узла, к которому не привязаны другие узлы). Соответствует ли моя функция требованиям времени выполнения?

1 Ответ

0 голосов
/ 06 мая 2018

Да, это так. Вы можете доказать это, заметив, что ваш алгоритм делает только посещение узлов, и каждое посещение узла требует O (1) времени. Каждое посещение, которое обнаруживает значение в диапазоне, может быть «начислено» на часть O (k) ограниченного времени.

Но есть некоторые посещения - те, которые находят узлы меньше или больше, чем диапазон - которые не обнаруживают значение. Они должны быть "заряжены" в O (log n) часть времени.

Остальное доказательство состоит в том, чтобы показать, что таких посещений действительно не более O (log n). Ключ в том, чтобы показать, что на каждой глубине от корня может быть не более постоянного числа c. Это требует некоторых рассуждений о структуре BST. Я позволю вам весело проработать детали. Имеется O (log n) глубин, поэтому количество этих посещений равно O (c log n) = O (log n). QED

Дополнительные примечания

Ваш алгоритм излишне тасует значения. Это легко настроить, чтобы значения были обнаружены в отсортированном порядке. Я снова позволю вам проработать детали.

...