Questions marquées «ds.data-structures»

Je viens de réaliser que je supposais que la réponse à ma question était "oui" mais je n'ai pas de bonne raison. J'imagine qu'il y a peut-être un garbage collector qui n'introduit que le ralentissement pire des cas. Y a-t-il une référence définitive que je peux citer? Dans mon cas, je travaille sur...

Lors de la compilation des résultats, il est souvent souhaitable d'avoir des diagrammes d'aspect professionnel, plutôt que des diagrammes rassemblés dans MS Paint. Quelle est la norme pour dessiner des structures de

Selon l'article de KW Regan "Connect the Stars" , il mentionne à la fin qu'il est toujours difficile de trouver une représentation des nombres entiers de sorte que les opérations d'addition, de multiplication et de comparaison sont calculables en temps linéaire: Existe-t-il une représentation...

Supposons qu'un graphe à n sommets soit présenté comme un flux de m arêtes, mais plusieurs passes sont autorisées sur le flux.gGGnnnmmm Monika Rauch Henzinger, Prabhakar Raghavan et Sridar Rajagopalan ont observé que l' espace est nécessaire pour déterminer s'il existe un chemin entre deux sommets...

Avertissement: je ne suis pas un théoricien CS. Issu de l'algèbre abstraite, j'ai l'habitude de traiter des choses qui sont égales à un isomorphisme - mais j'ai du mal à traduire ce concept en structures de données. J'ai d'abord pensé que des morphismes bijectifs théoriques définis suffisaient,...

Compte tenu d' une famille ensemble FF\mathcal{F} de sous - ensembles d'un univers UUU . Soit S1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal F et nous voulons répondre est S1⊆S2S1⊆S2S_1 \subseteq S_2 . Je recherche une structure de données qui me permettra d'y répondre rapidement. Mon application est de la...

Je cherche des moyens de maintenir un arbre couvrant relativement équilibré d'un graphique, alors que j'ajoute de nouveaux nœuds / arêtes au graphique. J'ai un graphique non orienté qui commence comme un seul nœud, la "racine". À chaque étape, j'ajoute au graphique soit un nouveau nœud et un bord...

Considérez équipé du produit scalaire standard et vecteurs: . Nous voulons construire une structure de données qui autorise les requêtes au format suivant: étant donné output . Est-il possible d'aller au-delà du temps de requête O (nm) trivial ? Par exemple, si n = 2 , alors il est immédiat...

Soit un graphe non orienté non pondéré avec sommets et arêtes. Est-il possible de prétraiter et de produire une structure de données de taille afin qu'il puisse répondre aux requêtes de la forme "distance entre et " dans le temps O (n)?n m G m ⋅ p o l y l o g ( n ) u vgGGnnnmmmgGGm ⋅ p o l y l o g...

Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...

Je cherche un algorithme pour fusionner deux arbres de recherche binaires de taille et de plage arbitraires. La manière évidente de procéder pour l'implémenter serait de trouver des sous-arbres entiers dont la plage peut s'insérer dans un nœud externe arbitraire dans l'autre arbre. Cependant, le...

L'article de Fischer ce mois-ci m'a rappelé à quel point je connaissais mal l'art des structures de données succinctes et les algorithmes pour les utiliser. Pour ceux qui ne connaissent pas les structures de données succinctes: Étant donné une structure combinatoire, avec une (n) configurations...

Cet article prétend que l'analyse traditionnelle du taux d'erreur dans les filtres Bloom est incorrecte, puis fournit une analyse longue et non triviale du taux d'erreur réel. L'article lié a été publié en 2010, mais j'ai vu l'analyse traditionnelle des filtres Bloom continuer à être enseignée dans...

Étant donné deux arbres AVL T1T1T_1 et T2T2T_2 et une valeur trtrt_r telle que ∀x∈T1,∀y∈T2,x<tr<y∀x∈T1,∀y∈T2,x<tr<y\forall x \in T_1, \forall y \in T_2, x < t_r < y , il est facile de construire un nouvel arbre AVL contenant trtrt_r et les valeurs en T1T1T_1 et T2T2T_2 dans le temps...

Après avoir travaillé avec 2-3 arbres à doigts pendant un bon moment, j'ai été impressionné par leur vitesse dans la plupart des opérations. Cependant, le seul problème que j'ai rencontré est la surcharge importante associée à la création initiale d'un grand arbre à doigts. Parce que la...

J'enseigne un cours sur les structures de données et couvrirai les arbres splay au début de la semaine prochaine. J'ai lu à plusieurs reprises l'article sur les arbres splay et je connais l'analyse et l'intuition derrière la structure des données. Cependant, je n'arrive pas à trouver une solide...

Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...

J'ai besoin de stocker des ensembles d'éléments de type a. Le type a est partiellement ordonné, donc comparer et un 2 peut retourner plus petit, plus grand, égal ou incomparable.une1une1a_1une2une2a_2 Un problème avec les tables de hachage est que deux éléments égaux peuvent être représentés...

Contexte La mémoire externe, ou modèle DAM, définit le coût d'un algorithme par le nombre d'E / S qu'il exécute (essentiellement, le nombre d'échecs de cache). Ces temps d'exécution sont généralement donnés en termes de , la taille de la mémoire et , le nombre de mots qui peuvent être transférés en...

Il existe un certain nombre d'algorithmes et de structures de données qui exploitent l'idée que obtient sa valeur minimale à k = \ sqrt n . Les exemples courants incluent k = √max { k , n / k }max{k,n/k}\max \left\{k, n/k\right\}k = n--√k=nk=\sqrt n algorithme pas à pas géant pour calculer le...