Kreuzung Komplexität

In Python können Sie den Schnittpunkt der zwei Sätze machen:

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

Jemand kennt die Komplexität dieser Kreuzung (&) Algorithmus?

EDIT: außerdem, weiß jemand, was ist die Datenstruktur, die hinter einem Python gesetzt?

InformationsquelleAutor juliomalegria | 2011-11-12

13

Die Antwort scheint zu sein eine Suchmaschinen-Abfrage entfernt. Sie können auch diese direkter link auf den Zeit-Komplexität-Seite an python.org. Kurze Zusammenfassung:
```
Average:     O(min(len(s), len(t))
Worst case:  O(len(s) * len(t))
```
EDIT: Wie Raymond Punkte unten, die "worst case" - Szenario ist nicht wahrscheinlich. Ich umfasste es ursprünglich um gründlich zu sein, und ich bin, dass es den Kontext für die Diskussion unten, aber ich denke, Raymond Recht.
- das ist eine böse schlimmsten Fall, ist es nicht?
- Ich war überrascht, wie gut! Vielleicht ist es ein Problem, dass wir verschiedene Daten-Typen gemischt, in der zwei sets wird geschnitten?
- Es sieht nicht wie es verwendet eine Art erste (die erfordert die Objekte haben eine Bestellung), sondern nur ein "hash " probe": vielleicht für einen besseren C und Durchschnittliche (und keine Bestellung Anforderung). Der maximal erforderlichen Komplexität, AFAIK, ist über O(n log n) + O(n) mit eine Art. Aber Big-O ist eine Obere-Schranken, und es gibt praktische Erwägungen so...
- Ich denke, das große Problem hier ist, dass die Menge ist eine ungeordnete Sammlung. In C++ können Sie eine Kreuzung (mit zwei sortierte Listen) in 2*(L1+L2)-1. Das ist eine verdammt gute Komplexität! cplusplus.com/reference/algorithm/set_intersection
- Schön! Ich bin wirklich dankbar für die Erkenntnis; hash-Kollisionen machen viel Sinn. +1 ist alles rund!
- Diese Antwort ist etwas irreführend in Bezug auf den "worst case" - Zeit. Lassen Sie sich nicht es Sie führen Weg von einer völlig in Ordnung-Algorithmus.
- Ich Stimme mit Ihnen überein; behoben. Wieder, ich Schätze die Diskussion!
- Bitte nicht sagen "google es" in diesen Antworten. Diese Antworten oft werden die Ergebnisse googeln etwas. Diese Antwort war die erste Suche Ergebnis für mich.
- Wahrscheinlichkeit, dass etwas passiert, ist irrelevant bei der Diskussion der "worst case". Im schlimmsten Fall ist der Schlimmste Fall, solange es einen Wert ungleich null chance dafür. Allerdings, wenn Python ist eine hash-Tabelle, dass $n^2$ Komplexität nicht passieren sollte, immer. Also, es ist nicht einmal der Schlimmste Fall.
- Es ist schon komisch, wie das erste suchergebnis ist dieser thread aus diesen hyperlink
InformationsquelleAutor Kurt McKee
20

Den Schnittpunkt-Algorithmus läuft immer auf O(min(len(s1), len(s2))).

In reinem Python, sieht es wie folgt aus:
```
    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
```
[Antwort auf die Frage in das weitere Bearbeiten] Die Struktur der Daten hinter legt ist ein hash-Tabelle.
- nicht immer check: wiki.python.org/moin/TimeComplexity#set
- Laut der wiki, die ich weiter oben verlinkt, im schlimmsten Fall für elem in big im code ist O(n) (obwohl der Durchschnitt ist natürlich O(1)). Das ist die basis für die Kreuzung schlechtesten Fall von O(len(s)*len(t)). Irgendeine Idee warum?
- Der "worst case" davon ausgegangen, daß die Daten ungeeignet für den Einsatz in der hash-Tabelle verwendet, die durch dict und set. Die Daten werden müsste, etwas, so dass jedes Bezugs-hatte genau den gleichen hash-Wert -- dies würde die Kraft der hash-Tabelle zu tun, so etwas wie eine lineare Suche zu tun, den __enthält__ zu überprüfen. IOW, ich würde nicht sorgen über diese überhaupt. Satz Kreuzung ist blind schnell-er selbst verwendet den intern gespeicherten hash-Werte, so dass Sie nicht brauchen, um alle Anrufe zu tätigen, um - hash().
InformationsquelleAutor Raymond Hettinger

Set Schnittmenge zweier sets von Größen m,n erreicht werden kann, mit O(max{m,n} * log(min{m,n})) in der folgenden Weise:
Übernehmen 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

Die Schleife in Schritt 3 wird für die n/m Iterationen und in jeder iteration wird nehmen O(m*logm), so haben Sie Zeit, die Komplexität der O(nlogm) für m << n.