Сложность пересечения

Question

В 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?

Answer 1

Алгоритм пересечения всегда работает при 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

[Ответ на вопрос в дополнительном редакторе] Структура данных, лежащая в основе наборов, - это хеш-таблица .

Answer 2

Ответом является запрос поисковой системы . Вы также можете использовать эту прямую ссылку на страницу сложности времени на python.org . Краткое резюме:

Average:     O(min(len(s), len(t))
Worst case:  O(len(s) * len(t))

РЕДАКТИРОВАТЬ: Как Раймонд указывает ниже, сценарий «наихудшего случая» вряд ли произойдет. Первоначально я включил это, чтобы быть тщательным, и я оставляю это, чтобы обеспечить контекст для обсуждения ниже, но я думаю, что Раймонд прав.

Answer 3

Установить пересечение двух наборов размеров 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 << n. </p>

Я думаю, что это лучшая нижняя граница, которая существует