Изменения

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

|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций makeSet, union, и findSet, <tex>n</tex> из которых составляют операции makeSet, требует для выполнения <tex>O(m+n \lg log 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 указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \lg\ n \right\rceil</tex> раз. Необходимо также отметить, что обновление <tex>head</tex> и <tex>tail</tex> указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления <tex>n</tex> объектов, составляет <tex>O(n \lg n)</tex>.