Анализируем Временную сложность алгоритма поиска объединения?

Question

Пожалуйста, дайте краткий и простой подход к анализу временной сложности алгоритма union-find. В двух случаях 1. Стандартный подход 2. Эвристический подход с взвешенным объединением

Я знаю, что в стандартной версии его временная сложность: O (n ^ 2), а в случае эвристического подхода с взвешенным объединением это: O (m + n logn)

Но я не понимаю, как это происходит. Предположение: Учтите, что существует n элементов и структура данных связанного списка, где каждый узел указывает на начало списка, m=make set.

Answer 1

Сначала несколько определений: m - это число операций make-set. n - сумма операций объединения / поиска.

Стандартная версия

При условии, что join(a,b) марки b корень a,

Если есть последовательность вызовов 0.5n вызовов как joint(1,2), joint(2,3), joint(3,4) Вы можете сделать цепочку из 0,5n узлов с 1 в нижней части. затем find(1) займет 0,5n времени, так что вызов 0,5n раз и время выполнения будет 0,25n^2=O(n^2)

Как мы должны сделать м makeset операции мы заканчиваем с O(m+n^2).

Взвешенный-Союз

Я предполагаю, что вес соответствует размеру набора (в отличие от ранга).

Для данного набора пусть h будет высотой представляющего его дерева и w его размера. find занимает не более часа времени в этом наборе. По индукции мы можем доказать, что h<=log(w).

Для одного узла, у которого w = 1 и h = 0, формула тривиально выполняется.

Теперь рассмотрим объединение двух деревьев a и b, где a становится новым корнем. Предполагая, что h<=log(w) выполняется для a и b, мы покажем, что оно также выполняется для объединения. Мы знаем, что wa>= wb => wab = wa + wb>= 2wb. Если a строго выше, чем b, мы имеем hab = ha <= log (wa) <= log (wab). В противном случае (когда hb>= ha) имеем hab = 1+hb <= 1+log(wb) = log(2wb) <= log(wab)

Это доказывает, что h<=log(w). Менее математически мы доказали, что высота любого набора меньше, чем логарифм его размера, поэтому нахождение занимает не более O (log (k)) времени, где k - размер набора.

Пусть j будет числом операций объединения. каждый union касается 2 элементов, поэтому максимальный размер любого множества ограничен 2j.

Следовательно, время выполнения объединения и находок составляет O (j + k log (2j)) = O (n + n log (2n)) = O (n log (n)). Снова мы должны сделать м makesets, итого мы получаем O(m + n log(n))