Minimiser les comparaisons : Borne inférieure Ω(n log n)

Bonjour,

Dans la leçon précédente, nous avons exploré des algorithmes de tri en temps linéaire, comme le tri par comptage et le tri par base. Nous avons vu qu'ils parvenaient à "battre" la complexité en $Θ (n lo g n)$ en exploitant des hypothèses fortes sur la nature des données (des entiers dans une plage connue). Cela soulève une question fondamentale : cette complexité en $Θ (n lo g n)$ , observée pour des algorithmes comme le tri fusion ou le tri par tas, est-elle une limite infranchissable pour la classe générale des algorithmes de tri ?

La réponse est oui, à condition que l'algorithme se base uniquement sur la comparaison entre les éléments. C'est l'objectif de cette leçon, la dernière de notre module sur le tri : démontrer la borne inférieure $Ω (n lo g n)$ pour les tris par comparaison en utilisant le modèle de l'arbre de décision. Cette preuve est un pilier de l'algorithmique et sa maîtrise est indispensable au niveau de l'Agrégation.

Nous allons construire cette preuve rigoureuse en trois étapes :

Modéliser l'exécution de n'importe quel algorithme de tri par comparaison à l'aide d'un arbre de décision.
Établir une relation entre les propriétés de cet arbre (nombre de feuilles, hauteur) et le problème du tri.
Utiliser cette relation pour déduire mathématiquement une borne inférieure sur le nombre de comparaisons nécessaires dans le pire des cas.

1. Le modèle de l'arbre de décision

Un algorithme de tri par comparaison ne peut obtenir d'information sur l'ordre des éléments qu'en effectuant des comparaisons par paires (ex: T[i] <= T[j]). Chaque comparaison a deux issues possibles. La séquence de comparaisons effectuée par un algorithme dépend des résultats des comparaisons précédentes.

Cette structure de décisions séquentielles peut être parfaitement modélisée par un arbre binaire de décision.

Nœuds internes : Chaque nœud interne représente une comparaison entre deux éléments du tableau.
Branches (arêtes) : Les deux branches qui partent d'un nœud représentent les deux issues possibles de la comparaison (par ex., la branche gauche pour oui, la droite pour non).
Feuilles : Chaque feuille de l'arbre représente un résultat final, c'est-à-dire une permutation des éléments d'entrée qui est maintenant triée.
Chemin : Une exécution de l'algorithme sur une entrée donnée correspond à un unique chemin de la racine à une feuille. La longueur de ce chemin est le nombre de comparaisons effectuées.

Pour vous familiariser avec ce modèle, je vous propose d'étudier un document qui le définit formellement et l'illustre avec l'exemple du tri à bulles.

Algorithmique IV - Complexité des tris comparatifs [JP. Zanotti]

Ce document de J-P. Zanotti, destiné à des étudiants en informatique, introduit de manière très claire le concept d'arbre de décision appliqué aux tris comparatifs. Il est idéal pour poser les bases de notre raisonnement.

Lisez les sections "Arbre de décision" et l'exemple qui suit. Observez attentivement comment l'arbre de décision du tri à bulles pour n=3 est construit. Chaque chemin de la racine à une feuille (ex: 1,2,3 ou 3,2,1) correspond à une exécution spécifique de l'algorithme.

Ce qu'il faut retenir, c'est que tout algorithme de tri par comparaison peut être représenté par un arbre de décision. La structure de l'arbre est unique à chaque algorithme.

2. La borne inférieure : la démonstration formelle

Maintenant que le modèle est posé, nous pouvons l'utiliser pour borner la complexité. La démonstration repose sur deux arguments clés.

Argument 1 : Le nombre de feuilles
Pour un tableau de $n$ éléments distincts, combien y a-t-il d'ordres initiaux possibles ? Il y a $n!$ (factorielle de n) permutations possibles. Un algorithme de tri correct doit pouvoir trier chacune de ces $n!$ permutations. Chaque permutation initiale doit aboutir à une feuille de l'arbre de décision qui correspond à l'ordre trié final. Deux permutations initiales différentes ne peuvent pas aboutir à la même feuille, car cela signifierait que l'algorithme a effectué la même séquence d'opérations pour les deux, ce qui est impossible si les ordres initiaux étaient différents. Par conséquent, l'arbre de décision doit avoir au moins $n!$ feuilles.

Argument 2 : La hauteur de l'arbre
La complexité dans le pire des cas d'un algorithme est le nombre maximal de comparaisons qu'il effectue pour une entrée de taille $n$ . Dans notre modèle, cela correspond à la longueur du plus long chemin de la racine à une feuille. C'est, par définition, la hauteur $h$ de l'arbre de décision.

