Изменения

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

[[Файл:ve.png|thumbright|600px|Реализация без весовой эвристикиОценка количества переподвешиваний]]Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка. Кроме ссылок на следующий элемент будем хранить ссылку указатель на представителя, а для представителя ссылку и на голову списка. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} <tex>O(1)</tex>. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий следующий элемент y. При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x.

Не трудно привести последовательность из m операций над n объектами, которая требует При такой реализации операция <tex>O(n^2)\mathrm {init} </tex> времени. Предположим, что у нас есть объекты <tex>x_1, x_2, ... x_n</tex>. Мы выполняем последовательность из для создания n операций makeSet (или init), за которой следует последовательность множеств состоящих из n - 1 операции union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время одного элемента займет <tex>O(n)</tex>времени. Поскольку i-ая операция union обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями union равно Для выполнения операции <tex>\sum\limits_mathrm {i=1findSet}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения достаточно перейти по ссылке на представителя за <tex>O(n1)</tex>. Таким образом амортизированное время выполнения операции union составляет Узким местом такой реализации является операция <tex>O(n)\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> \mathrm {union } </tex> по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов. Однако , но последовательность из m <tex>n</tex> операций makeSet, <tex> \mathrm {union и findSet, n из которых составляют операции makeSet, } </tex> требует для выполнения <tex>O(m + 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 O(\log k \right\rceiln)</tex>. Таким образом, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более общее время, необходимое для обновления указателей для n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более составляет <tex>\left\lceil O(n \log n \right\rceil)</tex> раз.

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