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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оценка для весовой эвристики)
Строка 2: Строка 2:
 
{{Определение|
 
{{Определение|
 
definition =  
 
definition =  
'''Весовая эвристика''' - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
+
'''Весовая эвристика'''(weighted-union heuristic) - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 
}}
 
}}
  
== Оценка для весовой эвристики ==
+
== Проблема наивной реализации ==
 +
 
 +
Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий  элемент будем хранить ссылку на представителя(голову списка). При использовании такого представления время работы процедур MAKE_SET, FIND_SET O(1). Процедуру UNION(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y.  При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует O(n^2) времени. Предположим, что у нас есть объекты x1, x2, ... xn. Мы выполняем последовательность из n операций MAKE_SET, за которой следует последовательность из n - 1 операции UNION. m = n + (n - 1) = 2n - 1. На выполнение n операций MAKE_SET мы тратим время O(n). Поскольку i-я операция UNION обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями UNION равно (сумма i..n-1: i = O(n^2)). Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения времени O(n). Таким образом амортизированное время выполнения операции UNION составляет O(N). В худшем случае представленная реализация процедуры UNION требует в среднем O(n) времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.
 +
 
 +
== Реализация с весовой эвристикой ==
 +
 
 +
Предположим теперь, что каждый список включает также поле длины списка и что мы всегда добавляем меньший список к большему(при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой эвристике одна операция UNION может потребовать омега эн действий, если оба множества имеют омега эн членов. Однако последовательность из m операций MAKE_SET, UNION и FIND_SET, n из которых составляют операции MAKE_SET, требует для выполнения O(m + n logn) времени.
 +
 
 +
== Доказательство оценки времени выполнения ==
  
 
{{Утверждение
 
{{Утверждение
 
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций MAKE_SET, UNION, и FIND_SET, <tex>n</tex> из которых составляют операции MAKE_SET, требует для выполнения <tex>O(m+n </tex> lg <tex> n)</tex> времени.
 
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций MAKE_SET, UNION, и FIND_SET, <tex>n</tex> из которых составляют операции MAKE_SET, требует для выполнения <tex>O(m+n </tex> lg <tex> n)</tex> времени.
|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из <tex>n</tex> элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Таким образом, при <tex>k \leqslant\ n</tex>, после того как указатель на представителя в объекте обновлен <tex>\left\lceil lg\ k \right\rceil</tex>, полученное в результате множество должно иметь не менее <tex>k</tex> элементов. Но максимальное множество может иметь не более <tex>n</tex> элементов. Значит указатель на каждом объекте поменяется не более <tex>\left\lceil lg\ n \right\rceil</tex> раз. Обновления <tex>head</tex> и <tex>tail</tex> и длины списка, для выполнения операции UNION требуется <tex>O(1)</tex> времени. Таким образом, общее время, для обновления <tex>n</tex> объектов, составляет <tex>O(n </tex> lg <tex> n)</tex>}}
+
|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из <tex>n</tex> элементов. Рассмотрим некий фиксированный объект n. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при <tex>k \leqslant\ n</tex>, после того как указатель на представителя в объекте обновлен <tex>\left\lceil lg\ k \right\rceil</tex>, полученное в результате множество должно иметь не менее <tex>k</tex> элементов. Поскольку максимальное множество может иметь не более <tex>n</tex> элементов, во всех операциях UNION указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil lg\ n \right\rceil</tex> раз. Необходимо также отметить, что обновление <tex>head</tex> и <tex>tail</tex> и длины списка при выполнении операции UNION требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления <tex>n</tex> объектов, составляет <tex>O(n </tex> lg <tex> n)</tex>}}
 +
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит O(m + nlgn). O(m) операций MAKE_SET и FIND_SET, работающих за константное время и суммарное время работы операций UNION для каждого объекта.
  
 
*Т. Кормен и остальные. Весовая эвристика, стр. 587 (2е издание)
 
*Т. Кормен и остальные. Весовая эвристика, стр. 587 (2е издание)

Версия 00:48, 12 марта 2012

Весовая эвристика

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


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

Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий элемент будем хранить ссылку на представителя(голову списка). При использовании такого представления время работы процедур MAKE_SET, FIND_SET O(1). Процедуру UNION(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y. При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует O(n^2) времени. Предположим, что у нас есть объекты x1, x2, ... xn. Мы выполняем последовательность из n операций MAKE_SET, за которой следует последовательность из n - 1 операции UNION. m = n + (n - 1) = 2n - 1. На выполнение n операций MAKE_SET мы тратим время O(n). Поскольку i-я операция UNION обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями UNION равно (сумма i..n-1: i = O(n^2)). Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения времени O(n). Таким образом амортизированное время выполнения операции UNION составляет O(N). В худшем случае представленная реализация процедуры UNION требует в среднем O(n) времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.

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

Предположим теперь, что каждый список включает также поле длины списка и что мы всегда добавляем меньший список к большему(при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой эвристике одна операция UNION может потребовать омега эн действий, если оба множества имеют омега эн членов. Однако последовательность из m операций MAKE_SET, UNION и FIND_SET, n из которых составляют операции MAKE_SET, требует для выполнения O(m + n logn) времени.

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

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

Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит O(m + nlgn). O(m) операций MAKE_SET и FIND_SET, работающих за константное время и суммарное время работы операций UNION для каждого объекта.

  • Т. Кормен и остальные. Весовая эвристика, стр. 587 (2е издание)