Изменения

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

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

1 байт добавлено, 15:45, 23 апреля 2012
Доказательство оценки времени выполнения
Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно за <tex>O(1)</tex>.
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. <tex>O(m)</tex> операций makeSet, findSet и часть работы операции union на обновление поля длины и слияния списков, каждая из которых выполняется за константное время и суммарное время обновления указателей на представителя операцией union для каждого элемента.}}
== Другие реализации ==
Анонимный участник

Навигация