Почему временная сложность операции в алгоритме взвешенного объединения составляет O(lgN)?

Я собираюсь предположить, что временная сложность, которую вы запрашиваете, - это время, чтобы проверить, принадлежат ли 2 узла одному и тому же набору.

Ключ в том, как наборы соединяются, в частности, вы берете корень одного набора (меньшего) и указываете на корень другого набора. Пусть два набора имеют p и q в качестве корней соответственно, а |p| будет представлять размер набора p, если p является корнем, в то время как в общем случае это будет количество элементов, путь набора которых проходит через p (что равно 1 + все его дети).

Мы можем без ограничения общности считать, что |p| <= |q| (иначе мы просто поменяем их именами). Затем у нас есть |p u q| = |p|+|q| >= 2|p|. Это показывает нам, что каждое поддерево в структуре данных может быть максимум вдвое меньше своего родителя, поэтому при наличии N элементов оно может иметь глубину не более 1+lg N = O(lg(N)).

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

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

Вы правы в том, что предлагаемое вами решение снизит временную сложность операции поиска до O (1). Однако это замедлит работу Союза.

Представьте, что вы используете массив/хэш-таблицу для запоминания представителя (или корня, как вы его называете) каждого узла. Когда вы выполняете операцию объединения между двумя узлами x и y, вам нужно либо обновить все узлы с тем же представителем, что и x, чтобы получить представителя y, либо наоборот. Таким образом, объединение выполняется в O(min{|Sx|, |Sy|}), где Sx — это набор узлов с тем же представителем, что и x. Эти наборы могут быть значительно больше, чем log n.

Алгоритм взвешенного объединения, с другой стороны, имеет O(log n) как для поиска, так и для

Так что это компромисс. Если вы планируете выполнять много операций Find, но мало операций Union, вам следует использовать предложенное вами решение. Если вы планируете выполнять многие из них, вы можете использовать алгоритм взвешенного объединения, чтобы избежать слишком медленных операций.