Алгоритм объединения/находить без объединения разрядом для лесной структуры данных непересекающегося набора

Вот разбивка на алгоритме объединения/находить для непересекающихся лесов набора на Википедию:

  • Базовые леса непересекающегося набора... (O(n))
    • ... с объединением разрядом... (теперь улучшенный до O(log(n))
      • ... со сжатием пути (теперь улучшенный до O(a(n)), эффективно O(1))

Реализация объединения разрядом требует того каждого узла, сохраняет a rank поле в целях сравнения. Мой вопрос, объединение разрядом, стоящим этого дополнительного пространства? Что происходит, если я пропускаю объединение разрядом и просто соединяю сжатие каналом вместо этого? Действительно ли это достаточно хорошо? Какова амортизируемая сложность теперь?


Комментарий сделан, который подразумевает что объединение разрядом без сжатия пути (амортизируемый O(log(n) сложность), достаточно для наиболее практического применения. Это корректно. То, что я спрашиваю, наоборот: что, если Вы пропускаете объединение разрядом и ТОЛЬКО соединяете сжатие каналом вместо этого?

В некотором смысле сжатие пути является дополнительным шагом для улучшения объединения разрядом, и вот почему что дополнительный шаг может быть опущен без катастрофического последствия. Но является объединение разрядом необходимым промежуточным шагом для соединения каналом сжатия? Я могу пропустить его и пойти прямо для соединения каналом сжатия, или это будет катастрофически?


Было также указано, что без объединения разрядом, повторные объединения могли создать связанный список как структура. Это означает, что единственная операция сжатия пути могла взять O(n) в худшем случае. Это, конечно, влияло бы на будущие операции, поэтому как это теряет значение при амортизации по многим операциям то, чем я больше интересуюсь.

16
задан polygenelubricants 1 March 2010 в 23:36
поделиться

2 ответа

Я набрал в гугле "без профсоюза по званию" и второй ссылкой, которая появилась, была эта:

...Мы завершаем этот раздел анализом анализом метода union-find со сжатием пути сжатием, но без объединения по рангу...

Структура данных union-find со сжатием пути сжатием пути, но без объединения по рангу обрабатывает m операций поиска и n-1 операций соединения за время O((m+n) log n)

7
ответ дан 30 November 2019 в 23:21
поделиться

Сжатие пути сглаживает древовидную структуру. Союз по рангу помогает сливаться. Предположим, что вы пропускаете последнее. Итак, теперь у вас есть лес без информации о ранге, чтобы выбрать способ слияния. Возможно, теперь вы рискуете объединить дерево с большей глубиной с деревом с меньшей глубиной, что приведет к несбалансированной древовидной структуре. В худшем случае вы можете получить связанный список. Амортизированная временная сложность вашего Союза увеличивается, даже если для Find остается прежним.

IMO, Было бы лучше пропустить сжатие пути, но не ранжирование.

1
ответ дан 30 November 2019 в 23:21
поделиться
Другие вопросы по тегам:

Похожие вопросы: