АиСД S01E08. Система непересекающихся множеств
HTML-код
- Опубликовано: 9 ноя 2020
- Алгоритмы и структуры данных. Семестр 1. Лекция 8.
На восьмой лекции мы рассмотрели еще одну полезную структуру данных ‒ систему непересекающихся множеств (union-find).
Университет ИТМО, 2020 г.
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() не больше чем _огромное число на доске_, крутые ребра.
-------------------------
Спасибо за супер крутую лекцию!
Понятно когда СНМ храним в виде дерева, мы каждым элементом подмножества ссылаемся на корень дерева, это быстро брать и поправлять если что. А когда нам надо смерджить два множества то есть дерева, это же будет долго потому что надо каждую ссылку в одном из деревьев менять, это считается ли долго и так ли как я понял объединять два дерева? Просто акцент на этом не сделан или я не заметил
В доте есть функция report
ок
Почему ранг родителя 'x' увеличивается после каждого get на пути которого есть x. Ведь ранг корня может уменьшаться после get. Так почему ранг родителя, которым становится корень после первого же get, увеличивается каждый раз. Похоже, я неправильно понимаю устройство дерева. Правильно ли я понимаю, что дело в том, что get не меняет ранг и операции union и get перемешаны. И мы рассматриваем худший случай, который приводит к амортизированному времени get lg*n?
Ранги никогда не уменьшаются, и могут меняться только у корня дерева. Ранг - это не настоящая глубина дерева, а глубина дерева, если бы оно не сжималось при операции get. "Ранг родителя увеличивается" - тут имеется в виду, что после операции get, родителем узла 'x' станет какой-то его предок, как минимум дед, а у этого нового родителя ранг строго больше, чем у старого родителя.
@@pavelmavrin понял. Большое спасибо!
В матлабе есть функция get)