Tri avec une moyenne de

Mise à jour: j'ai développé cette réponse dans un tri $\mathrm{lg}(n!)+o(n)$ papier avec une moyenne de comparaisons .

Oui, un tel algorithme existe. Je prouverai seulement la limite $\mathrm{lg}(n!)+o(n)$ , mais sous une hypothèse de randomisation probable, nous obtenons également $\mathrm{lg}(n!)+O(n^{1-ε})$ . Je décrirai également une tentative pour $n^{0.5+o(1)}$ et $O(n^{0.5-ε})$ .

On peut supposer que tous les éléments sont distincts, en les annotant si nécessaire; le cas moyen utilise des éléments distincts dans un ordre aléatoire. Nous pouvons calculer le nombre moyen de comparaisons en ajoutant la perte d'entropie pour chaque comparaison par rapport à l'utilisation d'une pièce équitable.

Le point de départ est une sorte d'insertion avec une recherche binaire pour décider où insérer l'élément suivant dans le sous - ensemble Sorted . Lorsque , une insertion utilise au plus comparaisons, qui (en termes d'entropie) est optimale jusqu'à un facteur additif (et pour la complexité moyenne, $S$ $(1-ε)2^m ≤ |S| ≤ 2^m-1$ $m$ $O(ε)$ $2^m ≤ |S| ≤ (1+ε) 2^m$ fonctionne également). Maintenant, quand n'est pas proche d'une puissance de 2, l'insertion d'un élément est sous-optimale (même dans le cas moyen et quelle que soit la façon dont nous équilibrons chaque requête), mais en gaspillant les comparaisons de , nous pourrions orienter vers une distribution approximativement uniforme sur un intervalle de de longueur proche d'une puissance de 2, on obtient l'optimalité souhaitée. $|S|$ $A$ $o(1)$ $A$ $S$

Nous y parvenons en ajoutant des éléments en lots, et parfois en comparant efficacement les éléments du lot entre eux, de sorte que l'intervalle de correspondant à un élément diminue de manière quasi aléatoire (et avec la distribution de probabilité de à l'intérieur de l'intervalle à peu près uniforme), et lorsque la longueur de l' intervalle est suffisamment proche d'une puissance de 2, en faisant la recherche binaire pour insérer . $S$ $A$ $A$ $A$

Constructions communes

Nous garderons un sous-ensemble d'éléments triés, et pour chaque élément non trié , nous garderons la trace de l'intervalle minimal de où est connu pour être localisé. est la longueur de ; est par l'identité des intervalles. $S$ $A$ $I_A$ $S$ $A$ $|I_A|$ $I_A$ $I_A=I_B$

Soit : Comparez avec , puis (dans un ordre aléatoire) comparez et avec les éléments correspondants de jusqu'à ce que leurs intervalles soient disjoints (ou aient une longueur 1). L'élément de est choisi (de manière cohérente) pour rendre les probabilités de comparaison aussi proches que 1/2 que possible, en supposant que lorsque est appelé, $\mathrm{Compare}(A,B)$ $A$ $B$ $A$ $B$ $S$ $S$ $\mathrm{Compare}$ $(A,B)$ est uniformément distribué sur . En raison de la disjonction à la fin, préserve l'hypothèse d'uniformité. $I_A⨯I_B$ $\mathrm{Compare}$

Les sections suivantes peuvent être lues indépendamment les unes des autres.

A algorithme $\mathrm{lg}(n!)+o(n)$

Éléments fournis : une liste triée et un lot de éléments non triés; ; les éléments non triés sont aléatoires par rapport à . $S$ $m$ $m∈ω(1)∩o(|S|)$ $S$

Répétez (1) - (3) autant que possible:
1. Choisissez deux éléments et du lot avec (tout choix fonctionnera). 2. Exécutez . 3. Si est assez proche d'une puissance de 2, ^{(note 1)} retirer du lot (sans oublier ); et faire de même avec . Enfin: insérez tous les éléments dans $A$ $B$ $I_A=I_B$
$\mathrm{Compare}(A,B)$
$|I_A|$ $A$ $I_A$ $B$
et complétez le tri. $S$

Note 1: Pour "assez proche", toute erreur relative (en fonction de ) fonctionne tant que les éléments seront supprimés à l'étape (4) (possible par la note 2). Sous une hypothèse de randomisation conjecturée, en utilisant l'erreur relative capture éléments, permettant a $o(1)$ $m$ $m-o(m)$ $c \log \log m / \log m$ $m(1-\log^{-Θ(c)}m)$ algorithme de tri de comparaison moyenne. $\mathrm{lg}(n!)+O(n \log \log n / \log n)$

Remarque 2: Étant donné que la même séquence de comparaisons conduit au même intervalle de délimitation, presque tous les éléments passeront par l'étape (1) fois (sauf s'ils sont supprimés à l'étape 4). Au début, si et on prend , on compare à l'élément $Ω(\log m)$ $A < B$ $A$ $A$ , et chaque application de l'étape (3) àa uneprobabilité de réduction deen $S[≈(1-1/\sqrt{2})|S|]$ $A$ $O(1)$ $|I_A|$ fois. Maintenant, pour chaque rapportqui n'est pas une puissance rationnelle de 2, nous avons $≈1/(1-1/\sqrt{2})$ $a>1$ , et donc nous obtenons laborne. $∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$ $o(n)$

Un algorithme probable $\mathrm{lg}(n!)+O(n^{1-ε})$

Modulo une hypothèse de randomisation, nous pouvons obtenir des comparaisons moyennes comme suit. $\mathrm{lg}(n!)+O(n^{1-ε})$

Mélangez au hasard les éléments et triez la première moitié dans une liste , tout en conservant la seconde moitié en tant que lot non trié. $S$
Répétez jusqu'à ce que le lot soit vide:
choisissez au hasard . Soit . Si est vide, retirez du lot et l' insérer dans . Autrement: $A∈\text{batch}$ $G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$ $G$ $A$ $S$
1. S'il y a tel qu'avec la probabilité (disons ≥0,05), fait dans erreur relative d'une puissance de 2, exécuter et en cas de succès (ie est dans $B∈G$ $Θ(1)$ $\mathrm{Compare}(A,B)$ $|I_A|$ $n^{-ε}$ $\mathrm{Compare}(A,B)$ $|I_A|$ l' erreur relative d'une puissance de 2), retirerpartir du lot etinsérer dans. $n^{-ε}$ $A$ $S$
2. S'il n'y a pas de , exécutez pour un aléatoire . $B∈G$ $\mathrm{Compare}(A,B)$ $B∈G$

Si notre hypothèse de randomisation fonctionne (c'est-à-dire que la distribution des longueurs et des positions d'intervalles est suffisamment aléatoire), alors tout au long du processus, un typique peut être efficacement comparé à un choix de éléments (avec différentes longueurs d'intervalle). Ainsi, nous pouvons généralement choisir une comparaison pour (1) ci - dessus, et si nous sommes malchanceux avec le résultat de la comparaison, nous obtenons toujours chances, réalisant ainsi (si est assez petit, disons 0,01) a $A$ $n^{Θ(1)}$ $n^{Θ(1)}$ $Θ(\log n)$ $ε$ Algorithme de comparaison . Avec quelques modifications et approximations, le calcul total peut être rendu quasi linéaire: étant donné un élément , calculez des longueurs d'intervalle prometteuses, puis recherchez s avec le centre approximatif et les longueurs d'intervalle appropriés. $\mathrm{lg}(n!)+O(n^{1-ε})$ $A$ $B$

Il existe un certain nombre de façons d'optimiser les comparaisons, mais l'obstacle est que chaque comparaison peut finir par être malchanceuse et nous avons un nombre limité de comparaisons. Si après optimisation, fait une moyenne de 4 comparaisons et 'réussit' avec 1/4 probabilité, on obtient . $\mathrm{Compare}(A,B)$ $ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$

Une approche peut-être bien meilleure consiste à attendre qu'un intervalle soit proche d'une puissance de 2, en contrôlant non pas les longueurs d'intervalle individuelles mais les distributions de longueurs.

Une tentative d' algorithme $\mathrm{lg}(n!)+n^{0.5+o(1)}$

Supposons que et on nous donne un lot non trié de éléments avec les intervalles également donnés, avec typiquement et avec $|S|=n$ $n$ $I_A$ $|I_A|$ $n^{1-o(1)}$ distribué uniformément (jusqu'à une erreur aléatoire, et tenant avec une précision suffisante même s'il est conditionné sur). Ensuite, nous pouvons trier les éléments perdant une moyenne decomparaisons comme suit: (*) Insérer tous les éléments dans l'ordre de leur initial $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ $A < S[i]$ $n^{0.5+o(1)}$
. De cette façon, tous les éléments sont insérés lorsque leur longueur d'intervalle est proche d'une puissance de 2. $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

L'algorithme de tri sera: lecture aléatoire de la liste et au hasard sorte la première moitié . Pour insérer la seconde moitié, faites la bonne distribution et faites le (*) ci-dessus. $S$

Pour faire le droit de distribution, nous pouvons faire une distribution «aléatoire», puis retenir la bonne fraction des éléments pour chaqueen randomisant le reste (en répétant si nécessaire). Cependant, alors que cela devrait corriger $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ $|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$ globalement, nous ne savons pas s'il peut être contrôlé localement avec la précision requise (d'où le mot "tentative" ci-dessus). $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

Pour faire une distribution «aléatoire», nous pouvons utiliser au hasard avec , sauf qu'avec le initial tous identiques, nous ne nous attendons pas à une randomisation à une profondeur sublogarithmique (ie avec assez longtemps). Cependant, je suppose que nous obtenons la randomisation à une profondeur sublogarithmique en utilisant des généralisations (probablement tout choix raisonnable fonctionnera) de to $\mathrm{Compare}(A,B)$ $P(A < B)≈0.5$ $I_A$ $I_A$ $\mathrm{Compare}$ éléments: Si nous gardons enchevêtrements (ie connectésutilisantrésultats decomparaison), nous devrions avoirsujet choix pour chaque comparaison commutent pas avec . Cela devrait permettre laprofondeur de randomisation , comme souhaité (en supposant que n'est pas trop grand car nous avons besoin de la profondeur $k=ω(1)$ $k=ω(1)$ $k$ $S$ $O(\log_k n + \log k)$ $k$ $Θ(\log k)$ pour éloigner les éléments). Je m'attends à ce que le calcul puisse être rendu quasi linéaire si vous utilisez un assez petit . $k$

