Алгоритми та структури даних · Senior · Запитання 6 з 75
Що робить операції union-find майже O(1)?
- 1Зберігання кожної множини як відсортованого масиву
- ✓Правильна відповідь: Стиснення шляхів плюс об'єднання за рангом чи розміром
- 3Перебудова всієї структури після кожного об'єднання
Пояснення
Стиснення шляхів під час find направляє вузли прямо на корінь; об'єднання за рангом чіпляє нижче дерево під вище. Разом вони дають амортизоване O(α(n)), де α (обернена функція Акермана) менша за 5 для будь-якого реального n.