Изменения
→Проблема наивной реализации
== Проблема наивной реализации ==
[[Файл:ve.png|thumb|400px|Реализация без весовой эвристики]]
Рассмотрим реализацию системы непересекающихся множеств с помощью списков, для каждого элемента которых будем хранить указатель на представителя и на следующий элементв списке.
При такой реализации операция init для создания n множеств из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Хотя мы можем объединить два списка за <tex>O(1)</tex>, но обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
