СНМ(списки с весовой эвристикой) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 6: Строка 6:
  
 
== Проблема наивной реализации ==
 
== Проблема наивной реализации ==
 
+
[[Файл:ve.png|thumb|600px|Реализация без весовой эвристики]]
 
Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий  элемент будем хранить ссылку на представителя, а для представителя ссылку на голову списка. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} <tex>O(1)</tex>. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y.  При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует <tex>O(n^2)</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_{i=1}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения <tex>O(n)</tex>. Таким образом амортизированное время выполнения операции union составляет <tex>O(n)</tex>. В худшем случае представленная реализация процедуры union требует в среднем <tex>O(n)</tex> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.
 
Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий  элемент будем хранить ссылку на представителя, а для представителя ссылку на голову списка. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} <tex>O(1)</tex>. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y.  При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует <tex>O(n^2)</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_{i=1}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения <tex>O(n)</tex>. Таким образом амортизированное время выполнения операции union составляет <tex>O(n)</tex>. В худшем случае представленная реализация процедуры union требует в среднем <tex>O(n)</tex> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.
 
[[Файл:ve.png]]
 
  
 
== Реализация с весовой эвристикой ==
 
== Реализация с весовой эвристикой ==
Строка 19: Строка 17:
 
{{Утверждение
 
{{Утверждение
 
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из m операций makeSet, union, и findSet, n из которых составляют операции makeSet, требует для выполнения <tex>O(m+n \log n)</tex> времени.
 
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из m операций makeSet, union, и findSet, n из которых составляют операции makeSet, требует для выполнения <tex>O(m+n \log n)</tex> времени.
|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из n элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \log n \right\rceil</tex> раз. Необходимо также отметить, что обновление указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления n объектов, составляет <tex>O(n \log n)</tex>.
+
|proof = [[Файл:ve2.png|thumb|600px|Оценка количества переподвешиваний]] Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из n элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \log n \right\rceil</tex> раз. Необходимо также отметить, что обновление указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления n объектов, составляет <tex>O(n \log n)</tex>.
 
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. <tex>O(m)</tex> операций makeSet и findSet, работающих за константное время и суммарное время работы операций union для каждого объекта.}}
 
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. <tex>O(m)</tex> операций makeSet и findSet, работающих за константное время и суммарное время работы операций union для каждого объекта.}}
 
[[Файл:ve2.png]]
 
  
 
== Другие реализации ==
 
== Другие реализации ==

Версия 20:52, 18 марта 2012

Определение

Определение:
Весовая эвристика(weighted-union heuristic) — улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.


Проблема наивной реализации

Реализация без весовой эвристики

Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий элемент будем хранить ссылку на представителя, а для представителя ссылку на голову списка. При использовании такого представления, время работы процедур makeSet и findSet — [math]O(1)[/math]. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y. При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует [math]O(n^2)[/math] времени. Предположим, что у нас есть объекты [math]x_1, x_2, ... x_n[/math]. Мы выполняем последовательность из n операций makeSet(или init), за которой следует последовательность из n - 1 операции union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время [math]O(n)[/math]. Поскольку i-ая операция union обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями union равно [math]\sum\limits_{i=1}^{n-1} i = O(n^2)[/math]. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения [math]O(n)[/math]. Таким образом амортизированное время выполнения операции union составляет [math]O(n)[/math]. В худшем случае представленная реализация процедуры union требует в среднем [math]O(n)[/math] времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.

Реализация с весовой эвристикой

Предположим теперь, что каждый список включает также поле длины списка и что мы всегда добавляем меньший список к большему(при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой эвристике одна операция union может потребовать [math]\Omega(n)[/math] действий, если оба множества имеют [math]\Omega(n)[/math] членов. Однако последовательность из m операций makeSet, union и findSet, n из которых составляют операции makeSet, требует для выполнения [math]O(m + n \log n)[/math] времени.

Доказательство оценки времени выполнения

Утверждение:
При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из m операций makeSet, union, и findSet, n из которых составляют операции makeSet, требует для выполнения [math]O(m+n \log n)[/math] времени.
[math]\triangleright[/math]
Оценка количества переподвешиваний
Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из n элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при k [math]\leqslant\[/math] n, после того как указатель на представителя в объекте обновлен [math]\left\lceil \log k \right\rceil[/math], полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более [math]\left\lceil \log n \right\rceil[/math] раз. Необходимо также отметить, что обновление указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует [math]O(1)[/math] времени. Таким образом, общее время, необходимое для обновления n объектов, составляет [math]O(n \log n)[/math]. Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит [math]O(m + n \log n)[/math]. [math]O(m)[/math] операций makeSet и findSet, работающих за константное время и суммарное время работы операций union для каждого объекта.
[math]\triangleleft[/math]

Другие реализации

Источники

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4

Ссылки