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

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

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

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

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

Answer 2

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

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

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

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

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 - количество элементов.