156
4 Approche combinatoire
toutes les permutations d’entrée sont équiprobables, vaut asymptotiquement lorsque
n → +∞
E[ξ ] = c 1 n − −log 2 n − V (n) + ω 1 (n) + O(1),
où la fonction V (n) est définie dans la proposition 4.15, où
c 1 = −2 +
j ≥1
j
2 j − 1
= 0,744033 . . .
et où
ω 1 (n) =
L
j =0
{n/2 j }
1 + {n/2 j }
est d’ordre O(log n) lorsque n → +∞.
Ce résultat s’obtient par les mêmes techniques que celles employées pour
énumérer les tas ; quelques indications sur sa démonstration se trouvent dans le
problème 4.18.
Il est possible d’obtenir la variance du nombre d’échanges, et la
convergence de ce nombre vers une loi limite gaussienne ; nous renvoyons à
Hwang et Steyaert [138] pour les détails.
Il y a en fait deux mesures de performances naturelles sur les tas :
le nombre ξ d’échanges et le nombre η de comparaisons. Le nombre de
comparaisons se comporte comme le nombre d’échanges ; le lecteur curieux
pourra se reporter à l’article de Doberkat [65], dont nous tirons
E[η] = 1,881372624 . . . n + O(log
2 n).
Les tas, utilisés comme files de priorité, permettent d’obtenir la plus
petite clé d’un ensemble : cette clé se trouve à la racine. Dans la plupart des
cas, cette plus petite clé va être ôtée du tas, qu’il faut alors reconstruire ; se
pose alors la question du coût de l’algorithme de suppression du minimum
et reconstruction du tas ; un tel algorithme est donné en section A.6.3.
Supposons toujours que tous les tas de taille n suivent une loi uniforme.
La proposition suivante est due à Doberkat [64], qui étudie les nombres
d’échanges et de comparaisons pour reconstruire un tas après suppression du
minimum, dans le cas particulier où la taille initiale est une puissance de 2.
(tsvp)