Изменения

Рассмотрим реализацию системы непересекающихся множеств с помощью списка, для каждого элемента которого будем хранить указатель на представителя и на следующий элемент. При такой реализации операция init для создания n множеств из одного элемента очевидно займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно просто перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Хотя мы и можем объединить два списка за <tex>O(1)</tex>, но обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов. Нетрудно придумать последовательность из n - 1 операций union, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку i-ая операция union обновляет i указателей, общее количество указателей, обновленных всеми n - 1 операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции union составляет <tex>O(n)</tex>.

Очевидным минусом Минусом наивной реализации являлось то, что при слиянии двух множеств, например относительно большого и из одного элемента, мы пытались обновить указатели для большого числа элементов, хотя гораздо быстрее было бы поменять указатель лишь одному. Отсюда следуют очевидная оптимизация - давайте будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Эта оптимизация называется весовой эвристикой и позволяет добиться асимптотики <tex>O(n \log n)</tex> для n - операций union. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов.