Ceci est une traduction automatique ; le texte anglais constitue la version originale. Lire l'original
Pourquoi le tri ne peut pas devenir plus rapide
Trier cent objets nécessite au moins 525 comparaisons. Pas seulement avec les algorithmes d'aujourd'hui. Jamais.
La plupart des affirmations concernant les performances portent sur un programme particulier. Celle-ci fait exception. Elle énonce qu'aucun algorithme de tri par comparaison, écrit par quiconque, dans n'importe quel langage, sur n'importe quel matériel qui n'a pas encore été inventé, ne peut trier cent éléments en moins de 525 comparaisons.
Le raisonnement ne s'intéresse à aucun algorithme.
Comptez les destinations, pas les étapes
Une liste de n éléments distincts peut être ordonnée de n! manières différentes. Une seule d'entre elles est triée, et avant de commencer, vous n'avez aucune idée de celle que vous avez en main.
Considérez maintenant ce qu'une comparaison vous apporte. Vous demandez si a se trouve avant b et vous obtenez oui ou non. Un bit. Quoi que fasse ensuite votre algorithme, il le fait en connaissant une information binaire de plus qu'auparavant.
Ainsi, après c comparaisons, vous avez reçu c bits, et c bits peuvent distinguer au maximum 2c situations différentes. Pour être certain d'identifier avec laquelle des n! dispositions vous avez commencé, il vous faut
2c ≥ n!, c'est-à-dire c ≥ log₂(n!).
C'est l'intégralité de la démonstration. Elle ne contient aucune boucle, aucune récursion et aucune hypothèse sur la stratégie, ce qui est précisément la raison pour laquelle elle s'applique à des algorithmes auxquels personne n'a encore pensé.
Le nom habituel pour désigner cela est la borne de l'arbre de décision. Représentez-vous n'importe quel tri par comparaison sous la forme d'un arbre : chaque nœud interne est une comparaison, chaque branche correspond à l'une des deux réponses, et chaque feuille est une disposition possible. Un arbre de profondeur c possède au plus 2c feuilles, et l'arbre doit en compter au moins n!, sa profondeur est donc d'au moins log₂(n!). La profondeur correspond au nombre de comparaisons dans le pire des cas.
Ce que disent concrètement les chiffres
Douze éléments peuvent être disposés de 479,001,600 façons. Le logarithme de ce nombre est de 28,84, donc douze éléments nécessitent au moins 29 comparaisons. Cent éléments en nécessitent au moins 525. Un million en nécessite au moins 18,488,885.
Ouvrez le Big-O Complexity Explorer et lisez la ligne pour N = 100. La colonne O(N log N) indique 664, ce qui se situe entre O(N) à 100 et O(N²) à 10,000. Ce 664 correspond à N × log₂N, le taux de croissance que nous qualifions d'optimal pour le tri.
Mais le seuil minimal est de 525, et 664 est situé 26,6% au-dessus.
Cet écart n'est pas dû à un manque de rigueur de l'outil. log₂(n!) n'est pas tout à fait n log₂ n : l'approximation de Stirling donne n log₂ n − 1,4427n, et pour N = 100 cette correction vaut 139 comparaisons. Ainsi, « N log N » désigne la bonne allure tout en surestimant le coût réel d'un facteur constant lié à la taille de l'entrée. L'allure est ce qui subsiste à mesure que N grandit ; les 139 comparaisons sont ce que vous remarqueriez si vous comptiez réellement.
L'échappatoire qui n'est pas une faille
Le tri par comptage triera un million de petits entiers en bien moins de 18 millions d'opérations, et ne contredit pas un seul mot de ce qui précède.
La démonstration suppose que chaque question posée est une comparaison. Le tri par comptage pose une question d'une autre nature : il lit une clé et l'utilise comme adresse. Cela extrait bien plus d'un bit à la fois, car il exploite une propriété que le modèle par comparaison refuse de poser en hypothèse, à savoir que les clés sont de petits entiers dont on est autorisé à examiner l'intérieur.
Voilà l'habitude utile à prendre. Une borne inférieure est toujours une borne inférieure au sein d'un modèle, et lorsqu'un résultat semble être battu, c'est que le modèle a été modifié. Sorting Race fait s'affronter les algorithmes de tri par comparaison les uns contre les autres, et ce qui les sépare relève des facteurs constants et du comportement en mémoire, pas de l'exposant. Ils sont tous bornés inférieurement par ce même 525.
Où vous avez déjà rencontré cela
Si la démarche du dénombrement vous semble familière, c'est celle qui explique pourquoi aucun compresseur ne peut réduire tous les fichiers. Dans cet autre cas, on comptait les fichiers possibles par rapport aux fichiers plus courts possibles ; ici, on compte les agencements possibles par rapport aux séquences de réponses possibles. Les deux démonstrations fonctionnent en constatant qu'un ensemble d'issues est plus grand que l'ensemble des éléments qui pourraient les décrire.
Entropy Coding représente la même quantité sous un autre angle : le nombre de bits dont vous avez réellement besoin est déterminé par le nombre de possibilités restantes, et aucun codage ne fait mieux.
Aucun de ces deux résultats ne vous indique comment écrire un programme rapide. Ils vous indiquent quand cesser d'en chercher un.