Изменения

Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий элемент , для каждого элемента которого будем хранить ссылку указатель на представителя, а для представителя ссылку и на голову спискаследующий элемент. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} такой реализации операция init для создания n множеств из одного элемента очевидно займет <tex>O(1n)</tex>времени. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y. При этом мы должны обновить указатели Для выполнения операции findSet достаточно просто перейти по ссылке на представителя у каждого объекта, который содержался в списке, содержащем x.  Не трудно привести последовательность из m операций над n объектами, которая требует за <tex>O(n^21)</tex> времени. Предположим, что у нас есть объекты Узким местом такой реализации является операция union. Хотя мы и можем объединить два списка за <tex>x_1, x_2, ... x_nO(1)</tex>. Мы выполняем последовательность , но обновить указатели на представителя для одного из n операций makeSet (или init), списков мы можем лишь за которой следует время пропорциональное количеству элементов. Нетрудно придумать последовательность из n - 1 операции операций union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время , требующую <tex>O(n^2)</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> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.