Изменения

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

Список заданий по ДМ-сем2

1 байт добавлено, 22:58, 14 марта 2014
Нет описания правки
# Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
# СНМ на списках с ранговой эвристикой. Будем хранить каждой множество в СНМ как список его элементов, каждый элемент знает голову, голова знает хвост. Тогда объедиенение двух списков происходит за время пропорциональное длине одного из них. Докажите, что если каждый раз добавлять меньший список к большему, суммарное время работы всех операций Union будет $O(n \log n)$.
# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k $ ребер
# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите, что в среднем время работы get будет $O(\log n)$.
</wikitex>
Анонимный участник

Навигация