Tri comparatif
| n | log log 2 (n! ) { {\displaystyle\left\lceil\log_{2}(n!) \right\rceil}
|
Minimum |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 ou 46 |
| 17 | 49 | 49 ou 50 |
| 18 | 53 | 53 ou 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | log log 2 (n! ) { {\displaystyle\left\lceil\log_{2}(n!) \right\rceil}
|
n log 2 n n-n ln 22 {\displaystyle n\log_{2} n -{\frac{n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
au nombre minimum réel de comparaisons (à partir de OEIS: A036604) nécessaires pour trier une liste de n éléments (dans le pire des cas). Ci-dessous: En utilisant l’approximation de Stirling, cette borne inférieure est bien approximée par n log 2 n-n ln 2 {\displaystyle n\log_{2} n-{\frac{n}{\ln 2}}}
.
Le nombre de comparaisons qu’un algorithme de tri de comparaison nécessite augmente proportionnellement à n log (n) {\displaystyle n\log(n)}
, où n {\displaystyle n}
est le nombre d’éléments à trier. Cette limite est asymptotiquement serrée.
Étant donné une liste de nombres distincts (nous pouvons le supposer car il s’agit d’une analyse du pire des cas), il y a n permutations factorielles dont exactement l’une est la liste dans l’ordre trié. L’algorithme de tri doit tirer suffisamment d’informations des comparaisons pour identifier la permutation correcte. Si l’algorithme se termine toujours après au plus f(n) étapes, il ne peut pas distinguer plus de 2f(n) cas car les clés sont distinctes et chaque comparaison n’a que deux résultats possibles. Par conséquent,
2 f(n) ≥ n! {\displaystyle 2^{f(n)}\geq n!}
, ou de manière équivalente f(n) ≥ log 2 (n! ) . {\displaystyle f(n)\geq\log _ {2}(n!).}
En regardant le premier n/2 {\displaystyle n/2}
facteurs de n! = n(n-1) { 1 {\displaystyle n!= n(n-1) \ cdots 1}
, on obtient log 2 (n! ) ≥ log 2 ((n 2) n 2) = n 2 log n log 2 − n 2 = Θ (n log n). {\displaystyle\log_{2} (n!) \geq\log_ {2}\left(\left({\frac{n}{2}}\right) ^{\frac{n}{2}}\right) = {\frac{n}{2}} {\frac{\log n} {\log 2}} – {\frac{n}{2}} = \Theta(n\log n).}
log 2 (n! ) = Ω(n log n). {\displaystyle\log_{2} (n!) = \Omega(n\log n).}
Cela fournit la partie inférieure de la réclamation. Une meilleure limite peut être donnée via l’approximation de Stirling.
Une borne supérieure identique découle de l’existence des algorithmes qui atteignent cette borne dans le pire des cas, comme heapsort et mergesort.
L’argument ci-dessus fournit une limite inférieure absolue, plutôt que seulement asymptotique sur le nombre de comparaisons, à savoir loglog 2 (n! ) { {\displaystyle\left\lceil\log_{2}(n!) \ droit \rceil }
comparaisons. Cette limite inférieure est assez bonne (elle peut être approchée dans une tolérance linéaire par un simple tri de fusion), mais elle est connue pour être inexacte. Par exemple, loglog 2 2 (13! ) == 33 {\displaystyle\left\lceil\log_{2}(13!) \ droit \rceil =33}
, mais le nombre minimal de comparaisons pour trier 13 éléments s’est avéré être de 34.
Déterminer le nombre exact de comparaisons nécessaires pour trier un nombre donné d’entrées est un problème difficile sur le plan informatique, même pour les petits n, et aucune formule simple pour la solution n’est connue. Pour certaines des quelques valeurs concrètes qui ont été calculées, voir OEIS: A036604.
Borne inférieure pour le nombre moyen de comparaisons
Une borne similaire s’applique au nombre moyen de comparaisons. En supposant que
- toutes les clés sont distinctes, c’est-à-dire que chaque comparaison donnera soit un > b, soit un < b, et
- l’entrée est une permutation aléatoire, choisie uniformément dans l’ensemble de toutes les permutations possibles de n éléments,
il est impossible de déterminer dans quel ordre se trouve l’entrée avec moins de log2(n!) comparaisons en moyenne.
Cela peut être plus facilement vu en utilisant des concepts de la théorie de l’information. L’entropie de Shannon d’une telle permutation aléatoire est log2(n!) bit. Comme une comparaison ne peut donner que deux résultats, la quantité maximale d’informations qu’elle fournit est de 1 bit. Par conséquent, après k comparaisons, l’entropie restante de la permutation, compte tenu des résultats de ces comparaisons, est au moins log2(n!) – k bits en moyenne. Pour effectuer le tri, des informations complètes sont nécessaires, l’entropie restante doit donc être 0. Il s’ensuit que k doit être au moins log2(n!) en moyenne.
La borne inférieure dérivée par la théorie de l’information est formulée comme “borne inférieure de la théorie de l’information”. La borne inférieure de la théorie de l’information est correcte mais n’est pas nécessairement la borne inférieure la plus forte. Et dans certains cas, la limite inférieure théorique de l’information d’un problème peut même être loin de la vraie limite inférieure. Par exemple, la limite inférieure de la sélection en théorie de l’information est loglog 2 ((n) {{\displaystyle\left\lceil\log_{2}(n)\right\rceil }
alors que n−1 {\displaystyle n-1}
des comparaisons sont nécessaires par un argument contradictoire. L’interaction entre la limite inférieure de la théorie de l’information et la vraie limite inférieure ressemble beaucoup à une fonction à valeur réelle limitant une fonction entière. Cependant, ce n’est pas exactement correct lorsque le cas moyen est considéré.
Pour découvrir ce qui se passe lors de l’analyse du cas moyen, la clé est que à quoi fait référence “moyenne”? Moyenne sur quoi? Avec une certaine connaissance de la théorie de l’information, la limite inférieure de la théorie de l’information fait des moyennes sur l’ensemble de toutes les permutations dans son ensemble. Mais tous les algorithmes informatiques (selon ce que l’on croit actuellement) doivent traiter chaque permutation comme une instance individuelle du problème. Par conséquent, la limite inférieure moyenne que nous recherchons est moyennée sur tous les cas individuels.
Pour rechercher la borne inférieure relative à la non-réalisabilité des ordinateurs, nous adoptons le modèle de l’arbre de décision. Reformulons un peu ce qu’est notre objectif. Dans le modèle de l’arbre de décision, la borne inférieure à afficher est la borne inférieure de la longueur moyenne des chemins racine-feuille d’un n! {\displaystyle n!}
– arbre binaire foliaire (dans lequel chaque feuille correspond à une permutation). Il serait convaincu de dire qu’un arbre binaire complet équilibré atteint le minimum de la longueur moyenne. Avec quelques calculs minutieux, pour un arbre binaire complet équilibré avec n! {\displaystyle n!}
feuilles, la longueur moyenne des chemins racine-feuille est donnée par (2 n! – 2 log log 2 n n! log +1) log log 2 n n! log + (2 log log 2 n n! ⌋ +1-n! ) log log 2 n n! n n! {\displaystyle{\frac{(2n!-2 ^{\lfloor\log_{2}n!\rfloor+1}) \cdot\lceil\log_ {2}n!\rceil+(2^{\lfloor\log_{2}n!\rfloor +1} -n!) \cdot\lfloor\log_{2}n!\rfloor} {n!}}}
Par exemple, pour n = 3, la limite inférieure de la théorie de l’information pour le cas moyen est d’environ 2,58, tandis que la limite inférieure moyenne dérivée via le modèle de l’arbre de décision est de 8/3, soit environ 2,67.
Dans le cas où plusieurs éléments peuvent avoir la même clé, il n’y a pas d’interprétation statistique évidente pour le terme “cas moyen”, donc un argument comme celui ci-dessus ne peut pas être appliqué sans faire des hypothèses spécifiques sur la distribution des clés.
