Structure de données basée sur la comparaison pour rechercher des éléments

Existe-t-il une structure de données qui prend un tableau non ordonné de éléments, effectue un prétraitement dans et répond aux requêtes: existe-t-il un élément dans la liste, chaque requête au pire moment ? $n$ $O(n)$ $x$ $O(\log n)$

Je pense vraiment qu'il n'y en a pas, donc la preuve qu'il n'y en a pas est également la bienvenue.

ds.data-structures sorting Chi-Lan
la source

(1) Je ne sais pas pourquoi vous pouvez dire «Bien sûr, je considère le temps attendu», car vous ne dites pas du tout «attendu» dans votre question. S'il vous plaît, essayez de préciser votre question avant de dire «bien sûr.» (2) S'il vous plaît définir «non-hashable».

Tsuyoshi Ito

(1) je vois. Merci pour l'explication. Si quelqu'un demandait «Vous vous souciez de la durée?», Alors la réponse serait bien «bien sûr.» :) (2) Je pense que «la seule action autorisée est de comparer deux valeurs dans la liste» est beaucoup plus précise. pouvez-vous modifier la question de sorte que les utilisateurs ne soient pas obligés de lire les commentaires pour comprendre ce que “non-lavable” signifie?

Tsuyoshi Ito

À propos, si vous ne pouvez pas le prouver, pourquoi savez-vous que c'est impossible? S'il s'agit d'un exercice dans un manuel ou une classe, vous posez la question sur un mauvais site.

Tsuyoshi Ito

S'agit-il de votre question: existe-t-il une structure de données qui prend un tableau non ordonné de n éléments, effectue un prétraitement dans O (n) et répond aux requêtes: y a-t-il un élément x dans la liste, chaque requête au pire moment O (log n)?

sdcvvc

@ Filip: Est-ce facile à voir? Si c'est vrai, alors je conviens que cela résout la question.

Tsuyoshi Ito

Réponses:

Voici une preuve que c'est impossible. Supposons que vous puissiez construire une telle structure de données. Construit le. Choisissez ensuite éléments au hasard dans la liste, ajoutez à chacun d’eux, où est inférieur à la différence entre deux éléments de la liste, puis exécutez les requêtes pour vérifier si l’un des éléments résultants est correct. est dans la liste. Vous avez déjà effectué requêtes. $n/\log n$ $\epsilon$ $\epsilon$ $O(n)$

Je voudrais affirmer que les comparaisons que vous avez effectuées sont suffisantes pour dire si un élément de la liste d'origine est plus petit ou plus grand que tout nouvel élément . Supposons que vous ne puissiez pas dire. Ensuite, puisqu'il s'agit d'un modèle basé sur la comparaison, vous ne pouvez pas savoir si est égal à ou non, ce qui contredit l'hypothèse selon laquelle votre structure de données fonctionne. $a$ $b$ $a$ $b$

Maintenant, puisque les éléments vous avez choisis étaient aléatoires, vos comparaisons ont avec une probabilité élevée suffisamment d’informations pour diviser la liste initiale en répertorie chacune des tailles de taille . En triant chacune de ces listes, vous obtenez un algorithme de tri temporel aléatoire basé uniquement sur des comparaisons, une contradiction. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

Peter Shor
la source

Quelques conseils pour aider à comprendre la preuve (si je comprends bien moi - même bien sûr): les

articles doivent être remplis par les éléments après

leur a été ajoutée; le modèle de comparaison vous garantit de savoir dans quels cas

; les

listes sont dans 'l'ordre croissant': chaque élément d'une liste supérieure est supérieur à chaque élément d'une liste inférieure; après les requêtes d'origine, vous avez suffisamment d' informations pour faire la liste autour des éléments que vous avez choisis au hasard,

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

Alex ten Brink

(suite) Notez qu'il n'est même pas nécessaire de pouvoir explicitement créer la liste dans le délai imparti pour que la preuve soit conservée.

Alex ten Brink

Je ne comprends pas cette preuve. La contradiction finale est off « algorithme basé uniquement sur des comparaisons », mais dans les premières étapes de notre algorithme , nous avons ajouté

à chaque élément (plus loin, « où

est plus petite que la différence entre les deux éléments de la liste »). Pourquoi sommes-nous toujours justifiés que notre algorithme ne repose que sur la comparaison si nous supposons que nos articles ont un ordre total non discret?

ϵ

$\epsilon$

ϵ

$\epsilon$

Artem Kaznatcheev

@Artem: Votre entrée d' origine est constituée d'éléments

. Ensuite, vous construisez un nouvel ensemble

; vous représenter un original

en tant que

et une version modifiée

que

