Алгоритмы с нуля
Графы: тест на свободное припоминание
Припоминание сильнее перечитывания. Для каждой подсказки скажите или запишите полный ответ по памяти, прежде чем открыть модельный ответ, — именно усилие припоминания закрепляет материал.
Восстановите ключевые механизмы юнита — компромиссы представлений, BFS против DFS, topological sort, инвариант фиксации Dijkstra и амортизированную оценку union-find — не заглядывая в уроки.
- 01Когда выбирать adjacency list вместо adjacency matrix и сколько стоит каждое?
- 02BFS и DFS оба работают за O(V + E). Когда важен порядок и что даёт каждый?
- 03Что такое topological order, когда он существует и как два алгоритма обнаруживают цикл?
- 04Сформулируйте инвариант фиксации (settle) Dijkstra и объясните, почему он рушится при отрицательном ребре.
- 05Почему амортизированная стоимость union-find — O(alpha(n)), а не истинное O(1) или O(log n)?
- 06Связные компоненты можно искать через BFS/DFS или через union-find. Когда брать каждое?
Если вы смогли восстановить каждый ответ по памяти, вы держите хребет юнита: компромиссы представлений (list для разрежённых, matrix для плотных или O(1) поиска), BFS для путей с наименьшим числом рёбер и DFS для глубины и упорядочивания, topological sort со встроенным обнаружением циклов, инвариант фиксации Dijkstra и почему неотрицательные веса обязательны, и амортизированное O(alpha(n)) у union-find для динамической связности. Повторяющийся урок — подбирать алгоритм под форму задачи до написания кода.