215
правок
Изменения
→Реализация с весовой эвристикой
== Проблема наивной реализации ==
[[Файл:ve.png|thumbright|600px|Реализация без весовой эвристикиОценка количества переподвешиваний]]Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка. Кроме ссылок на следующий элемент будем хранить ссылку указатель на представителя, а для представителя ссылку и на голову спискаследующий элемент в списке. При использовании такого представления, время работы процедур makeSet и findSet такой реализации операция <tex> \mathrm {{ --- }init} </tex> для создания n множеств состоящих из одного элемента займет <tex>O(1n)</tex>времени. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y. При этом мы должны обновить указатели Для выполнения операции <tex> \mathrm {findSet} </tex> достаточно перейти по ссылке на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует за <tex>O(n^21)</tex> времени. Предположим, что у нас есть объекты Узким местом такой реализации является операция <tex>x_1, x_2, ... x_n\mathrm {union} </tex>. Мы выполняем последовательность Слить списки и обновить указатели на представителя для одного из n операций makeSet(или init), списков мы можем лишь за которой следует время пропорциональное количеству элементов. Нетрудно придумать последовательность из <tex>n - 1 операции </tex> операций <tex> \mathrm {union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время } </tex>, требующую <tex>O(n^2)</tex>времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция <tex> \mathrm {union } </tex> обновляет <tex>i объектов</tex> указателей, общее количество объектовуказателей, обновленных всеми <tex>n - 1 </tex> операциями <tex> \mathrm {union } </tex> равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1Отсюда следует, так что каждая операция в среднем требует для выполнения <tex>O(n)</tex>. Таким образом амортизированное время выполнения операции union составляет <tex>O(n)\mathrm {union} </tex>. В худшем случае представленная реализация процедуры union требует в среднем составляет <tex>O(n)</tex> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.
== Реализация с весовой эвристикой ==
== Доказательство оценки времени выполнения ==
{{Утверждение
|statement=При использовании связанных списков для представления реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции <tex> \mathrm {init} </tex> для n элементов и m операций makeSet, <tex> \mathrm {union, } </tex> и <tex> \mathrm {findSet, n из которых составляют операции makeSet} </tex>, требует для выполнения <tex>O(m+n \log n)</tex> временидействий.|proof = [[Файл:ve2.png|thumbright|600px|Оценка количества переподвешиваний]] Вычислим верхнюю границу количества обновлений указателя Оценим время работы необходимое для обновления указателей на представителя в операциях <tex> \mathrm {union} </tex>. Рассмотрим количество обновлений отдельно для каждого элемента. Оказывается, что для каждого множества из элемента мы можем обновить указатель не более <tex>O(\log n элементов)</tex> раз. Рассмотрим некий фиксированный Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Когда Действительно, так как мы обновляем указатель на представителя в объектеэлементу, он должен находиться то этот элемент находился в меньшем из множеств(согласно нашей эвристике), но тогда размер второго множества не меньше. СледовательноТогда после первого обновления элемент содержится в множестве, при первом обновлении образованное множество хранит в котором не менее 2 двух элементов, при втором не менее 4 элементовпосле второго {{ --- }} четырех, и ттак далее.д. Продолжая рассуждение приходим к выводу о томВ силу того, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не содержать более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен количество обновлений не более превосходит <tex>\left\lceil O(\log n \right\rceil</tex> раз. Необходимо также отметить, что обновление указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления указателей для n объектовэлементов, составляет <tex>O(n \log n)</tex>. Необходимо также отметить, что слить два списка и обновить поле длины при выполнении <tex> \mathrm {union} </tex> можно за константное количество операций (последние три строчки в псевдокоде). Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. Операция <tex> \mathrm {init} </tex> за <tex>O(n)</tex>, <tex>O(m)</tex> операций makeSet <tex> \mathrm {findSet} </tex> и findSetчасть работы операции <tex> \mathrm {union} </tex> на обновление поля длины и слияния списков, работающих каждая из которых выполняется за константное время и , а также суммарное время работы операций обновления указателей на представителя операцией <tex> \mathrm {union } </tex> для каждого объектаэлемента за <tex>O(n \log n)</tex> действий.}}
== Другие реализации ==
* [[СНМ(наивные реализации)]]
* [[СНМ(реализация с помощью леса корневых деревьев)]]
== Ссылки ==
* [http://habrahabr.ru/blogs/algorithm/104772/ habrahabr.ru - Система непересекающихся множеств и её применения]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4
[[Категория: Дискретная математика и алгоритмы]]