Почему DSU со сжатием путей и рангом даёт обратную Аккермана, а только со сжатием — O(log n)?
Везде пишут «почти O(1)» и «обратная функция Аккермана α(n)». Я понимаю, что α(n) ≤ 4, но не понимаю, откуда она берётся и почему нельзя обойтись одной оптимизацией. Если оставить только сжатие путей без ранга — что будет с асимптотикой?
2 ответа
Главная мысль: обе оптимизации нужны вместе, и доказательство амортизации — нетривиальное (Тарьян, 1975).
- Только объединение по рангу (без сжатия): высота дерева ≤ log₂(размера), поэтому
find— O(log n) в худшем случае. - Только сжатие путей (без ранга, объединение в произвольную сторону): тоже амортизированно O(log n) на операцию (точнее, Θ(log n) на запрос в среднем по последовательности).
- Обе вместе: амортизированно O(α(n)) на операцию, где α — обратная Аккермана. Это не строго O(1), но α(n) ≤ 4 для n < 2^65536, поэтому на практике — константа.
Интуиция за α: ранги вершин по пути растут «быстрее любой башни степеней», а сжатие переподвешивает их к корню, и потенциальная функция Тарьяна показывает, что суммарная работа ограничена α(n)·m для m операций. Подробный вывод — через разбиение рангов на «блоки» по функции Аккермана; на олимпиаде достаточно знать факт и что это амортизированная, а не худшая оценка одной операции.
Итого: для контеста считайте операцию DSU практически O(1), но в строгих оценках пишите O(α(n)) амортизированно.
Маленькое, но важное уточнение по терминологии для собеседований/разборов: α(n) в худшем случае на одну операцию может быть и больше — но амортизированно по последовательности из m операций над n элементами суммарное время O((n+m)·α(n)). То есть оценка про среднее по последовательности, а не гарантия на каждый отдельный find. Если в задаче критична именно гарантия на единичный запрос (онлайн с жёстким лимитом на ход), это стоит держать в голове.