Сложность объединения-поиска с путём-сжатием без ранга

10

Википедия говорит, что объединение по рангу без сжатия пути дает сложную временную сложность O(logn) , и что объединение по рангу и сжатию пути дает сложную временную сложность (где - обратная величина функции Аккермана). Однако в нем не упоминается время сжатия пути без ранга объединения, что я обычно реализую сам.O(α(n))α

Какова амортизированная временная сложность объединения-поиска с оптимизацией сжатия пути, но без объединения путем оптимизации ранга?

Филип Хаглунд
источник
5
Обратите внимание, что является обратной функцией Аккермана, а не . Здесь «инверсия» означает инверсию как функцию, а не обратную: то есть, если , , а не . 1 / A ( n , n ) ) f ( n ) = A ( n , n ) α ( n ) = f - 1 ( n ) 1 / f ( n )α(n)1/A(n,n))f(n)=A(n,n)α(n)=f1(n)1/f(n)
DW
Я понимаю, что это относительно старый вопрос, но см. Мой ответ и соответствующий документ: epubs.siam.org/doi/abs/10.1137/S0097539703439088 . Я мог пропустить одну или две детали при копировании за пределы. В этом случае, пожалуйста, предложите изменить :-)
BearAqua

Ответы:

4

Зейдель и Шарир доказали в 2005 году [1], что использование сжатия пути с произвольным связыванием примерно с m операциями имеет сложность примерно O((m+n)log(n)) .

См. [1], Раздел 3 (Произвольное связывание): пусть f(m,n) обозначает время выполнения поиска объединения с m операциями и n элементами. Они доказали следующее:

Требование 3.1. Для любого целого числа имеем .k>1f(m,n)(m+(k1)n)logk(n)

Согласно [1], установка дает .k=m/n+1

f(m,n)(2m+n)logm/n+1n

Аналогичная оценка была дана с использованием более сложного метода Тарьяном и ван Леувеном в [2], раздел 3:

Лемма 7 из [2]. Предположим, что . В любой последовательности операций над множествами, реализованной с использованием любой формы сжатия и наивного связывания, общее количество узлов в путях поиска не При делении пополам и наивном связывании общее количество узлов в путях поиска составляет не более .mn(4m+n)log1+m/nn(8m+2n)log1+m/n(n)

Лемма 9 из [2]. Предположим, что . В любой последовательности операций над множествами, реализованной с использованием сжатия и наивного связывания, общее количество узлов в путях поиска составляет не более .m<nn+2mlogn+m

[1]: Р. Зейдель и М. Шарир. Нисходящий анализ сжатия пути. Siam J. Computing, 2005, Vol. 34, № 3, с. 515-525.

[2]: Р. Тарьян и Дж. Ван Леувен. Наихудший анализ алгоритмов объединения множеств. J. ACM, Vol. 31, № 2, апрель 1984, с. 245-281.

BearAqua
источник
2

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

nn1Θ(n)Θ(n)

O(logn)O(logn)O(logn) может быть полезно в интерактивном приложении, где вы хотите убедиться, что ни одна операция не может вызвать длительную задержку (например, вы хотите гарантировать, что ни одна операция не может вызвать зависание приложения в течение длительного времени) или в режиме реального времени приложение, в котором вы хотите убедиться, что вы всегда будете соответствовать гарантиям в реальном времени.

DW
источник