Изменения

Не трудно привести последовательность из m операций над n объектами, которая требует <tex>O(n^2)</tex> времени. Предположим, что у нас есть объекты <tex>x_1, x_2, ... x_n</tex>. Мы выполняем последовательность из n операций makeSet (или init), за которой следует последовательность из n - 1 операции union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время <tex>O(n)</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>.

== Реализация с весовой эвристикой ==