L’art de la machinerie

Tout manuel d’algorithmique décent expliquera à quel point les algorithmes de tri comme quicksort et heapsort sont rapides, mais il ne faut pas de mathématiques folles pour prouver qu’ils sont aussi asymptotiquement rapides que possible.

Une note pédante sur la notation

La plupart des informaticiens utilisent la notation big-O pour signifier « asymptotiquement égal, jusqu’à un facteur d’échelle constant », ce qui n’est pas tout à fait ce que cela signifie pour les autres mathématiciens. Désolé, j’utiliserai big-O comme dans les manuels de CS, mais au moins je ne le mélangerai pas avec d’autres notations mathématiques.

Tri basé sur la comparaison

Regardons le cas particulier des algorithmes qui comparent les valeurs deux à la fois (comme quicksort et heapsort, et la plupart des autres algorithmes populaires). Les idées peuvent être étendues à tous les algorithmes de tri plus tard.

Un argument de comptage simple pour le pire cas

Supposons que vous ayez un tableau de quatre éléments, tous différents, dans un ordre aléatoire. Pouvez-vous le trier en comparant seulement une paire d’éléments ? De toute évidence, non, mais voici une bonne raison qui prouve que vous ne le pouvez pas : par définition, pour trier le tableau,vous devez savoir comment réorganiser les éléments pour les mettre dans l’ordre. En d’autres termes, vous devez savoir quelle permutation est nécessaire. Combien de permutations possibles y a-t-il ? Le premier élément peut être déplacé à l’une des quatre places, le deuxième peut aller à l’une des trois autres, le troisième a deux possibilités et le dernier doit prendre la place restante. Il y a donc 4×3×2×1=4!=244 fois 3 fois 2 fois 1 = 4 ! = 24 permutations possibles, mais il n’y a que deux résultats possibles en comparant deux choses différentes : « PLUS GRAND » et « PLUS PETIT ». Si vous faites une liste de toutes les permutations possibles, vous pourriez décider que « PLUS GRAND » signifie que vous avez besoin de la permutation n°8 et « PLUS PETIT » de la permutation n°24, mais il n’y a aucun moyen de savoir quand vous avez besoin des 22 autres permutations.

Avec deux comparaisons, vous avez 2×2=42 \times 2 = 4 sorties possibles, ce qui n’est toujours pas suffisant. Vous ne pouvez pas trier tous les tableaux mélangés possibles à moins de faire au moins cinq comparaisons (25=322^5 = 32). Si W(N)W(N) est le nombre de comparaisons le plus défavorable nécessaire pour trier NN éléments différents en utilisant un certain algorithme, nous pouvons dire

2W(N)≥N!2^{W(N)}. \geq N!

En prenant un logarithme base 2,

W(N)≥log2N!W(N) \geq \log_2{N!}

Asymptotiquement, N!N ! croît comme NNN^N (voir aussi la formule de Stirling), donc

W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}

Et c’est une limite O(NlogN)O(N\log N) sur le pire cas juste en comptant les sorties.

Cas moyen à partir de la théorie de l’information

Nous pouvons obtenir un résultat plus fort si nous étendons cet argument de comptage avec un peu de théorie de l’information. Voici comment nous pourrions utiliser un algorithme de tri comme un code de transmission de l’information :

1. Je pense à un nombre – disons, 15
2. Je cherche la permutation #15 dans la liste des permutations de quatre éléments
3. J’exécute l’algorithme de tri sur cette permutation et j’enregistre tous les résultats de comparaison « PLUS GRAND » et « PLUS PETIT »
4. Je vous transmets les résultats de comparaison en code binaire
5. Vous reconstituez l’exécution de mon algorithme de tri, étape par étape, en vous référant à ma liste de résultats de comparaison si nécessaire
6. Maintenant que vous savez comment j’ai réarrangé mon tableau pour le trier, vous pouvez inverser la permutation pour découvrir mon tableau d’origine
7. Vous recherchez mon tableau d’origine dans la liste de permutation pour découvrir que j’ai transmis le nombre 15

Ok, c’est un peu étrange, mais c’est faisable. Cela signifie que les algorithmes de tri sont liés par les mêmes lois que les schémas d’encodage normaux, y compris le théorème prouvant qu’il n’y a pas de compresseur de données universel. J’ai transmis un bit par comparaison effectuée par l’algorithme, donc, en moyenne, le nombre de comparaisons doit être au moins égal au nombre de bits nécessaires pour représenter mes données, selon la théorie de l’information. Plus techniquement, le nombre moyen de comparaisons doit être au moins égal à l’entropie de Shannon de mes données d’entrée, mesurée en bits. L’entropie est une mesure mathématique du contenu en information, ou de l’imprévisibilité, de quelque chose.

Si j’ai un tableau de NN éléments qui pourraient être dans n’importe quel ordre possible sans biais, alors l’entropie est maximisée et estlog2N!\log_2{N!} bits. Cela prouve que O(NlogN)O(N\log{N}) est une moyenne optimale pour un tri basé sur la comparaison avec une entrée arbitraire.