. Maintenant, vous utilisez l'algorithme de boîte noire; l'algorithme compare des éléments de

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$ l'un à l'autre; pour répondre à de telles questions, il vous suffit de comparer un nombre constant d'éléments de

les uns aux autres. Par conséquent, tout devrait être faisable dans le modèle de comparaison, avec des frais généraux constants.

X

$X$

Jukka Suomela

@ Aryabhata: c'est le cas. Qu'est-ce que l' algorithme

O (\log^{2} n)

$O(\log^2 n)$

Peter Shor

Je crois qu’il s’agit d’une preuve différente, prouvant l’impossibilité d’une structure temporelle de requêtes , avec un prétraitement . $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Supposons que dans le prétraitement, vous faites des comparaisons , aboutissant à un ordre partiel. $\mathcal{O}(n)$

Considérons maintenant la taille du plus grand antichain en cela. Puisque ces éléments ne sont pas comparables, pour que nous ayons un algorithme de requête , nous devons avoir ce . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Selon le théorème de Dilworth, il existe une partition de taille , en chaînes. $A$

Nous pouvons maintenant compléter l’algorithme pour déterminer les chaînes dans la partition. Nous pouvons déterminer si deux éléments sont comparables en créant un graphe de comparaisons dirigé et en effectuant une analyse d'accessibilité. Cela peut être fait sans comparaison supplémentaire. Il suffit maintenant de forcer brutalement chaque partition possible de taille pour déterminer s’il s’agit d’une partition de chaînes. $A$

Une fois que nous avons les chaînes, nous pouvons les fusionner pour donner un algorithme de comparaison permettant de trier la liste complète. $\mathcal{O}(n \log \log n)$

Aryabhata
la source

C'est une bonne idée. Et si vous pouviez montrer que l'algorithme doit connaître la partition de la chaîne, vous pouvez utiliser mergesort pour montrer qu'il ne faudrait qu'une comparaison supplémentaire O (n log log n) pour trier toute l'entrée, plutôt que d'utiliser Jensen. Mais il y a un problème: pourquoi l'algorithme de pré-traitement doit-il construire une partition en chaîne? Une partition en chaîne doit exister, oui, mais c'est très différent de la connaissance de l'algorithme.

David Eppstein

Ok, je crois maintenant cette preuve. Et cela montre plus clairement que pour atteindre le temps de requête polylog, vous devez utiliser un certain nombre de comparaisons comprises dans un tri additif

. Agréable. À propos, la partition de la chaîne peut être trouvée en temps polynomial à partir de l'ensemble de comparaisons déjà effectuées, plutôt que de nécessiter une recherche en force brute, mais cela ne change rien à votre argument.

O (n \log \log n)

$O(n\log\log n)$

David Eppstein

Les preuves montrent en fait que vous devez avoir un prétraitement

pour chaque requête. Bien sûr les deux sont serrés. Cela montre que la recherche binaire et la recherche linéaire sont les seuls algorithmes de recherche "intéressants" (du moins dans le monde classique).

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

Yuval Filmus

@Yuval: Peut-être devriez-vous écrire cette observation comme une réponse réelle, car il me semble que vous devez effectuer un travail modéré pour obtenir le résultat ci-dessus à partir des preuves dans les réponses.

Peter Shor

@Yuval: en pensant aux preuves, je vois seulement que vous devez avoir soit un prétraitement

soit un temps de requête

pour tout

. Il est possible d'avoir un temps de prétraitement

et un temps de requête

. On peut diviser la liste en

listes de taille

chacune dans le temps

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

utilisant plusieurs fois la médiane.

θ (n \log \log n)

$\theta(n \log\log n)$

Peter Shor le

Comme le note la réponse de Peter Shor, pour exclure l'appartenance à un modèle basé sur la comparaison, nous devons savoir comment l'élément se compare à chaque membre. Ainsi, en utilisant requêtes aléatoires (le nombre de membres inférieur au non-membre interrogé est aléatoire), nous obtenons des informations relatives à valeurs non triées. Par conséquent, pour une constante , en utilisant $k<n$ $Θ(n \log k)$ $n$ $c>0$ pré-traitement, on ne peut pas avoir $c \, n \log k$ coût de la requête. C'est optimal jusqu'à un facteur constant puisque nous pouvons trier les données dans approximativement égaux (chaque compartiment non trié) dans temps, ce qui permet à le coût de la requête. $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ $O(n/k')$

En particulier, en utilisant le prétraitement , nous ne pouvons pas avoir le coût de la requête . En outre, le prétraitement correspond à dans pour chaque et donc pour le coût de la requête. $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

Dmytro Taranovsky
la source