Temps d'exécution de l'ensemble de l'union opération
Étant donnés deux ensembles A et B, quelle est la commune de l'algorithme utilisé pour trouver leur union, et qu'est-ce que c'est de la course du temps?
Mon intuition:
a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
union.add(el)
for el in b:
union.add(el)
Ajouter des contrôles de collision, qui est O(1), puis ajoute l'élément, qui est (??). Ceci est fait n fois (où n est |a| + |b|). C'est donc O(n * x) où x est avg temps d'exécution de l'opération d'ajout.
Est-ce correct?
OriginalL'auteur Claudiu | 2008-11-24
Vous devez vous connecter pour publier un commentaire.
Ce est très dépendant de l'implémentation. D'autres ont mentionné jeux basés sur des données comparables (moins-que pour le tri) ou hashables (avoir une bonne fonction de hachage hachage). Une autre mise en cause "de l'union-find", qui ne prend en charge un sous-ensemble spécialisé de jeu habituel des opérations, mais est très rapide (de l'union est amorti de la constante de temps, je pense?), vous pouvez lire à ce sujet ici
http://en.wikipedia.org/wiki/Union_find
et voir un exemple d'application ici
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!220.entrée
OriginalL'auteur Brian
La complexité de trouver(collision), dépendra de la mise en œuvre de l'union.
Si vous utilisez une table de hachage en fonction de discbased alors votre collision opération va en effet être constante en supposant une bonne fonction de hachage.
Autrement, sera probablement en O(Log(N)) pour une liste triée/arbre de discbased.
OriginalL'auteur Akusete
Première réponse: Si vous travaillez avec jeux de de numéros de, vous pourriez mettre en œuvre un ensemble comme un triés vecteur d'éléments distincts. Ensuite, vous pouvez mettre en œuvre l'union(S1, S2) simplement comme une opération de fusion (vérification des doublons), qui prend en O(n), où n = somme des cardinalités.
Maintenant, ma première réponse est un peu naïf. Et Akusete est vrai: Vous pouvez, et vous devez, à les mettre en place comme une table de hachage (un jeu devrait être un conteneur générique, et pas tous les objets peuvent être triées!). Alors, à la fois de la recherche et de l'insertion sont en O(1) et, comme vous l'avez deviné, l'union prend en O(n) fois.
(En regardant votre code Python) Python ensembles sont mis en œuvre avec les tables de hachage. Lisez ce fil intéressant. Voir aussi cette mise en œuvre qui utilise des vecteurs triés à la place.
OriginalL'auteur Federico A. Ramponi
Si vous pouvez utiliser bitsets (chaque bit dans un tableau de int est égal à un élément de votre jeu), vous pouvez tout simplement marcher sur le tableau int et le OU les éléments. Cela a pour complexité O(N) (où N est la longueur du tableau) ou O((m+31)/32), où M est le nombre d'éléments.
OriginalL'auteur Aaron Digulla