Изменения

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

Предположим теперь, что каждый список включает также поле длины списка и что мы всегда добавляем меньший список к большему(при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой эвристике одна операция UNION union может потребовать омега эн <tex>omega(n)</tex> действий, если оба множества имеют омега эн <tex>omega(n)</tex> членов. Однако последовательность из m операций MAKE_SETmakeSet, UNION union и FIND_SETfindSet, n из которых составляют операции MAKE_SETmakeSet, требует для выполнения <tex>O(m + n logn\lgn) </tex> времени.

|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций MAKE_SETmakeSet, UNIONunion, и FIND_SETfindSet, <tex>n</tex> из которых составляют операции MAKE_SETmakeSet, требует для выполнения <tex>O(m+n </tex> \lg <tex> n)</tex> времени.|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из <tex>n</tex> элементов. Рассмотрим некий фиксированный объект n. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при <tex>k \leqslant\ n</tex>, после того как указатель на представителя в объекте обновлен <tex>\left\lceil lg\ k \right\rceil</tex>, полученное в результате множество должно иметь не менее <tex>k</tex> элементов. Поскольку максимальное множество может иметь не более <tex>n</tex> элементов, во всех операциях UNION union указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \lg\ n \right\rceil</tex> раз. Необходимо также отметить, что обновление <tex>head</tex> и <tex>tail</tex> и длины списка при выполнении операции UNION union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления <tex>n</tex> объектов, составляет <tex>O(n </tex> \lg <tex> n)</tex>}}.Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + nlgnn \lg n)</tex>. <tex>O(m) </tex> операций MAKE_SET makeSet и FIND_SETfindSet, работающих за константное время и суммарное время работы операций UNION union для каждого объекта.