Limites inférieures pour les structures de données

14

Connaît-on des résultats qui excluent l'existence de structures de données «trop belles pour être vraies»?

Par exemple: peut-on ajouter des fonctionnalités et à une structure de données de maintenance de commande (voir Dietz et Sleator STOC '87 ) tout en obtenant des opérations de temps ? $Split$ $Join$ $\mathcal{O}(1)$

Ou: peut-on implémenter un ensemble ordonné avec des clés entières et opérations de temps ? Bien sûr, cela est au moins aussi difficile que de découvrir un algorithme de temps linéaire pour trier les entiers. $\mathcal{O}(1)$

La réponse a-t-elle été prouvée non pour l'une ou l'autre de ces questions? Les résultats de la borne inférieure sont-ils connus pour une structure de données naturelle?

ds.data-structures big-list lower-bounds time-complexity Shaun Harker
la source

Les choses changent si nous pouvons ajouter des limites à l'espace des problèmes. Par exemple, si nous avons un ensemble limité de clés et suffisamment de mémoire, nous pouvons les trier en temps linéaire en utilisant un vecteur de bits.

jetru

1

Je pense que la raison pour laquelle vous n'obtenez pas trop de réponses à cette question est qu'il y a tellement de possibilités. Beaucoup, beaucoup de structures de données ont connu des limites inférieures, et il est difficile de ne pas simplement tomber dessus. Une recherche Google pour "structure de données" "borne inférieure" comprend, pour moi, 5 articles qui doivent encore être mentionnés dans ce fil. Je pense que vous auriez plus de succès à obtenir une réponse à votre question si vous la restreigniez, peut-être en supprimant la partie sur les "structures de données naturelles" et en posant simplement des questions sur la maintenance des listes ou les ensembles ordonnés entiers (mais pas les deux dans une seule question).

jbapple

J'ai omis que les 5 articles que j'ai trouvés dans la recherche Google se trouvent sur la première page des résultats de recherche.

jbapple

@jbapple: Vous avez raison! Je pense que les clics des personnes de cette communauté qui essaient de m'aider avec ma question ont poussé les bons résultats en haut de la liste. (Par exemple, CETTE page est maintenant sur la liste!) Je ne me souviens pas qu'elle ait été utile lors de la première recherche, ou j'aurais probablement restreint la question comme vous le suggérez. (Ou j'étais un gros mannequin, c'est possible aussi. :))

Shaun Harker

19

Il y a une discussion vraiment sympa sur les limites inférieures dynamiques sur les graphiques de Mihai Pătraşcu. En résumé (à la p.20 des diapositives), nous avons les bornes inférieures en termes de temps de requête et de temps de mise à jour (insérer un bord): $t_q$ $t_u$

entrez la description de l'image ici

Consultez le document pour plus de détails. Quelques autres papiers de Mihai sont également pertinents et agréables.

MISE À JOUR: J'ai trouvé que sa thèse de doctorat " Techniques de limite inférieure pour les structures de données " fournit des limites inférieures pour de nombreux problèmes centraux de structure de données en utilisant les techniques qu'il a développées. Cela vaut certainement la peine d'être lu.

Hsien-Chih Chang 張顯之
la source

1

Cette thèse est magnifique, merci beaucoup d'avoir partagé le lien.

Shaun Harker

6

La réponse à l'une de vos questions dépend du modèle de calcul. Par exemple, sur de nombreuses machines, la multiplication d'entiers est plus coûteuse que leur ajout. Certains modèles reflètent cela, d'autres non.

$O(\sqrt{\log n/ \log \log n})$

jbapple
la source

Agréable. Mais il semble que vous ayez surestimé le résultat dans le document d'Andersson et Thorup. Elle ne s'applique qu'aux structures spatiales linéaires, pas à toutes les structures spatiales polynomiales.

Shaun Harker

2

Andersson et Thorup citent Beame et Fich pour l'espace polynomial: «La borne inférieure découle d'un résultat de Beame et Fich. Elle montre que même si nous voulons simplement prendre en charge les opérations d'insertion et de prédécesseur dans l'espace polynomial, l'une de ces deux opérations a un pire borne de Ω (sqrt (log n / log log n)), correspondant à notre borne supérieure commune. Nous notons que l'on peut trouver de meilleures bornes et des compromis pour certaines des opérations individuelles. En effet, nous prendrons en charge min, max, prédécesseur, successeur et opérations de suppression en temps constant, et n'insèrent et ne recherchent qu'en Θ (sqrt (log n / log n)). "

jbapple

Je vois, l'espace linéaire entre pour annoncer la limite supérieure , mais le corollaire 3.10 de Beame et Fich donne la limite inférieure du polyespace , comme vous l'avez dit et je l'ai bêtement contredit. Il me vient également à l'esprit que l'on pourrait vouloir annoncer les pires moments pour les limites supérieures tout en annonçant les temps amortis pour les limites inférieures. Le document d'Andersson et Thorup cite en effet (page 5) Beame et Fich pour une borne inférieure (et supérieure) amortie. Mais le corollaire 3.10 ne semble donner que la borne inférieure du pire des cas. Peut-être que quelqu'un pourrait me donner un indice à ce sujet également?

Shaun Harker

2

$O(n \log n)$ afin de prouver l'inexistence de superstructures.

De plus, il n'est pas rare d'utiliser des arguments de théorie de l'information (par exemple la complexité de Kolmogorov) afin de prouver les limites inférieures des structures de données.

chazisop
la source

Limites inférieures pour les structures de données

Réponses: