4.6 Exercices et problèmes
177
proposition 4.13, et en affinant les évaluations asymptotiques des sommes S 1 et S 2 jusqu’à obtenir
un terme d’erreur o(1) qui, en en prenant l’exponentielle, donnera bien un terme d’erreur en o(1)
sur t n . On rappelle que L = =log 2 n, et on reprend les notations de la Section 4.3 :
S 1 =
L
k=2
u k ν k ;
S 2 =
p
log s p .
1. Nous avons vu que
S 1 =
L
k=2
log(2
k − 1).
n
2 k − 1 −
n
2 k−1
+
n
2 k
.
La somme des deux premiers termes
L
k=2 log(2 k − 1).
n
2 k − 1
peut être isolée ; calculer sa
valeur.
2. Dans les deux termes restants, réarranger les termes de façon à faire apparaître la somme
k
n
2 k−1
log
2 k − 1
2 k−1 − 1
,
puis évaluer cette somme.
3. Pour étudier la somme S 2 =
p log s p , correspondant à la contribution des nœuds spéciaux,
poser
s p = 2
L−p
⎛
⎝ 1 +
0≤j b j
2 j
2 L+p
⎞
⎠ ,
où les b j sont les chiffres de la décomposition binaire de n. En isolant le facteur 2 L−p , calculer
la valeur de
p log 2 L−p . Enfin évaluer le terme
p
log
⎛
⎝ 1 +
0≤j b j
2 j
2 L+p
⎞
⎠ .
4. Conclure.
(On pourra se reporter à l’article de Hwang et Steyaert [138] d’où est tiré ce calcul.)
Problème 4.18. (Nombre d’échanges faits par l’algorithme de Floyd) Nous nous intéressons ici au nombre moyen d’échanges lors de la construction d’un tas par l’algorithme de
Floyd. Soit ξ(τ ) le nombre d’échanges faits sur un arbre parfait τ pour obtenir un tas, et soit
x n = E[ξ(τ ) : |τ | = n] ; soit aussi L = =log 2 n
1. Montrer que x n satisfait la relation de récurrence
x 2 L +j =
t 2 L +j + x 2 L−1 −1 + x 2 L−1 +j (0 ≤ j ≤ 2 L−1 − 1);
t 2 L +j + x 2 L −1 + x L
(2 L−1 ≤ j ≤ 2 L − 1).
avec t n =
1
n
n
i=1 log 2 i