Complexité binaire d'une requête de plage de temps O (1) dans un tableau -ary

Considérez le problème suivant:

Soit une constante. On nous donne un tableau -ary de et . Soit . $k$ $k$ $A_{d_1\times\ldots\times d_k}$ $0$ $1$ $N = \prod_{i=1}^k d_i$

Nous voulons créer une structure de données en prétraitant pour effectuer le type d'opérations de requête suivant: $A$

Étant donné les coordonnées d'une case -ary , y a-t-il un dans la case? $k$ $D$ $1$
Étant donné les coordonnées d'une case -ary , retournez la position d'un dans la case (s'il y en a une). $k$ $D$ $1$

Les opérations doivent être effectuées en temps constant . La complexité temporelle est mesurée sur une machine RAM. Le temps et l'espace de prétraitement pour la structure des données ne sont pas importants pour nous. $O(1)$

La question est de combien d'espace (en complexité de bits) avons-nous besoin pour stocker une infrastructure de données permettant les opérations ci-dessus?

La borne inférieure triviale est bits car le tableau peut être reconstruit pour ces requêtes (la structure de données doit donc contenir au moins la même quantité d'informations). $N$

La limite supérieure triviale consiste à stocker la réponse à toutes les requêtes. Cela nécessiterait $\prod_{i=1}^k {d_i \choose 2} = \Theta(N^2)$ bits. Cependant, nous pensons que cela peut être fait beaucoup plus efficacement.

Par exemple, considérons le cas spécial où $k=1$ . Dans ce cas, nous pouvons utiliser une structure de données RMQ succincte pour résoudre le premier problème, et la structure de données prend $2N+o(N)$ bits à stocker.

Qu'est-ce qu'une structure de données efficace pour cette tâche?
Jusqu'à quel point la complexité de l'espace (le nombre de bits) peut-elle aller pour supporter ces opérations (ou tout simplement la première opération)?

Mise à jour (1/15): Dans le cas spécial , l'utilisation de bits est suffisante (en fait mieux, , où est le nombre de dans ) en réduisant le problème à un problème prédécesseur et en utilisant la réduction du problème prédécesseur au dictionnaire entièrement indexable (FID). Voir « Plus de hâte, moins de déchets: réduire la redondance dans les dictionnaires entièrement indexables » de Grossi, Orlandi, Raman et Rao (2009). $k=1$ $N +o(N)$ $\log {N\choose t}+O(t)$ $t$ $1$ $A$

Mise à jour (6/27): Réduisez encore le problème à RMQ. Nous utilisons un RMQ dimensionnel par Yuan et Atallah pour obtenir une limite supérieure sur la quantité d'espace requise lorsque est fixe. $k$ $O(n\log n)$ $k$

reference-request data-structures space-complexity Chao Xu
la source

La question n'est pas claire: s'agit-il d'une question de structure de données? Si oui, quelles sont les autres opérations sur ce tableau kD? S'il n'y a pas d'autre opération, il n'y a pas de 1 dessus. Si la question est que l'on nous donne un tableau kD et quoi faire du prétraitement dessus puis le stocker de telle sorte que nous utilisons peu de mémoire mais que nous puissions effectuer cette opération de vérification dans le pire des cas , alors clarifions cela. Expliquez également quel est le modèle de calcul si vous voulez une borne inférieure.

O (1)

$O(1)$

Kaveh

citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5421

Kaveh

IIUC, le papier dit que la réponse pour 1D est vraiment bits et l'idée est de stocker toutes les petites boîtes plus toutes les boîtes avec des longueurs de puissance 2 et d'autres boîtes peuvent être obtenues à partir de boîtes len pow-2 en constante temps ( ) et il me semble que la même chose fonctionnerait ici et bits suffiraient.

O (n \lg n)

$O(n\lg n)$

O (2^{k})

$O(2^k)$

O (n^{k} \lg^{k} n)

$O(n^k\lg^k n)$

Kaveh

Merci, j'ai ajouté quelques éclaircissements. Le journal n'a-t-il pas dit que leur principale contribution était l'utilisation de bits dans le prétraitement et le stockage?

2 n + o (n)

$2n+o(n)$

Chao Xu

Désolé, celui que j'ai décrit provenait d'un travail précédent. Cependant, leur résultat semble être conceptuellement similaire, c'est-à-dire qu'ils divisent le tableau en blocs, précalculent la réponse sur eux et utilisent un nombre constant d'entre eux pour calculer la réponse pour n'importe quel donné. Si en kD le nombre de blocs de base dont on a besoin pour calculer la réponse à un bloc arbitraire est une constante, alors un algorithme similaire fonctionnerait ici et donnerait probablement quelque chose comme (je n'ai pas ' t vérifier que c'est le cas).

O (n^{k}) = O (N)

$O(n^k) = O(N)$

Kaveh

Complexité binaire d'une requête de plage de temps O (1) dans un tableau -ary

Réponses: