82
3 Arbres, algorithmes et données
A pour trier un tableau T de n clés, que nous supposons toutes distinctes, et
dénotons le nombre minimal de comparaisons faites par l’algorithme A, sur tous
les tableaux T de taille n possibles, par Y n (A) = inf
|T |=n
{Z n (T , A)}. Alors, sous le
modèle des permutations uniformes sur les tableaux,
lim inf
n→+∞
E[Y n (A)]
n log 2 n
≥ 1.
En d’autres termes, tout tri par comparaison fait en moyenne un nombre de
comparaisons au moins égal asymptotiquement à n log 2 n, et le tri rapide atteint cet
ordre de grandeur optimal, cependant avec une constante multiplicative de valeur
2 log 2 ∼ 1,386.
La démonstration de la proposition 3.9 fait appel à la notion d’arbre de décision
relatif à un algorithme, notion que nous introduisons ci-dessous. Nous verrons
comment il est possible de « lire » les différents coûts d’un algorithme sur l’arbre
de décision qui lui est associé ; pour obtenir la proposition 3.9 nous aurons aussi
besoin d’un résultat (proposition 3.13) sur la longueur de cheminement minimale
d’un arbre binaire.
Arbres de décision
Nous donnons ci-après une définition de l’arbre de décision associé à un algorithme
A travaillant sur un tableau dont nous supposons tous les éléments distincts, et
procédant par comparaisons de clés. 14 Cette définition peut bien sûr être facilement
étendue au cas où le résultat d’une comparaison n’est pas binaire (clés pouvant être
égales), voire à d’autres opérations que les comparaisons de clés, du moins lorsque
ces opérations ne peuvent avoir pour résultat qu’un nombre fini de valeurs. Nous
commençons par définir une relation d’équivalence R A entre tableaux.
Définition 3.10 Soit A un algorithme sur un tableau T , procédant par comparaisons sur les clés qu’il contient et effectuant un réordonnement de T . Deux tableaux
T 1 et T 2 de même taille n sont équivalents pour la relation R A , si et seulement
si l’algorithme fait exactement les mêmes comparaisons entre éléments du tableau,
lors de son exécution sur chacun des deux tableaux, et le résultat donne le même
réordonnement du tableau initial.
Définition 3.11 L’arbre de décision τ (n, A) associé à un algorithme A, travaillant
sur un tableau de taille donnée n et procédant par comparaisons de clés, est l’arbre
binaire représentant toutes les exécutions possibles de A sur n clés distinctes x i ,
1 ≤ i ≤ n, construit comme suit.
14 Nous rappelons que, dans cette section, les clés appartiennent à un ensemble totalement ordonné.
3 Arbres, algorithmes et données
A pour trier un tableau T de n clés, que nous supposons toutes distinctes, et
dénotons le nombre minimal de comparaisons faites par l’algorithme A, sur tous
les tableaux T de taille n possibles, par Y n (A) = inf
|T |=n
{Z n (T , A)}. Alors, sous le
modèle des permutations uniformes sur les tableaux,
lim inf
n→+∞
E[Y n (A)]
n log 2 n
≥ 1.
En d’autres termes, tout tri par comparaison fait en moyenne un nombre de
comparaisons au moins égal asymptotiquement à n log 2 n, et le tri rapide atteint cet
ordre de grandeur optimal, cependant avec une constante multiplicative de valeur
2 log 2 ∼ 1,386.
La démonstration de la proposition 3.9 fait appel à la notion d’arbre de décision
relatif à un algorithme, notion que nous introduisons ci-dessous. Nous verrons
comment il est possible de « lire » les différents coûts d’un algorithme sur l’arbre
de décision qui lui est associé ; pour obtenir la proposition 3.9 nous aurons aussi
besoin d’un résultat (proposition 3.13) sur la longueur de cheminement minimale
d’un arbre binaire.
Arbres de décision
Nous donnons ci-après une définition de l’arbre de décision associé à un algorithme
A travaillant sur un tableau dont nous supposons tous les éléments distincts, et
procédant par comparaisons de clés. 14 Cette définition peut bien sûr être facilement
étendue au cas où le résultat d’une comparaison n’est pas binaire (clés pouvant être
égales), voire à d’autres opérations que les comparaisons de clés, du moins lorsque
ces opérations ne peuvent avoir pour résultat qu’un nombre fini de valeurs. Nous
commençons par définir une relation d’équivalence R A entre tableaux.
Définition 3.10 Soit A un algorithme sur un tableau T , procédant par comparaisons sur les clés qu’il contient et effectuant un réordonnement de T . Deux tableaux
T 1 et T 2 de même taille n sont équivalents pour la relation R A , si et seulement
si l’algorithme fait exactement les mêmes comparaisons entre éléments du tableau,
lors de son exécution sur chacun des deux tableaux, et le résultat donne le même
réordonnement du tableau initial.
Définition 3.11 L’arbre de décision τ (n, A) associé à un algorithme A, travaillant
sur un tableau de taille donnée n et procédant par comparaisons de clés, est l’arbre
binaire représentant toutes les exécutions possibles de A sur n clés distinctes x i ,
1 ≤ i ≤ n, construit comme suit.
14 Nous rappelons que, dans cette section, les clés appartiennent à un ensemble totalement ordonné.