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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 20 промежуточных версий 4 участников)
Строка 1: Строка 1:
== Весовая эвристика ==
+
#перенаправление [[СНМ (списки с весовой эвристикой)]]
{{Определение|
 
definition =
 
'''Весовая эвристика''' - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 
}}
 
 
 
== Оценка для весовой эвристики ==
 
 
 
{{Утверждение
 
|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> элементов. Значит указатель на каждом объекте поменяется не более }}
 

Текущая версия на 00:56, 22 марта 2012