Время выполнения операции объединения

Question

Учитывая два набора A и B, какой общий алгоритм используется для поиска их объединения и каково его время выполнения?

Моя интуиция:

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

Добавьте проверки на столкновение, которое равно O (1), а затем добавьте элемент, который равен (??). Это делается n раз (где n равно | a | + | b |). Так что это O (n * x), где x - среднее время выполнения операции добавления.

Это правильно?

Answer 1

Это очень сильно зависит от реализации. Другие упоминали наборы, основанные на сопоставимых (имеют меньше чем для сортировки) или хеш-хеллах (имеют хорошую хэш-функцию для хеширования). Другая возможная реализация включала «union-find», которая поддерживает только специализированное подмножество обычных операций над множествами, но очень быстрая (я думаю, объединение амортизируется постоянным временем), вы можете прочитать об этом здесь

http://en.wikipedia.org/wiki/Union_find

и посмотрите пример приложения здесь

http://lorgonblog.spaces.live.com/blog /cns!701679AD17B6D310!220.entry

Answer 2

Сложность добавления / поиска (столкновения) будет зависеть от реализации объединения.

Если вы используете некоторую структуру данных, основанную на хеш-таблицах, то ваша операция коллизий действительно будет постоянной при условии хорошей хеш-функции.

В противном случае add, вероятно, будет O (Log (N)) для отсортированной структуры списка / дерева данных.

Answer 3

Первый ответ: если вы имеете дело с наборами чисел , вы можете реализовать набор как вектор отсортированный отдельных элементов. Тогда вы можете реализовать объединение (S1, S2) просто как операцию слияния (проверка на наличие дубликатов), что занимает время O (n), где n = сумма мощностей.

Теперь мой первый ответ немного наивен. А Акусете прав: вы можете и должны реализовать набор в виде хеш-таблицы (набор должен быть универсальным контейнером, и не все объекты могут быть отсортированы!). Тогда и поиск, и вставка - это O (1), и, как вы уже догадались, объединение занимает O (n) времени.

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

Answer 4

Если вы можете использовать наборы битов (каждый бит в массиве int равен элементу вашего набора), вы можете просто пройтись по массиву int и ИЛИ элементам. Это имеет сложность O (N) (где N - длина массива) или O ((m + 31) / 32), где M - количество элементов.