4.3 Tas
155
Fig. 4.10 La fonction V (n), égale au nombre de 1 dans la représentation binaire de n, et
normalisée en divisant par log 2 (n)
Fig. 4.11 La fonction ω(n), normalisée en divisant par log 2 (n)
Fig. 4.12 Les valeurs de P (log 2 (n)), normalisées en divisant par log 2 (n)
4.3.3 Complexité des opérations sur un tas
Nous nous intéressons prioritairement ici à l’algorithme de Floyd, qui construit un
tas en connaissant dès le départ toutes les clés, et nous choisissons comme mesure
de sa performance le nombre d’échanges de clés ξ(τ ) nécessaires pour obtenir un tas
à partir d’un arbre parfait τ . Le modèle aléatoire retenu pour analyser cet algorithme
suppose une loi uniforme sur S n , n étant le nombre de clés.
Proposition 4.16 Le nombre moyen d’échanges effectués lors de la construction
d’un tas par l’algorithme de Floyd appliqué à un arbre parfait de taille n, lorsque
155
Fig. 4.10 La fonction V (n), égale au nombre de 1 dans la représentation binaire de n, et
normalisée en divisant par log 2 (n)
Fig. 4.11 La fonction ω(n), normalisée en divisant par log 2 (n)
Fig. 4.12 Les valeurs de P (log 2 (n)), normalisées en divisant par log 2 (n)
4.3.3 Complexité des opérations sur un tas
Nous nous intéressons prioritairement ici à l’algorithme de Floyd, qui construit un
tas en connaissant dès le départ toutes les clés, et nous choisissons comme mesure
de sa performance le nombre d’échanges de clés ξ(τ ) nécessaires pour obtenir un tas
à partir d’un arbre parfait τ . Le modèle aléatoire retenu pour analyser cet algorithme
suppose une loi uniforme sur S n , n étant le nombre de clés.
Proposition 4.16 Le nombre moyen d’échanges effectués lors de la construction
d’un tas par l’algorithme de Floyd appliqué à un arbre parfait de taille n, lorsque