Структуры данных и модели вычислений


Анализ трудоемкости - часть 2


Остается оценить суммарную трудоемкость операций НАЙТИ.

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

Для краткости будем обозначать .

Поскольку ранг узла может увеличиваться лишь при выполнении операции ОБЪЕДИНИТЬ, причем не более чем на 1, после таких операций ранг никакого узла не может стать больше , следовательно, максимальный индекс , при котором может быть непустым, равен .

Оценим теперь суммарное время, требуемое для выполнения операций НАЙТИ; очевидно, оно пропорционально числу ребер, ведущих от сыновей к отцам и встречающихся при выполнении всех таких операций. Для оценки времени, затрачиваемого на реализацию этих операций, применим бухгалтерский прием. Отнесем расход времени на прохождение очередного ребра от узла к его родителю при выполнении операции типа НАЙТИ на одну из трех разных статей расходов: "корневую", "транзитную" и "местную" в зависимости от следующих условий.

Еслии в данный момент не является корнем, то расходы относим на статью транзитных расходов. Еслии не является корнем, то на статьюместных расходов в-м диапазоне, если же— корень, то на статью корневых расходов.

Сумму местных расходов во всех диапазонах обозначим через

Имеем, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.

Для транзитных переходов имеем, так как при каждом выполнении операции НАЙТИ происходит не болеепереходов из одного диапазона в другой.

Для оценки величины введем потенциалузла после выполнения операции . Если к узлу еще не применялась операция СОЗДАТЬ, то.

Потенциалом группыпри текущем состоянии коллекции назовем величину

Очевидно, что в любой момент времени справедливо неравенство

(1)

Покажем, что для любого узлапри любом выполняется неравенство . Действительно, если — операция СОЗДАТЬ (), то

то есть потенциал узла , так же, как, очевидно, и всех остальных, не изменяется.


Начало  Назад  Вперед



Книжный магазин