Изменения

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

При такой реализации операция init для создания n множеств из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Хотя мы можем объединить два списка за <tex>O(1)</tex>, но Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.

Нетрудно придумать последовательность из <tex>n - 1 </tex> операций union, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция union обновляет <tex>i </tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1 </tex> операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции union составляет <tex>O(n)</tex>.