Изменения

|proof = [[Файл:ve2.png|thumb|600px|Оценка количества переподвешиваний]] Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из n элементовэлемента. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объектеэлементе, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \log n \right\rceil</tex> раз. Таким образом, общее время, необходимое для обновления n объектов, составляет <tex>O(n \log n)</tex>.

Необходимо также отметить, что обновление указателя на голову слить два списка и next представителя, а также обновление длины списка обновить поле длинны при выполнении операции union требует можно легко за <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления n объектов, составляет <tex>O(n \log n)</tex>.

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