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