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