Imaginez que nous avons un tableau infini, où nous stockons des entiers. Lorsque J'essaie de trouver une structure de données / algorithme capable de:
Chaque opération doit être dans J'ai rencontré Ce site , où l'algorithme suivant a été présenté: < / p>
Malheureusement, cette solution est Comment le rendre pur Étant donné que toutes les opérations doivent être effectuées, j'imagine que l'insertion et la suppression seraient toutes deux Qu'est-ce que le tableau infini est signifie?
Fondamentalement, vous pouvez stocker n'importe quel nombre d'éléments. C'est infini. Cependant, il y a deux restrictions. Première - une cellule ne peut stocker qu'un seul élément. Deuxièmement, lorsque la matrice stocke actuellement N éléments, seules N premières cellules peuvent être utilisées.
Qu'en est-il de la commande?
Peu importe. N est dans la matrice, seul n premières cellules sont utilisés, le reste est vide.
O (sqrt (n)) .
Approche 1
O (sqrt (n) * journal (n)) .
O (sqrt (n)) ?
idée 2
O (1) . Juste une supposition. Et probablement une fois l'insertion est terminée, la suppression sera évidente.
Clarification
5 Réponses :
Puisque vous stockez des entiers, rendez le tableau 4 milliards d'INT de large. Ensuite, lorsque vous ajoutez un élément incrémente l'entier égal à l'élément par 1. Vous pourrez ajouter, supprimer, la vérification de l'élément prendra O (1) heure. C'est fondamentalement une table de hachage sans hachage.
Quelle est la dépense de réhabation de la matrice quand elle dépasse 4 milliards?
Il n'aura jamais besoin d'être réhabé. Les entiers ne peuvent avoir qu'une valeur de 4 milliards de max.
Qu'en est-il d'environ 64 bits d'entiers?
Le tableau est censé être infini, mais la taille d'un entier est finie. Donc, vous pouvez réellement stocker comme 4 gigues de mémoire. Et en avoir un pour chaque valeur. Et le nombre de combien de cette valeur que vous avez.
Très incorrect. Unsigné 4-octets Les entiers ne peuvent avoir qu'une valeur de 4 294 967 295. Mais non signé 8-octet Les entiers ont une valeur maximale de 18 446 744,073 709 551,615. En supposant une machine 8 bits, bien sûr. Naturellement, vous pouvez concevoir des types de données entier personnalisés pour avoir des valeurs beaucoup plus grandes ou un matériel exotique.
Les entiers 64 bits sont pas réalisables. J'ai effectivement fait cela avec des couleurs 24 bits. 16 Megs n'était pas beaucoup de mémoire pour le système que j'étais implémensifi, où le temps était super critique.
@Tatariser: Ce n'est pas une question sur la faisabilité. C'est une question sur les algorithmes. Aussi: il n'est pas nécessaire que toute la mémoire soit attribuée à l'avance.
Yup, il s'agit d'algorithmes. Il n'y a pas de véritable informatique, juste pure théorie merveilleuse.
Eh bien, je vais de l'avant et faites dans une table infinie. Bien que la chose de Hilbert soit vraiment pertinente.
16 gigs de mémoire plutôt. pour stocker cette table. Ma table de recherche pour les 24 bits coûte 256 mégots de mémoire.
Créer une liste liée à un ensemble de tableaux k qui représentent des tables de hachage.
par l'idée du premier site, que les tables de hachage soient dimensionnées de contenir 1, 4, 9, 16, 25, 36, 49, ... éléments.
La structure de données contient donc Vous pouvez ensuite rechercher successivement chaque table de hachage pour des éléments. Le chèque de hachage, insérer et supprimer des opérations fonctionnent dans Si une table de hachage est pleine, ajoutez un supplémentaire à la liste liée. Si une table de hachage est vide, retirez-la de la liste (ajoutez-la si nécessaire ultérieurement). Liste Insertion / Suppression est Notez que cela s'améliore sur d'autres réponses suggérant une table de hachage droite, car la réhabation ne sera pas nécessaire car la structure de données augmente. n = k * (k + 1) * (2 * k + 1) / 6 = O (k ^ 3) (ceci est le résultat d'un puits Formule de sommation connue pour ajouter des carrés) éléments avec k tables de hachage.
O (1) heure (en supposant une chaîne séparée afin que les suppressions puissent être manipulées gracieusement) et, étant donné k O (1) Pour une liste doublement liée, cela n'affecte donc pas la complexité de temps.
"Lorsque n éléments sont dans le tableau, seules n premières cellules sont utilisées"
Si vous utilisez déjà des tables de hachage et que le scénario est théoriquement infini, pourquoi pas simplement utiliser une table de hachage et obtenir o (1) complexité globale plutôt que O (sqrt n) < / code>?
Avez-vous considéré comme un Heap BI-parental (AKA: BEAD)?
Le tas maintient une hauteur de Ces structures sont décrites dans le papier de Munro et Suwanda de 1980 structures de données implicites pour Recherche rapide et mise à jour . sqrt (n) , ce qui signifie que l'insertion, la recherche et la suppression de toutes l'exécution dans O (sqrt (n)) dans le pire cas.
C'est en fait un pire des cas.
C'est la réponse. Merci, Richard!
Je pense que l'approche 1 fonctionne, je pense simplement que certaines des mathématiques sont fausses.
Le nombre de sous-tableaux n'est pas Donc, vous obtenez Mon CS est un peu rouillé, vous devrez donc vérifier cela. S'il vous plaît laissez-moi savoir si je me suis trompé. O (sqrt (n)) C'est O (cuberoot (n))
O (log (n) * n ^ (1/3) = O ((log (n) / n ^ (1/6)) * N ^ (1/2) ) et puisque lim (journal (n) / n ^ (1/6)) = 0 nous obtenons o ((N) / n ^ (1/6 )) * N ^ (1/2))
Je pensais que le problème de cette approche est que, étant donné que les compartiments sont censés être tenus de sorte que les ensembles d'éléments d'entre eux se trouvent dans une commande croissante par rapport à l'autre, la mise à jour peut potentiellement affecter tous les compartiments, en ajoutant trop de la complexité. des opérations.
@ גגעבברקן Les éléments des sous-arôtes ne sont pas en augmentation de la commande, mais dans un tas, je pense que l'insertion et la suppression d'un tas prend o (journal (n)) , si le nombre de sous-bras est O (Cuberoot (N)) et vous insérez et supprimez de chacun d'entre eux que vous obtenez O (journal (n) * n ^ (1/3))
Je n'ai pas dit que les éléments des sous-ouvriers sont en augmentation de la commande. J'ai dit que dans l'algorithme, le PO lié à, le définit d'éléments, c'est-à-dire que les compartiments par rapport aux autres sont censés être dans l'ordre croissant. Ou ai-je mal lu cette description?
@ גגעברקן vous lisez correctement, mais même si vous allez bien que chaque banquier la complexité reste assez faible
Comment supprimez-vous l'élément de la première sous-carraille (taille 1) et évitez les opérations N nécessaires pour tout déplacer?
La réponse courte est que remplir toutes vos exigences est impossible pour le simple fait qu'un tableau est une représentation des éléments commandés par index; et si vous souhaitez conserver le premier (Cela dit, ignorant la suppression, c'était ma proposition antérieure: puisque votre matrice est infinie, cela ne vous dérangera-t-il pas si je plie un peu l'une des règles. Pensez à votre tableau aussi semblable aux adresses de mémoire dans un ordinateur , puis construire un arbre binaire équilibré, consignant un bloc d'éléments de tableau pour chaque nœud (je ne suis pas trop expérimenté avec des arbres, mais je pense que vous aurez besoin d'un bloc de quatre éléments, deux pour les enfants, un pour la valeur et une Pour la hauteur). Les éléments réservés aux enfants contiennent simplement les index de départ de la matrice pour les blocs d'enfants (nœuds). Vous utiliserez n référencé par les index des premiers n , comme vous le dites, toute suppression peut potentiellement nécessiter une nouvelle indexation (qui change d'éléments Array) Sur l'ordre de O (n) Opérations.
4n = O (n) au lieu de strictement n espace pour le premier n éléments (pliant votre règle un peu) et avoir des ordres de grandeur mieux complexité car les opérations d'une BST seraient O (log2 n) < / code>. (Au lieu d'attribuer des blocs d'éléments, la construction de nœuds pourrait également être effectuée en divisant chaque élément de tableau dans des sections de bits, dont vous auriez probablement assez dans un scénario théoriquement infini.)
Puisque vous n'avez pas spécifié de langue, ce n'est pas clair ce que vous entendez par «tableau». Les matrices C et Java ont une taille finie spécifiée à l'initialisation. Je suggère de raffiner la question pour expliquer exactement ce que vous entendez par «tableau infini». Un arbre binaire serait-il qualifié, par exemple?
En outre, il n'est pas clair pour moi si le contenu devrait être trié, ni ce que vous entendez par 'insert' (dans une matrice C / Java, vous ne pouvez pas "insérer", vous ne pouvez modifier qu'une valeur par index)
Je viens de modifier la question. Bientôt - la taille est infinie . Vous utilisez simplement les premières n cellules.
Eh bien alors, ça ne peut pas être fait. La première étape de la création d'une matrice consiste à attribuer la mémoire pour chaque cellule. Sauf si vous pouvez imaginer un ordinateur où
malloc (infini) fonctionne ...@slim: Bien sûr, cela peut être fait. Il vous suffit de réaffecter lorsque le tableau devient plus grand.
@Richard, alors ce n'est pas un tableau. C'est quelque chose de plus complexe. Alors, quelles sont les contraintes de l'OP?
@slim: "J'essaie de trouver une structure de données / algorithme". Par votre logique, rien qui est réaffecté peut être un tableau.
@Richard J'essaie de l'entraîner à dire que ce qu'il veut, c'est un séminage de manière arbitraire (qui est différent de «infini») (qui est différent de «tableau»). Je pense que c'est probablement ce qu'il veut. Ensuite, il existe peut-être d'autres contraintes sur ses exigences qui signifient que quelque chose basé sur un arbre ou un hachage n'est pas acceptable, par exemple. "Le magasin de support doit être un bloc de mémoire contigu" ou "Je ne veux pas utiliser les pointeurs", etc.