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