Y a-t-il une structure de données disponible qui fournirait o (1) - c'est-à-dire une complexité constante d'insertion et o (log (n)) complexité de recherche Un vecteur trié peut faire un o (log (n)) la recherche mais l'insertion prendrait o (n) (pris le fait que je n'insère pas toujours le éléments soit à l'avant ou à l'arrière). Alors qu'une liste ferait o (1) l'insertion mais n'aboutirait pas à fournir o (log (n)) recherche.
Je me demande si une telle structure de données peut même être mise en œuvre.
3 Réponses :
Je me demande si une telle structure de données peut même être mise en œuvre.
Je crains que la réponse soit non.
recherche ok, insertion non Lorsque nous examinons les structures de données telles que l'arbre de recherche binaire, l'arbre B, l'arbre rouge-noir et l'arbre AVL, ils ont une complexité de recherche moyenne de
O (log n) , mais au même Heure La complexité d'insertion moyenne est la même que celle du code> O (journal n) . La raison est évidente, la recherche suivra (ou naviguera) le même modèle dans lequel l'insertion se produit .
Insertion OK, recherche non Les structures de données telles que la liste liée, la liste doublement liée aura une complexité d'insertion moyenne de
O (1) , mais la recherche de la recherche de manière simple et doublement ll est douloureuseo (n) , juste parce qu'ils n'ont pas de support d'accès à l'élément basé sur l'indexation .Réponse à votre question réside dans le Lisklist implémentation, qui est une liste liée, toujours Il a besoin
O (journal n) en moyenne pour l'insertion (lorsque les listes sont censées insertion dansO (1) ).sur les notes de clôture, HASHMAP est très proche de la recherche rapide de la recherche rapide et de l'insertion rapide avec le coût de l'énorme espace, mais si horriblement mis en œuvre, cela peut entraîner une complexité du
o (N) pour l'insertion et la recherche.
(NE Skip-List: La question demande explicitement O (journal (n)) Complexité de recherche Même dans le pire des cas .)
non (au moins dans un modèle où les éléments stockés dans la structure de données ne peuvent être comparés que pour commander uniquement; hachage n'aider pas les limites du temps pire cas, car il peut y avoir une grande collision) .
Supposons que chaque insertion nécessite à la plupart des comparaisons C. (Heck, faisons l'hypothèse plus faible que les n insertions nécessitent au plus de comparaisons C * N.) Considérons un adversaire qui insère n éléments, puis regarde un. Je décrirai une stratégie contradictoire qui, pendant la phase d'insertion, oblige la structure de données à avoir oméga (n) éléments qui, étant donné que les comparaisons fabriquées jusqu'à présent, pourraient être commandées toutes les parties. Ensuite, la structure de données peut être forcée de rechercher ces éléments, ce qui représente une liste non formée. Le résultat est que la recherche a le temps de fonctionnement des cas d'oméga (n).
L'objectif de l'adversaire est de donner la même information que possible. Les éléments sont triés en trois groupes: gagnants, perdants et inconnus. Initialement, tous les éléments sont dans le groupe inconnu. Lorsque l'algorithme compare deux éléments inconnus, on choisi arbitrairement devient un gagnant et l'autre devient un perdant. Le gagnant est considéré plus grand que le perdant. De même, les comparaisons inconnues-perdant, inconnus et gagnantes-gagnants sont résolues en désignant l'un des éléments un gagnant et l'autre un perdant, sans modifier les désignations existantes. Les cas restants sont des comparaisons perdant-perdant et gagnant-gagnant, qui sont gérées de manière récursive (le groupe des gagnants du gagnant dispose donc d'un sous-groupe gagnant-inconnu, d'un sous-groupe gagnant-gagnants et d'un sous-groupe gagnant-perdant). Par un argument en moyenne, car au moins N / 2 éléments sont comparés à la plupart des temps 2 * C, il existe un sous-groupe de taille d'au moins N / 2/3 ^ (2 * C) = oméga (n). Il peut être vérifié qu'aucun de ces éléments n'est commandé par des comparaisons antérieures.
Oui, mais vous devriez plier les règles un peu de deux manières:
1) Vous pouvez utiliser une structure qui a une recherche O (1) insertion et O (1) (1) (telle que le Critbit arbre, également appelé Bitwise Trie ) et ajouter artificiel coût pour transformer la recherche dans O (log n).
Une critique d'une critique est comme un binaire arbre RADIX pour les bits. Il stocke des clés en marchant le long des bits d'une clé (disons 32bits) et utilisez le bit pour décider de naviguer à gauche ('0') ou de droite ('1') à chaque noeud. La complexité maximale de la recherche et de l'insertion est à la fois O (32), qui devient O (1).
2) Je ne suis pas sûr que cela soit O (1) dans un sens théorique strict, car o (1) ne fonctionne que si nous limitons la plage de valeurs (à, dire, 32 bits ou 64 bits), mais pour Des objectifs pratiques, cela semble une limitation raisonnable.
Notez que les performances perçues seront O (log n) jusqu'à ce qu'une partie importante des permutations de clé possibles soient insérées. Par exemple, pour les touches 16 bits, vous devez probablement insérer une partie importante de 2 ^ 16 = 65563 clés.
Toute raison pour laquelle les tables de hachage ne seraient pas appropriées? Considérez-vous que la possibilité de collisions est un facteur de ne pas compter que O (1) pour ces actions?
Oui, il y aura des duplicats. Donc, les tables de hasch ne fonctionneront pas correctement? Je n'ai pas pensé à la taille, mais considérez-le assez grand.
"Cela dépend" - sur la signification de "recherche", pour une: trouver des correspondances exactes dans ce qui a été inséré auparavant, ou "plus petit non plus petit". Pour une correspondance exacte, vous pouvez vous échapper avec hachage et agitant à la main (aux collisions). La phrase verbe dans
cette structure de données est même mise en œuvre est cassée.Hash travaille avec des doublons, car vous pouvez maintenir un nombre d'événements pour chaque élément de votre table de hachage.
Vous pouvez avoir les deux
O (1) insertion etO (1) Rechercher si vous êtes prêt à consommer une quantité énorme de mémoire. Créez une matrice géante la taille de votre espace clé. Pour insérer, copiez l'élément dans la matrice à la position indexée par le kay. Pour rechercher, lisez de la matrice à la position indexée par la clé. Chacun d'entre eux est une opérationO (1) . Cependant, les exigences spatiales sont énormes si votre espace clé est grand.Je doute que vous puissiez obtenir cela dans le pire des cas, mais les tables de hasch peuvent vous donner amortis
0 (1) pour l'insertion et la recherche et fonctionneront bien même avec de grands ensembles de données.(L'insertion sera au moins aussi coûteuse que la recherche car l'insertion doit d'abord rechercher la clé afin de gérer les doublures. Donc, si vous voulez
O (1) insertion, vous devez trouver quelque chose qui vous donne < Code> O (1) recherche. Cela limite considérablement vos options.)Peut-être une structure de données avec
O (journal (n)) insertion et recherche, qui donne toutes les insertions jusqu'à la recherche? Ceci est similaire à ce que la structure de données disjointe de Tarjan fait si je ne me trompe pas.@Rhymoid qui ne voudrait pas aider, car l'insertion d'éléments
n suivi d'une recherche va incitero (n) coût à la première recherche car il traite toutes les insertions différées. Vous pourrez peut-être amortir ce coût, mais OP veut garantio (journal n) Coût de la recherche, pas de coût amorti.@Raymondchen:
L'insertion sera [aussi coûteux parce que cela] doit d'abord rechercher la clé afin de gérer les doublons Vous semblez envisager définir (ou incluez-vous Multiset ?) - Aucun dont la question ne mentionne (explicitement).@Raymondchen
L'insertion sera au moins aussi coûteuse que la recherche car l'insertion doit d'abord rechercher la clé afin de gérer les doublons . Ce n'est pas correct, considérons par exemple des tas de binomiels, qui ont O (1) pour l'insertion mais O (log n) pour trouver la valeur minimale et o (n) pour trouver une valeur arbitraire.