Изменения

Перейти к: навигация, поиск

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

2 байта добавлено, 22:56, 23 апреля 2012
Проблема наивной реализации
== Проблема наивной реализации ==
[[Файл:ve.png|thumb|600px|Реализация без весовой эвристики]]
Рассмотрим реализацию системы непересекающихся множеств с помощью спискасписков, для каждого элемента которого будем хранить указатель на представителя и на следующий элемент. При такой реализации операция init для создания n множеств из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Хотя мы можем объединить два списка за <tex>O(1)</tex>, но обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов. Нетрудно придумать последовательность из n - 1 операций union, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку i-ая операция union обновляет i указателей, общее количество указателей, обновленных всеми n - 1 операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции union составляет <tex>O(n)</tex>.
== Реализация с весовой эвристикой ==
Анонимный участник

Навигация