Как сжатие пути в непересекающемся множестве может привести к O(log*n)

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

я читаю книгу "Алгоритм" С. Дасгупты на странице 145 и не могу понять, как сжатие пути меняется с O(log n) на O (log * n)

Спасибо!

0 ответов

Другие вопросы по тегам