СНМ(списки с весовой эвристикой) — различия между версиями
Linn (обсуждение | вклад) (Новая страница: «== Весовая эвристика == {{Определение| definition = '''Весовая эвристика''' - улучшение наивной реал…») |
Linn (обсуждение | вклад) |
||
| Строка 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
Весовая эвристика
| Определение: |
| Весовая эвристика - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему. |
Оценка для весовой эвристики
| Утверждение: |
При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из операций MAKE_SET, UNION, и FIND_SET, из которых составляют операции MAKE_SET, требует для выполнения lg времени. |
