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

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

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

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

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

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

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

[math]\triangleright[/math]

Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из [math]n[/math] элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, после первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Таким образом, при [math]k \leqslant\ n[/math], после того как указатель на представителя в объекте обновлен [math]\left\lceil lg\ k \right\rceil[/math], полученное в результате множество должно иметь не менее [math]k[/math] элементов. Но максимальное множество может иметь не более [math]n[/math] элементов. Значит указатель на каждом объекте поменяется не более [math]\left\lceil lg\ n \right\rceil[/math] раз. Обновления [math]head[/math] и [math]tail[/math] и длины списка, для выполнения операции UNION требуется [math]O(1)[/math] времени. Таким образом, общее время, для обновления [math]n[/math] объектов, составляет [math]O(n [/math] lg [math] n)[/math]

[math]\triangleleft[/math]

• Т. Кормен и остальные. Весовая эвристика, стр. 587 (2е издание)