C’est la théorie, mais comment se comparent les algorithmes de tri réels ? Ci-dessous est un graphique du nombre moyen de comparaisonsnécessaires pour trier un tableau. J’ai comparé l’optimum théorique avec le tri rapide naïf et le tri par fusion-insertion de Ford-Johnson, qui a été conçu pour minimiser les comparaisons (bien qu’il soit rarement plus rapide que le tri rapide dans l’ensemble, car la vie ne se résume pas à minimiser les comparaisons). Depuis son développement en 1959, le tri par fusion-insertion a été modifié pour extraire quelques comparaisons supplémentaires, mais le graphique montre qu’il est déjà presque optimal.

C’est agréable quand un peu de théorie donne un résultat pratique aussi serré.

Résumé jusqu’ici

Voici ce qui a été prouvé jusqu’ici :

1. Si le tableau pouvait commencer dans n’importe quel ordre, au moins O(NlogN)O(N\log{N}) comparaisons sont nécessaires dans le pire des cas
2. Le nombre moyen de comparaisons doit être au moins l’entropie du tableau, ce qui est O(NlogN)O(N\log{N}) pour une entrée aléatoire

Notez que #2 permet aux algorithmes de tri basés sur les comparaisons d’être plus rapides que O(NlogN)O(N\log{N}) si l’entrée est de faible entropie (autrement dit, plus prévisible). Le tri par fusion est proche de O(N)O(N) si l’entrée contient de nombreux sous-réseaux triés. Le tri par insertion est proche de O(N)O(N) si l’entrée est un tableau qui a été trié avant d’être un peu perturbé. Aucun d’entre eux ne batO(NlogN)O(N\log{N}) dans le pire des cas, à moins que certains ordonnancements de tableaux soient impossibles en entrée.

Algorithmes de tri généraux

Les tris basés sur la comparaison sont un cas particulier intéressant en pratique, mais il n’y a rien de spécial en théorie à propos deCMP par rapport à toute autre instruction sur un ordinateur. Les deux arguments ci-dessus peuvent être généralisés à n’importe quel algorithme de tri si vous notez deux ou trois choses :

1. La plupart des instructions de l’ordinateur ont plus de deux sorties possibles, mais en ont toujours un nombre limité
2. Le nombre limité de sorties signifie qu’une instruction ne peut traiter qu’une quantité limitée d’entropie

Cela nous donne la même O(NlogN)O(N\log{N}) borne inférieure sur le nombre d’instructions. Tout ordinateur physiquement réalisable ne peut traiter qu’un nombre limité d’instructions à la fois, donc c’est une borne inférieure O(NlogN)O(N\log{N}) sur le temps requis, aussi.

Mais qu’en est-il des algorithmes « plus rapides » ?

L’implication pratique la plus utile de la borne générale O(NlogN)O(N\log{N}) est que si vous entendez parler d’un algorithme asymptotiquement plus rapide, vous savez qu’il doit « tricher » d’une manière ou d’une autre. Il doit y avoir une faille qui fait qu’il ne s’agit pas d’un algorithme de tri général qui s’adapte à des tableaux de taille arbitraire. Il pourrait encore être un algorithme utile, mais c’est une bonne idée de lire attentivement les petits caractères.

Un exemple bien connu est le tri radix. On l’appelle souvent un algorithme de tri O(N)O(N), mais le hic, c’est qu’il ne fonctionne que si tous les nombres tiennent dans kk bits, et qu’il est en réalité O(kN)O(kN).

Que cela signifie-t-il en pratique ? Supposons que vous ayez une machine de 8 bits. Vous pouvez représenter 28=2562^8 = 256 nombres différents sur 8 bits, donc si vous avez un tableau de milliers de nombres, vous allez avoir des doublons. Cela peut convenir à certaines applications, mais pour d’autres, vous devez passer à au moins 16 bits, qui peuvent représenter distinctement 216=65,5362^16 = 65 536 nombres. 32 bits permettent de représenter 232=4 294 967 2962^32 = 4 294 967 296 nombres différents. Plus la taille du tableau augmente, plus le nombre de bits nécessaires a tendance à augmenter également. Pour représenter distinctement NN nombres différents, vous aurez besoin de k≥log2Nk \geq \log_2{N}. Donc, à moins que vous soyez d’accord avec beaucoup de doublons dans votre tableau, O(kN)O(kN) est effectivement O(NlogN)O(N\log{N}).

Le besoin de O(NlogN)O(N\log{N}) de données d’entrée dans le cas général prouve en fait le résultat global par lui-même. Cet argument n’est pas si intéressant en pratique car nous avons rarement besoin de trier des milliards d’entiers sur une machine 32 bits, et si quelqu’un a atteint les limites d’une machine 64 bits, il ne l’a pas dit au reste d’entre nous.