Изменения

Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий элемент будем хранить ссылку на представителя, а для представителя ссылку на голову списка. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} <tex>O(1)</text>. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y. При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует <text>O(n^2)</tex> времени. Предположим, что у нас есть объекты <tex>x_1, x_2, ... x_n</tex>. Мы выполняем последовательность из n операций makeSet(или init), за которой следует последовательность из n - 1 операции union. <tex>m = n + (n - 1) = 2n - 1</tex>. На выполнение n операций makeSet мы тратим время <tex>O(n)</tex>. Поскольку i-я операция union обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения <tex>O(n)</tex>. Таким образом амортизированное время выполнения операции union составляет <tex>O(n)</tex>. В худшем случае представленная реализация процедуры union требует в среднем <tex>O(n)</tex> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.

== Реализация с весовой эвристикой ==