Изменения
→Доказательство оценки времени выполнения
|proof = [[Файл:ve2.png|thumb|400px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях union. Рассмотрим количество обновлений отдельно для каждого элемента.
Оказывается, что для каждого элемента мы можем обновить указатель не более <tex>O(\log n)</tex> раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве , в котором не менее двух элементов, после второго {{ --- }} четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит <tex>O(\log n)</tex>.
Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет <tex>O(n \log n)</tex>.
Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно за константное количество операций (последние три строчки в псевдокоде).
Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция init за <tex>O(n)</tex>, <tex>O(m)</tex> операций findSet и часть работы операции union на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией union для каждого элементаза <tex>O(n \log n)</tex> действий.
}}
