Пересечение множеств

> Можно ли найти пересечение быстрее?

Поддерживать список с пересечением? При изменении множеств делать актуализацию.

Сортировка твоё O(n) убивает напрочь.

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

+1

Эту задачу нельзя рассматривать в отрыве от того, как эти множества будут создаваться и использоваться. Решений может быть множество :) Сама же по себе задача в сформулированном виде имеет лишь академический интерес.

Хранение чисел отсортированными является хорошей идеей, но здесь не будет общих решений, пока задача не конкретизирована и не определены более четко use cases.

Видимо, dilmah имел ввиду использование битовых масок для представления множеств. Так реализованы множества в Pascal/Ada/Modula etc. Это было бы действительно самым быстрым способом, но там есть жесткое ограничение на диапазон чисел (точнее на мощность их диапазона).

Если вариант с битовыми масками не подойдёт, лучше использовать дерево, храня в каждом узле, помимо значения, 2 бита. 0-й устанавливать, если число пришло из первого множества, 1-й устанавливать, если число пришло из второго множества. Тогда пересечение, в отсортированном виде, находится обходом в глубину.

А вариант со списками, это O(n^2) + O(m^2) в худшем случае.

Согласен с предыдущими ораторами -- телепаты нынче в отпуске :-)

Решений масса -- битовые маски, деревья (двоичные, B, префиксные), хэши; их комбинации...

Для произвольных множеств - думаю невозможно быстрее чем за m+n. Собственно, для этого тебе надо знать об элементах множеств что-то такое, что даст возможность смотреть не на все элементы. Ибо просто пройтись по ним - m+n

Сделать хеш размером max(m,n). Если возникает коллизия, значит что-то уже есть в этом хеше. Значит, возникло пересечение. Итого, вместо O(m+n) получается O(max(m,n))

> вместо O(m+n) получается O(max(m,n))

анекдоты в big O notation

A = set((1, 2, 3))
B = set((0, 2, 4, 5))
print A.intersection(B)

>> Сортировка твоё O(n) убивает напрочь.

Учи матчасть. Все задачи доступа к множеству в виде упорядоченного списка имеют сложность O(n). Твое предложение ничем не лучше чем хранить множество в виде неупорядоченного списка, на пересечении получишь O(n^2) минимум, плюс сложность сортировки.

>> Сделать хеш размером max(m,n). Если возникает коллизия, значит что-то уже есть в этом хеше. Значит, возникло пересечение. Итого, вместо O(m+n) получается O(max(m,n))

В упорядоченном списке сложность и так O(max(m,n)), что равно O(m+n) кстати. А вот хештаблица может дать тебе O(1) (опять же смотря как хранить хеши).

>> Если вариант с битовыми масками не подойдёт, лучше использовать дерево, храня в каждом узле, помимо значения, 2 бита. 0-й устанавливать, если число пришло из первого множества, 1-й устанавливать, если число пришло из второго множества. Тогда пересечение, в отсортированном виде, находится обходом в глубину.

И что? Сложность O(n), т.к. надо просмотреть все дерево. Та же самая сложность получается при пересечении двух бинарных деревьев (не обязательно даже сбалансированных).