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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Весовая эвристика == {{Определение| definition = '''Весовая эвристика''' - улучшение наивной реал…»)
 
Строка 3: Строка 3:
 
definition =  
 
definition =  
 
'''Весовая эвристика''' - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 
'''Весовая эвристика''' - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 +
}}
 +
 +
== Оценка для весовой эвристики ==
 +
 +
{{Утверждение
 +
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций MAKE_SET, UNION, и FIND_SET, <tex>n</tex> из которых составляют операции MAKE_SET, требует для выполнения <tex>O(m+n </tex> lg <tex> n)</tex> времени.
 
}}
 
}}

Версия 21:20, 7 марта 2011

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

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


Оценка для весовой эвристики

Утверждение:
При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из [math]m[/math] операций MAKE_SET, UNION, и FIND_SET, [math]n[/math] из которых составляют операции MAKE_SET, требует для выполнения [math]O(m+n [/math] lg [math] n)[/math] времени.