АиСД S01E08. Система непересекающихся множеств

Алгоритмы и структуры данных. Семестр 1. Лекция 8.

На восьмой лекции мы рассмотрели еще одну полезную структуру данных ‒ систему непересекающихся множеств (union-find).

Университет ИТМО, 2020 г.

[littleyoch]

00:00 - 01:50 Приветствие/название темы

01:51 - 9:15 Объяснение логики действий в целом

9:25 - 14:18 Примерный код "в лоб"

14:19 - 18:42 Оптимизация (создаем второй список, чтобы одно множество было в своем отдельном местечке, и не надо было бегать искать)

18:43 - 22:27- Считаем время на программу

22:28 - 27:57 Еще больше оптимизируем программу (Супер чит - объединяя множества, мы обязательно добавляем меньшее к большему, а не наоборот, чтобы передвигать меньше элементов) + считаем новое время O(log n) для union

27:58 - 30:14 Доп примечания

30:15 - 38:39 План - сделать быстрее, чем за log n. Новый способ хранить множества как смешные деревья с представителем в корне!! Теперь get() поднимается наверх по дереву, пока не вернет корень, а union() - подсоединяет один корень к другому (и магически получается одно дерево) + рассуждение о времени работы.

38:40 - 43:30 Как бороться с "бамбуком", по которому долго бежать. Подсоединяем маленькое дерево к большому (с рангами. Ранг - расстояние до самого далекого листа). Именно по рангам определяем размер дерева.

43:31 - 44:37 Фиксируем все в коде

44:38 - 47:47 Считаем время заново. Или сказ, как мы получили O(log n) + доказательства двух выражений о рангах.

47:47 - 49:29 Вопросики от аудитории

49:30 - 55:27 Идем оптимизировать get() - запоминаем ссылочку на корень (сжатие путей) + уточняем время для нового get()

55:28 - 59:31 Сжатие путей на сбалансированном дереве (ранговая эвристика) через функцию Аккермана.

59:31 - 1:20:04 Логарифм со звездочкой + доказательство, что время работы get() не больше чем _огромное число на доске_, крутые ребра.



Спасибо за супер крутую лекцию!

[cltbsgg]

Понятно когда СНМ храним в виде дерева, мы каждым элементом подмножества ссылаемся на корень дерева, это быстро брать и поправлять если что. А когда нам надо смерджить два множества то есть дерева, это же будет долго потому что надо каждую ссылку в одном из деревьев менять, это считается ли долго и так ли как я понял объединять два дерева? Просто акцент на этом не сделан или я не заметил

[rgqcsxh]

Почему ранг родителя 'x' увеличивается после каждого get на пути которого есть x. Ведь ранг корня может уменьшаться после get. Так почему ранг родителя, которым становится корень после первого же get, увеличивается каждый раз. Похоже, я неправильно понимаю устройство дерева. Правильно ли я понимаю, что дело в том, что get не меняет ранг и операции union и get перемешаны. И мы рассматриваем худший случай, который приводит к амортизированному времени get lg*n?