Несложная сложность поиска и объединение операции

Question

Я изучаю алгоритм о непересекающихся множествах.

И глава Fast FIND Implementation (Quick Find)

структура данных показана ниже:

, например)

int array[5] 

[0] = 3, 
[1] = 5, 
[2] = 7, 
[3] = 1, 
[4] = 2, 

В [number] = set name (выше примере), число является элементом во имя набора.

Таким образом, число 0 находится в наборе 3, номер 1 в наборе 5, .. и т.д.

Для этого союза (а, б) (при условии, что в наборе я и б находится в множестве j), ему нужны операции O (n). Я знаю это. Причина показана ниже (Псевдо-код):

void Union(a, b) { 
     int set1 = Find(a); /* set 1 will be 'i' */ 
     int set2 = Find(b); /* set 2 will be 'j' */ 

     if(set 1 != set2) 
      for(int i = 0; i < sizeof(array); i++) { /* O(n) operation */ 
       if(array[i] == set1) 
        array[i] = set2; 
      } 
} 

Но, в книге, я не могу понять это:

Последовательность п - 1 союзов взять O (N^2) время в худшем случае. Если есть операции O (n^2) FIND, эта производительность прекрасна, так как средняя временная сложность O (1) для каждой операции UNION или FIND. Если число FIND меньше, эта сложность неприемлема.

Я не могу понять, в чем смысл этого предложения, и почему сложность O (n^2). Не могу представить эту сложность, как код, который я пишу выше.

Answer 1

Мы хотим сделать общую сложность для всех операций максимально возможной.

Общая сложность = сложность (FIND) + сложность (UNION)

Как вы заявили, если задано, что последовательность из п - 1 союзами взять O (N^2) время, в худшем случае. И найти принимает O (1) в среднем.

Итак, для операций объединения n-1, сколько мы можем найти, без увеличения общей сложности, превышающей O (n^2).

Ответ: O (n^2) операции поиска могут поддерживаться.

Так что, пока количество FIND является < = O (N^2) и количество UNION является < = О (п). Сложность остается такой же.

Общее правило: Чем тяжелее работа (больше времени) следует использовать как меньшее число раз, как вес более легкой работу и зажигалку операция должна быть использована как многое количество раз, как вес тяжелой работы.

Надеюсь, этого достаточно.