Nous avons donc deux relations :

Nombre de feuilles, $L \geq n!$
Dans un arbre binaire de hauteur $h$ , le nombre de feuilles est au plus $2^{h}$ . Donc, $L \leq 2^{h}$ .

En combinant ces deux points, nous obtenons l'inégalité fondamentale :

n! \leq L \leq 2^{h}

Ce qui nous donne directement :

n! \leq 2^{h}

Notre objectif est de trouver une borne inférieure pour $h$ . En appliquant le logarithme en base 2 des deux côtés :

lo g_{2} (n!) \leq lo g_{2} (2^{h})

lo g_{2} (n!) \leq h

La complexité dans le pire des cas, $h$ , est donc au moins $lo g_{2} (n!)$ . Il nous reste à évaluer $lo g_{2} (n!)$ . Pour cela, on utilise l'approximation de Stirling, un résultat classique d'analyse.

Le document suivant, issu de l'ENS Rennes, formalise admirablement cette démonstration.

[PDF] Minorant de complexité pour les tris par comparaison

Ce document synthétise la preuve de manière formelle et concise, au niveau attendu pour une préparation à l'Agrégation. Il utilise l'approximation de Stirling pour conclure la démonstration.

Lisez les "Étape 1", "Étape 2" et "Étape 3". Suivez attentivement le raisonnement qui mène de la définition de l'arbre à l'inégalité finale C(n) = Ω(n lg n). La notation 'lg' est ici utilisée pour log base 2.

Pour récapituler l'argument final utilisant l'approximation de Stirling :
$lo g_{2} (n!) = \sum_{i = 1}^{n} lo g_{2} (i)$
L'analyse de cette somme (par exemple en la minorant par une intégrale comme dans la ressource de J-P. Zanotti, ou en utilisant l'approximation de Stirling) montre que :
$lo g_{2} (n!) \sim n lo g_{2} n$
Donc, $h \geq lo g_{2} (n!)$ implique que $h$ est en $Ω (n lo g n)$ .

3. Une autre perspective visuelle

Pour consolider votre compréhension, la vidéo suivante présente la même démonstration avec une approche très visuelle. Bien qu'elle soit en anglais, les schémas et les équations sont universels et renforcent l'intuition derrière chaque étape.

Why is Comparison Sorting Ω(n*log(n))? | Asymptotic Bounding & Time Complexity

Cette vidéo de la chaîne Interview Pen décompose la preuve pas à pas, en commençant par un rappel sur les logarithmes, en construisant un arbre pour n=3, et en déroulant la même preuve mathématique que nous venons de voir, y compris l'usage de l'approximation de Stirling.

Regardez la vidéo de 02:44 à 16:36. Concentrez-vous sur les liens entre les concepts : l'arbre binaire, le nombre de permutations (n!), l'inégalité n! <= 2^h, et la dérivation finale utilisant les logarithmes. C'est une excellente révision visuelle de notre démonstration.

Conclusion

Aujourd'hui, nous avons achevé notre exploration des algorithmes de tri par une preuve fondamentale.

Points clés à retenir :

Modèle de l'arbre de décision : C'est un outil théorique puissant pour analyser n'importe quel algorithme de tri par comparaison. La hauteur de l'arbre représente la complexité dans le pire des cas.
Argument combinatoire : Un algorithme de tri doit pouvoir distinguer les $n!$ permutations possibles de son entrée, ce qui impose à son arbre de décision d'avoir au moins $n!$ feuilles.
La borne $Ω (n lo g n)$ : L'inégalité $n! \leq 2^{h}$ nous mène inévitablement à la conclusion que la hauteur $h$ doit être au moins de l'ordre de $n lo g n$ .
Optimalité : Cette preuve démontre que les algorithmes comme le tri fusion et le tri par tas sont asymptotiquement optimaux. Il est impossible de concevoir un algorithme de tri par comparaison qui soit significativement plus rapide dans le cas général.

Cette leçon conclut notre module sur les algorithmes de tri. Vous avez maintenant une vision complète du sujet, depuis l'implémentation d'algorithmes concrets jusqu'à la compréhension de leurs limites théoriques fondamentales.

Prochaine étape :
Dans le prochain module, nous aborderons une autre structure de données fondamentale en informatique : les arbres. Nous commencerons par les bases, en définissant formellement les arbres binaires et en explorant leurs différentes méthodes de parcours.

Recommended resources

1. Le modèle de l'arbre de décision

2. La borne inférieure : la démonstration formelle

3. Une autre perspective visuelle

Conclusion