почему сложность O (n log n) времени для выполнения n операций поиска объединения (объединения по размеру)?

Question

В древовидной реализации операции поиска объединения каждый элемент хранится в узле, который содержит указатель на заданное имя. Узел v, указатель набора которого указывает на v, также является именем набора. Каждый набор представляет собой дерево, корни которого находятся в узле с указателем самоссылающихся наборов. Чтобы выполнить объединение, мы просто указываем, что корень одного дерева указывает на корень другого. Чтобы выполнить поиск, мы следуем указателям набора имен от начального узла до достижения узла, указатель имени набора которого ссылается на себя.

В Союзе по размеру -> При выполнении объединения мы делаем корень меньшего дерева указать на корень большего. Это подразумевает O (n log n) время для выполняя n операции поиска. Каждый раз, когда мы следуем за указателем, мы собираемся получить поддерево размером не более чем в два раза больше предыдущего поддерева. Таким образом, мы будем следовать не более O (log n) указателям для любой находки.

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

Answer 1

Вы можете выполнить n операций поиска (объединения по рангу или размеру) со сложностью O (n lg * n) , где lg * n - это обратная функция Аккермана , использующая оптимизация сжатия пути .

Обратите внимание, что O (n lg * n) лучше, чем O (n log n)

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

Answer 2

Предположим на данный момент, что каждое дерево высотой h содержит не менее 2 ^ h узлов. Что произойдет, если вы соедините два таких дерева?

Если они имеют разные размеры, высота объединенного дерева равна высоте более высокого, таким образом, новое дерево все еще имеет более 2 ^ h узлов (такая же высота, но больше узлов).

Теперь, если они имеют одинаковую высоту, результирующее дерево увеличит свою высоту на один и будет содержать не менее 2 ^ h + 2 ^ h = 2 ^ (h + 1) узлов. Таким образом, условие все еще будет выполняться.

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

Теперь высота - это максимальное количество шагов, которые нужно выполнить во время поиска. Если дерево имеет n узлов и высоту h (n> = 2 ^ h), это сразу дает log2 (n)> = h> = steps.