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