Изменения

== Определение =={{Определение|definition = '''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большемупри объединении множеств.}}

[[Файл:ve.png|thumbright|600px|Реализация без весовой эвристикиОценка количества переподвешиваний]]Рассмотрим реализацию системы непересекающихся множеств с помощью списка, для списков. Для каждого элемента которого списка будем хранить указатель на представителя и на следующий элементв списке.  При такой реализации операция <tex> \mathrm {init } </tex> для создания n множеств состоящих из одного элемента очевидно займет <tex>O(n)</tex> времени. Для выполнения операции <tex> \mathrm {findSet } </tex> достаточно просто перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Хотя мы и можем объединить два списка за <tex>O(1)\mathrm {union} </tex>, но . Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.  Нетрудно придумать последовательность из <tex>n - 1 </tex> операций <tex> \mathrm {union} </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>. Отсюда следует, что амортизированное время выполнения операции <tex> \mathrm {union } </tex> составляет <tex>O(n)</tex>.

Очевидным минусом Недостаток наивной реализации являлось то, что проявляется при слиянии двух множеств, например относительно большого и множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, мы пытались обновить указатели для вместо обновления большого числа элементов, хотя гораздо быстрее было бы поменять указатель лишь одномууказателей в первом списке. Отсюда следуют очевидная оптимизация {{ - давайте -- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Эта оптимизация называется весовой эвристикой и позволяет добиться асимптотики Хотя одна операция <tex>O(n \log n)mathrm {union} </tex> для n - операций union. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций <tex> \mathrm {union} </tex> требует <tex>O(n \log n)</tex> действий. '''Псевдокод:''' s[n] '''function''' init(): '''for''' i = 0 '''to''' n - 1 s[i].set = i <font color = "green">// номер-идентификатор множества</font> s[i].next = null s[i].head = s[i] s[i].tail = s[i] <font color = "green">// храним только для представителя</font> s[i].count = 1 <font color = "green">// храним только для представителя</font> '''T''' find(x): <font color = "green">// подразумевается, что x {{ --- }} ссылка на один из элементов</font> '''return''' x.head.set '''function''' union(x, y): x = x.head y = y.head '''if''' x == y '''return''' '''else''' '''if''' x.count > y.count swap(x, y) i = x.head '''while''' i != null i.head = y i = i.next y.tail.next = x.head <font color = "green">// соединили списки</font> y.tail = x.tail y.count += x.count

|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> раз.  Таким образом, общее время, необходимое для обновления указателей для n объектовэлементов, составляет <tex>O(n \log n)</tex>.

Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно легко за <tex>O(1)\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> и часть работы операции <tex> \mathrm {union } </tex> на обновление поля длины и слияния списков, каждая из которых выполняется за константное время и , а также суммарное время обновления указателей на представителя операцией <tex> \mathrm {union } </tex> для каждого объектаэлемента за <tex>O(n \log n)</tex> действий.}}