Материал из Викиконспекты
|
|
| (не показаны 23 промежуточные версии 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> времени.
| |
| − | }}
| |
Текущая версия на 00:56, 22 марта 2012