Depuis une comparaison avec oui probabilité que les déchets entropie, la randomisation initiale et la légère non - uniformité des éléments dans leurs intervalles de délimitation doit seulement besoin déchets entropie. Si la mise en forme de la distribution réussit assez bien, les déchets d'entropie proviennent principalement de disparités de longueur d'intervalle pendant (*) (d'où le ). $1/2+n^{-0.5}$ $O(1/n)$ $n^{o(1)}$ $n^{0.5+o(1)}$

Une combinaison possible de : $\mathrm{lg}(n!)+O(n^{0.5-ε})$ si la mise en forme de la distribution fonctionne assez bien et que la taille du lot est égale et rejeter sélectivement éléments dans (*) (ci-dessus), nous pouvons insérer tous sauf ces avec des déchets d'entropie $|S|+n^{0.5+ε}$ $≈n^{0.5+ε}$ $≈n^{0.5+ε}$ comme suit. Fractionneren intervalles presque égaux, et lorsque lors de l'insertion, fixe sur un intervalle, rejeter (c'est-à-dire annuler l'insertion) si l'intervalle est trop long, réduisant ainsi la variation des longueurs de ces intervallesfois, ce qui réduit à son tour les variations de longueur d'intervallesde longueur aléatoire dans $n^{0.5-ε/2+o(1)}$ $S$ $n^ε$ $I_A$ $Θ(n^{ε/2})$ $n^{1-o(1)}$ $n^{ε/2-o(1)}$ fois, au besoin. Maintenant, nous pouvons utiliser l' algorithme ci-dessus pour insérer les éléments restants avec déchets si est suffisamment petit. $\mathrm{lg}(n!)+O(n^{1-ε})$ $O(n^{0.5-ε'})$ $ε$

Complexité du pire cas de tri: Très probablement, il existe un algorithme de tri avec comparaisons du pire cas. Pour trouver la médiane, il existe un écart linéaire entre le cas moyen ( comparaisons) et le pire des cas (au moins comparaisons). Cependant, pour le tri, il y a beaucoup de liberté pour organiser des comparaisons et pour trouver de nouveaux algorithmes de tri. $\mathrm{lg}(n!)+o(n)$ $1.5n+o(n)$ $(2+ε)n-O(1)$

Dmytro Taranovsky
la source

Je pense que vous devriez écrire ceci comme un papier.

Emil Jeřábek le

@ EmilJeřábek D'accord. En tant que site de recherche, de nombreuses questions et réponses sont ici des mini-articles, mais avec la longueur et l'importance ici, un article formel est souhaitable. N'hésitez pas à me faire savoir (à [email protected]) quelles parties devraient être développées dans le document (cette réponse restant sous forme de version concise).

Dmytro Taranovsky

Tri avec une moyenne de

Réponses: