Intersection de la complexité

En Python, vous pouvez obtenir l'intersection de deux ensembles de fait:

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

Quelqu'un sait la complexité de cette intersection (&) algorithme?

EDIT: En outre, personne ne sait quelle est la structure de données derrière un Python ensemble?

InformationsquelleAutor juliomalegria | 2011-11-12
  1. 13

    La réponse semble être une requête moteur de recherche de suite. Vous pouvez également utiliser cette lien direct vers le Temps de la Complexité de la page à python.org. Résumé:

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

    EDIT: Comme Raymond points ci-après, le "pire des cas" scénario n'est pas susceptible de se produire. Je l'ai inclus à l'origine pour être complet, et je pars à fournir le contexte de la discussion ci-dessous, mais je pense que Raymond droit.

    • c'est un méchant pire des cas, n'est-ce pas?
    • J'ai été surpris par celui-ci! Peut-être que c'est une question d'avoir différents types de données mixtes dans les deux ensembles étant coupée?
    • Il ne regarde pas comme il utilise un tri première (exige que les objets ont une commande), mais plutôt à un "hash de la sonde": peut-être pour une meilleure C et Moyenne (et aucun ordre exigence). L'exigence maximale de la complexité, autant que je sache, est d'environ O(n log n) + O(n), avec une sorte. Cependant, le Big-O est un haut-limites et il y a des considérations d'ordre pratique donc...
    • Je pense que le problème majeur ici est que l'ensemble est une collection non ordonnée. En C++, vous pouvez faire une intersection (avec deux listes triées) en 2*(L1+L2)-1. C'est un putain de bon complexité! cplusplus.com/reference/algorithm/set_intersection
    • Nice! J'apprécie vraiment l'intuition; les collisions de hachage faire des bouquets de sens. +1 a autour!
    • Cette réponse est un peu trompeuse quant à la "pire des cas" du temps. Ne le laissez pas vous éloigner d'une parfaitement bien de l'algorithme.
    • Je suis d'accord avec vous; fixe. Encore une fois, j'apprécie la discussion!
    • Merci de ne pas dire "google" dans ces réponses. Ces réponses deviennent souvent les résultats de recherche sur google quelque chose. Cette réponse a été le premier résultat de recherche pour moi.
    • La probabilité de se passer quelque chose n'a aucune importance lors de la discussion de la "pire des cas". Le pire des cas est le pire des cas, tant il est différent de zéro chance que cela se produise. Toutefois, si Python est à l'aide d'une table de hachage, que $n^2$ complexité ne devrait jamais se produire. Par conséquent, il n'est même pas le pire des cas à tous.
    • C'est drôle comment le premier résultat de recherche est ce fil à partir de ce lien hypertexte

    InformationsquelleAutor Kurt McKee
  2. 20

    La algorithme d'intersection toujours s'exécute en O(min(len(s1), len(s2))).

    En pur Python, il ressemble à ceci:

        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

    [Réponse à la question dans le supplémentaires modifier] La structure de données derrière des ensembles est une table de hachage.

    • pas de toujours, vérifier: wiki.python.org/moin/TimeComplexity#set
    • Selon le wiki, j'ai lié ci-dessus, le pire des cas pour elem in big dans votre code est O(n) (bien qu'en moyenne, bien sûr, est de O(1)). C'est la base de l'intersection pire des cas en O(len(s)*len(t)). Aucune idée pourquoi?
    • Le "pire des cas" suppose de données qui est inapproprié pour une utilisation dans la table de hachage utilisé par dict et set. Les données devront être quelque chose de tel que chaque donnée a exactement la même valeur de hachage -- ce serait forcer la table de hachage de faire quelque chose qui s'apparente à un linéaire de recherche, de faire l' __contient__ chèque. OIE, je ne serais pas s'inquiéter à ce sujet. Ensemble intersection est aveugle et rapide -- il réutilise le même stockée en interne les valeurs de hachage de sorte qu'il ne sera pas besoin de faire des appels à hash().
    InformationsquelleAutor Raymond Hettinger
  3. 1

    Ensemble intersection de deux ensembles de tailles m,n peut être réalisé avec O(max{m,n} * log(min{m,n})) de la façon suivante:
    Supposons 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

    La boucle à l'étape 3 sera exécuté pour n/m itérations et à chaque itération prendra O(m*logm), de sorte que vous aurez le temps de la complexité de O(nlogm) pour m << n.

    Je pense que c'est la meilleure borne inférieure qui existe

    • Avez-vous entendu parler des tables de hachage lol
    InformationsquelleAutor Elad Yehezkel