Алгоритм поиска союза

Question

Я читал о знаменитой проблеме union-find , и в книге говорилось: «либо поиск, либо объединение займут O(n) времени, а другой - O(1).... "

Но как насчет использования битовых строк для представления набора?Тогда и для объединения (с использованием бита ИЛИ), и для поиска (итерации по сет-листам с проверкой соответствующего бита 1) потребуется O(1) ..

Что не так с этой логикой?

Answer 1

Обе операции можно выполнить в амортизированном времени, равном O(Alpha(n)), где альфа представляет собой inverse of the Ackermann function (растет очень медленно) Вы должны представлять проблему как Форрест. Выберите представителя некоторого подграфа (узла дерева), и операция объединения объединит деревья (повесьте меньшее дерево под корнем более высокого). Операция объединения просто переходит к корню и сокращает пройденный путь (вешает искомый элемент (возможно, все пройденные элементы) ниже корня).

Answer 2

с битовым полем

• объединение будет O (n). Вы предполагаете, что можете сделать простой бит or для двух собственных целых чисел, но если n большое, вы, очевидно, не сможете использовать встроенные типы.
• обнаружение будет O (1). Вам не нужно повторять, вы знаете точное местоположение бита.

Кроме того, битовое поле не очень подходит для произвольных наборов. Например, если у вас есть набор, который может содержать любое 32-битное целое число, вам нужно битовое поле размером 4G / 8 = 0,5G.