СНМ(списки с весовой эвристикой)

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

Определение:

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

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

Утверждение:

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