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