Википедия говорит, что объединение по рангу без сжатия пути дает сложную временную сложность , и что объединение по рангу и сжатию пути дает сложную временную сложность (где - обратная величина функции Аккермана). Однако в нем не упоминается время сжатия пути без ранга объединения, что я обычно реализую сам.
Какова амортизированная временная сложность объединения-поиска с оптимизацией сжатия пути, но без объединения путем оптимизации ранга?
complexity-theory
time-complexity
union-find
Филип Хаглунд
источник
источник
Ответы:
Зейдель и Шарир доказали в 2005 году [1], что использование сжатия пути с произвольным связыванием примерно сm операциями имеет сложность примерно O((m+n)log(n)) .
См. [1], Раздел 3 (Произвольное связывание): пустьf(m,n) обозначает время выполнения поиска объединения с m операциями и n элементами. Они доказали следующее:
Согласно [1], установка дает .k=⌈m/n⌉+1 f(m,n)≤(2m+n)log⌈m/n⌉+1n
Аналогичная оценка была дана с использованием более сложного метода Тарьяном и ван Леувеном в [2], раздел 3:
[1]: Р. Зейдель и М. Шарир. Нисходящий анализ сжатия пути. Siam J. Computing, 2005, Vol. 34, № 3, с. 515-525.
[2]: Р. Тарьян и Дж. Ван Леувен. Наихудший анализ алгоритмов объединения множеств. J. ACM, Vol. 31, № 2, апрель 1984, с. 245-281.
источник
Я не знаю, каково амортизированное время выполнения, но я могу привести одну возможную причину, по которой в некоторых ситуациях вам может потребоваться использовать оба способа, а не просто сжатие пути: наихудшее время выполнения на операцию равно если вы используйте только сжатие пути, которое намного больше, чем если бы вы использовали объединение по рангу и сжатие пути.Θ(n)
источник