Probleme – L'arbre de décision, et pourquoi aucun tri ne fera mieux que $n lo g n$

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 10 — Arbres

Énoncé

Un algorithme qui trie en ne faisant que des comparaisons se représente par un arbre binaire : chaque nœud interne est une comparaison, chaque feuille une permutation rendue.

Montrer qu'un arbre binaire non vide de hauteur $h$ a au plus $2^{h}$ feuilles.
Combien de feuilles l'arbre de décision d'un tri de $n$ éléments doit-il avoir ?
En déduire une borne inférieure sur le nombre de comparaisons dans le pire cas.
Calculer cette borne pour $n = 5$ et $n = 12$ , et la comparer au tri fusion.

Corrigé

1. Au plus $2^{h}$ feuilles. <details class="group my-6 border border-gray-300 rounded-2xl bg-black/[0.03] overflow-hidden transition-all duration-300"><summary style="color:#1e3a8a" class="flex items-center justify-between p-4 cursor-pointer text-xs font-bold select-none"><div class="flex items-center"><i class="fa-solid fa-graduation-cap mr-2"></i>Démonstration</div><span class="transition-transform group-open:rotate-180"><i class="fa-solid fa-chevron-down"></i></span></summary><div style="color:#1d4ed8" class="force-blue p-4 pt-0 border-t border-gray-200 bg-black/[0.02] leading-relaxed font-sans text-xs select-text"> Par induction structurelle sur l'arbre non vide $a$ , en notant $f (a)$ son nombre de feuilles.

Cas $a = N œ ud (Vide, e, Vide)$ — une feuille, $h = 0$ : $f (a) = 1 = 2^{0}$ .

Cas $a = N œ ud (g, e, d)$ avec au moins un fils non vide. Si les deux le sont, $f (a) = f (g) + f (d) \leq 2^{h_{g}} + 2^{h_{d}} \leq 2 \cdot 2^{h - 1} = 2^{h}$ , puisque $h_{g}, h_{d} \leq h - 1$ . Si un seul l'est, disons $g$ , alors $f (a) = f (g) \leq 2^{h_{g}} = 2^{h - 1} \leq 2^{h}$ .

Autrement dit, $h \geq lo g_{2} f (a)$ : un arbre à beaucoup de feuilles est nécessairement haut, et c'est tout ce dont on a besoin.

2. Il faut au moins $n!$ feuilles. L'algorithme reçoit $n$ éléments dans un ordre inconnu et doit rendre l'une des $n!$ permutations possibles. Deux entrées demandant des permutations différentes ne peuvent pas aboutir à la même feuille : la feuille détermine entièrement ce que l'algorithme rend. Chacune des $n!$ permutations doit donc être atteinte par au moins une feuille, d'où $f \geq n!$ .

3. La borne inférieure. La hauteur de l'arbre de décision est le nombre de comparaisons dans le pire cas — c'est la plus longue branche. Les deux questions précédentes donnent

$h \geq lo g_{2} f \geq lo g_{2} (n!) .$

Et par la formule de Stirling, $lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + O (lo g n)$ , donc

$h = Ω (n lo g n) .$

Aucun algorithme de tri par comparaisons ne peut faire mieux, quelle que soit son ingéniosité. Le tri fusion, en $Θ (n lo g n)$ , est donc optimal à une constante près — et c'est ce théorème qui le dit.

4. Les chiffres, calculés.

$n$	$n!$	$lo g_{2} (n!)$	borne $⌈ lo g_{2} (n!)⌉$	tri fusion, pire cas
$5$	$120$	$6, 907$	$7$	$8$
$8$	$40320$	$15, 299$	$16$	$17$
$10$	$3628800$	$21, 791$	$22$	$25$
$12$	$479001600$	$28, 835$	$29$	$33$

Pour $n = 5$ : sept comparaisons au minimum, et le tri fusion en fait huit. Un algorithme atteignant sept existe — celui de Ford et Johnson — ce qui montre que la borne est atteinte pour cette valeur.

Pour $n = 12$ , la borne est $29$ et le tri fusion en fait $33$ . L'écart reste petit, et il est logarithmique en $n$ , jamais d'un ordre de grandeur.

Trois mises en garde, et elles sont le vrai contenu du problème.

Un. La borne ne dit rien des tris qui ne comparent pas. Un tri par comptage ou par base ne fait aucune comparaison : il indexe. Il trie $n$ entiers de ${0, \dots, k}$ en $Θ (n + k)$ , donc en temps linéaire quand $k = O (n)$ . Il ne contredit pas le théorème : il sort de ses hypothèses. Repérer l'hypothèse qu'un algorithme viole est le réflexe à acquérir devant toute borne inférieure.

Deux. La borne porte sur le pire cas. Un algorithme peut faire moins de comparaisons sur des entrées favorables : le tri par insertion en fait $n - 1$ sur une liste déjà triée (chapitre chap:induction). L'arbre de décision a alors une branche courte — il n'a pas moins de feuilles pour autant.

Trois. C'est un résultat sur les arbres, pas sur les tris. Le raisonnement se transporte tel quel : toute procédure qui doit distinguer $m$ cas en posant des questions binaires demande $⌈ lo g_{2} m ⌉$ questions dans le pire cas. Recherche dichotomique, pesées de pièces, jeu des vingt questions — la même inégalité $h \geq lo g_{2} f$ , et la seule chose qui change est le compte des feuilles.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.

Probleme – L'arbre de décision, et pourquoi aucun tri ne fera mieux que nlogn

Énoncé

Corrigé

Probleme – L'arbre de décision, et pourquoi aucun tri ne fera mieux que $n lo g n$