В Python вы можете получить пересечение двух наборов:
>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s2 = {0, 3, 5, 6, 10}
>>> s1 & s2
set([3, 5, 6])
>>> s1.intersection(s2)
set([3, 5, 6])
Кто-нибудь знает сложность этого алгоритма пересечения (&)?
РЕДАКТИРОВАТЬ: Кроме того, кто-нибудь знает, какова структура данных за комплектом Python?
Ответ выглядит как запрос поисковой системы. Вы также можете использовать прямую ссылку на странице Time Complexity на python.org. Краткое резюме:
Average: O(min(len(s), len(t))
Worst case: O(len(s) * len(t))
EDIT: Как указывает Раймонд, сценарий "наихудшего случая" вряд ли произойдет. Я включил его изначально, чтобы быть основательным, и я оставляю его, чтобы предоставить контекст для обсуждения ниже, но я думаю, что Раймонд прав.
Алгоритм пересечения всегда работает в O (min (len (s1), len (s2))).
В чистом Python это выглядит так:
def intersection(self, other):
if len(self) <= len(other):
little, big = self, other
else:
little, big = other, self
result = set()
for elem in little:
if elem in big:
result.add(elem)
return result
[Ответ на вопрос в дополнительном редактировании] Структура данных за наборами представляет собой хеш-таблицу .
Установить пересечение двух наборов размеров m,n можно с помощью O(max{m,n} * log(min{m,n})) следующим образом:
Предположим, что m << n
1. Represent the two sets as list/array(something sortable)
2. Sort the **smaller** list/array (cost: m*logm)
3. Do until all elements in the bigger list has been checked:
3.1 Sort the next **m** items on the bigger list(cost: m*logm)
3.2 With a single pass compare the smaller list and the m items you just sorted and take the ones that appear in both of them(cost: m)
4. Return the new set
Цикл на шаге 3 будет выполняться для n/m итераций, и каждая итерация займет O(m*logm), поэтому у вас будет временная сложность O(nlogm) для m < п.
Я думаю, что лучшая нижняя граница, которая существует