Анализ трудоемкости
Для анализа трудоемкости выполнения операций нам потребуются две функции. Одна из них,, является суперэкспонентой и определяется следующим образом:
Вторая — суперлогарифм , по основанию 2, определяемая соотношением
Суперлогарифм является в некотором смысле обратной функцией к суперэкспоненте, . Значения функций и при нескольких значениях аргументов приведены в следующих таблицах:
| … | ||||||||||||||
Ребропри текущем состоянии коллекции назовем корневым, если— корень и (петля); назовем его прикорневым, если — корень и, в противном случае — внутренним.
Отметим следующие свойства коллекции на множестве из элементов. Прикорневое ребро может превратиться во внутреннее, а корневое — в прикорневое только при выполнении операции ОБЪЕДИНИТЬ.
Внутреннее ребропри первом же выполнении операции НАЙТИ, "проходящей через него", исчезает, но вместо него появляется прикорневое ребро, при этом, следовательно, внутреннее ребро "участвует в поиске" не более одного раза.
Если при выполнении очередной операции ОБЪЕДИНИТЬузел становится родителем узла , то после ее выполнения справедливо неравенство.
При выполнении операции НАЙТИ ранги узлов не изменяются, но узлы могут менять своих родителей, то есть меняется структура леса.
Если перед выполнением операции НАЙТИ узел был родителем узла , а после выполнения этой операции родителем узла стал узел , то выполняется неравенство. Следовательно, даже после изменения леса в результате выполнения операции НАЙТИ ранги вдоль любого пути от листа к корню будут строго возрастать.
При выполнении операции ОБЪЕДИНИТЬ ранг любого некорневого элемента не изменяется, а ранг корня либо сохраняется, либо увеличивается на 1.
Остается оценить суммарную трудоемкость операций НАЙТИ.
Черезобозначим ранг узла , который получится после выполнения операции, а — родитель узла, получающийся после выполнения этой операции. Определим множество Для краткости будем обозначать .
Поскольку ранг узла может увеличиваться лишь при выполнении операции ОБЪЕДИНИТЬ, причем не более чем на 1, после таких операций ранг никакого узла не может стать больше , следовательно, максимальный индекс , при котором может быть непустым, равен .
Оценим теперь суммарное время, требуемое для выполнения операций НАЙТИ; очевидно, оно пропорционально числу ребер, ведущих от сыновей к отцам и встречающихся при выполнении всех таких операций. Для оценки времени, затрачиваемого на реализацию этих операций, применим бухгалтерский прием. Отнесем расход времени на прохождение очередного ребра от узла к его родителю при выполнении операции типа НАЙТИ на одну из трех разных статей расходов: "корневую", "транзитную" и "местную" в зависимости от следующих условий.
Еслии в данный момент не является корнем, то расходы относим на статью транзитных расходов. Еслии не является корнем, то на статьюместных расходов в-м диапазоне, если же— корень, то на статью корневых расходов.
Сумму местных расходов во всех диапазонах обозначим через
Имеем, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.
Для транзитных переходов имеем, так как при каждом выполнении операции НАЙТИ происходит не болеепереходов из одного диапазона в другой.
Для оценки величины введем потенциалузла после выполнения операции . Если к узлу еще не применялась операция СОЗДАТЬ, то.
Потенциалом группыпри текущем состоянии коллекции назовем величину
Очевидно, что в любой момент времени справедливо неравенство
(1) |
