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

Question

Поэтому везде, где я вижу алгоритм поиска взвешенного объединения, они используют этот подход:

1. Поддерживает массив, указывающий на родительский узел определенного узла
2. Поддерживает массив, обозначающий размердерева, в котором находится узел
3. Для объединения (p, q) объедините меньшее дерево с большим

Временная сложность здесь O (lgN) * ​​1011 *

---

Теперь оптимизация заключается в том, чтобы сгладить деревья, т. Е. Всякий раз, когда я вычисляю корень определенного узла, устанавливаю все узлы на этом пути так, чтобы он указывал на этот корень.

Сложность этого времени равна O(LG * N)

---

Это я могу понять, но я не понимаю, почему они не начинают с массива / хэш-набора, где узлы указывают на корень (вместо непосредственногородительский узел)?Это снизит сложность времени до O (1).

Answer 1

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

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

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

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

Answer 2

Я собираюсь предположить, что сложность, которую вы запрашиваете, - это время, чтобы проверить, принадлежат ли 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)) времени для его выполнения, что сопоставимо с тем, сколько времени потребуется для запуска всего алгоритма без использования быстрого ярлыка.оптимизация.