W Pythonie możesz zdobyć skrzyżowanie dwóch zestawów:

>>> 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])

Ktoś zna złożoność tego skrzyżowania ({x0}}) algorytm?

Edytuj: Ponadto, czy ktoś wie, jaka jest struktura danych za zestawem Python?

16
juliomalegria 12 listopad 2011, 08:07

3 odpowiedzi

Najlepsza odpowiedź

Odpowiedź wydaje się być Zapytanie w wyszukiwarki. Możesz także użyć tego Direct Link do strony złożoności czasu w Python.org. Szybkie podsumowanie:

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

Edytuj: Ponieważ Raymond wskazuje poniżej, "najgorszy przypadek" scenariusz prawdopodobnie nie wystąpi. Włączyłem to pierwotnie, aby być dokładnym i zostawiam go, aby zapewnić kontekst do dyskusji poniżej, ale myślę o prawej stronie Raymond.

15
Kurt McKee 12 listopad 2011, 05:21

Algorytm przecięcia zawsze działa w O (min (Len (S1), Len (S2))).

W czystym pytonie wygląda tak:

    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

[Odpowiedź na pytanie w dodatkowej edycji] Struktura danych za zestawami jest stół Hash.

25
Raymond Hettinger 12 listopad 2011, 04:33

Ustaw przecięcie dwóch zestawów rozmiarów {X0}} można osiągnąć za pomocą O(max{m,n} * log(min{m,n})) w następujący sposób: Załóżmy 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

Pętla w kroku 3 uruchomi się do iteracji n/m i każda iteracja weźmie O(m*logm), więc będziesz miał złożoność czasu O(nlogm) dla M & LT; n.

Myślę, że to najlepsza niższa granica, która istnieje

1
Elad Yehezkel 25 styczeń 2017, 18:01