7.1 Analyses exactes
297
est donnée par la série entière
v(z) =
j ≥0
2
j
γ (
z
2 j ) e
z(1−
1
2 j ) .
Preuve Nous vérifions que les conditions du lemme d’itération 7.12 sont bien
vérifiées (avec r = 2). En effet γ (z) = O(z 2 ) puisque γ (ω) = 0 si |ω| ≤ 1. La
fonction α(z) vaut 2e z/2 . La solution v(z) doit vérifier v(0) = v (0) = 0 puisque,
comme pour γ , la quantité v(ω) vaut 0 si |ω| ≤ 1.
Taille d’un trie Pour ce paramètre additif, l’expression du péage déduite d’après
l’équation (7.2), γ (ω) = 1 {|ω|≥2} , donne lieu à la série génératrice
γ (z) = e
z
− 1 − z.
En appliquant le lemme 7.13, nous obtenons
S(z) =
k≥0
2
k
e
z
− e
z(1−
1
2 k ) −
z k
2 k e
z(1−
1
2 k )
.
L’extraction du coefficient en z n donne la valeur moyenne de la taille (le nombre de
nœuds internes) dans ce modèle pour un trie contenant n mots :
E n [S] = n![z
n
] S(z) =
k≥0
2
k
1 −
1 −
1
2 k
n
−
n
2 k
1 −
1
2 k
n−1
.
L’expression est exacte mais il est difficile d’en mesurer l’ordre de grandeur.
L’analyse asymptotique peut être menée par des moyens élémentaires (cf. section 7.2.1) ou plus sophistiqués (cf. section 7.2.3).
Remarque 7.14 Grâce à la remarque 7.11, nous pouvons tracer la courbe de
l’espérance de la taille, et dès à présent mettre en évidence des phénomènes
oscillatoires intrigants. Sur la figure 7.4, nous avons tracé la taille du trie divisée
par le nombre n de mots. Nous prouverons lors de l’étude asymptotique que la taille
d’un trie est bien en O(n). Comme le suggère la figure, des phénomènes oscillatoires
entrent en jeu, qui sont dus à un terme oscillant de très faible amplitude dans le terme
dominant de l’espérance de la taille.
Longueur de cheminement externe d’un trie Pour ce paramètre additif et d’après
l’équation (7.3), la fonction péage s’écrit γ (ω) = |ω| − 1 {|ω|=1} , ce qui se traduit
par
γ (z) = ze
z
− z.
297
est donnée par la série entière
v(z) =
j ≥0
2
j
γ (
z
2 j ) e
z(1−
1
2 j ) .
Preuve Nous vérifions que les conditions du lemme d’itération 7.12 sont bien
vérifiées (avec r = 2). En effet γ (z) = O(z 2 ) puisque γ (ω) = 0 si |ω| ≤ 1. La
fonction α(z) vaut 2e z/2 . La solution v(z) doit vérifier v(0) = v (0) = 0 puisque,
comme pour γ , la quantité v(ω) vaut 0 si |ω| ≤ 1.
Taille d’un trie Pour ce paramètre additif, l’expression du péage déduite d’après
l’équation (7.2), γ (ω) = 1 {|ω|≥2} , donne lieu à la série génératrice
γ (z) = e
z
− 1 − z.
En appliquant le lemme 7.13, nous obtenons
S(z) =
k≥0
2
k
e
z
− e
z(1−
1
2 k ) −
z k
2 k e
z(1−
1
2 k )
.
L’extraction du coefficient en z n donne la valeur moyenne de la taille (le nombre de
nœuds internes) dans ce modèle pour un trie contenant n mots :
E n [S] = n![z
n
] S(z) =
k≥0
2
k
1 −
1 −
1
2 k
n
−
n
2 k
1 −
1
2 k
n−1
.
L’expression est exacte mais il est difficile d’en mesurer l’ordre de grandeur.
L’analyse asymptotique peut être menée par des moyens élémentaires (cf. section 7.2.1) ou plus sophistiqués (cf. section 7.2.3).
Remarque 7.14 Grâce à la remarque 7.11, nous pouvons tracer la courbe de
l’espérance de la taille, et dès à présent mettre en évidence des phénomènes
oscillatoires intrigants. Sur la figure 7.4, nous avons tracé la taille du trie divisée
par le nombre n de mots. Nous prouverons lors de l’étude asymptotique que la taille
d’un trie est bien en O(n). Comme le suggère la figure, des phénomènes oscillatoires
entrent en jeu, qui sont dus à un terme oscillant de très faible amplitude dans le terme
dominant de l’espérance de la taille.
Longueur de cheminement externe d’un trie Pour ce paramètre additif et d’après
l’équation (7.3), la fonction péage s’écrit γ (ω) = |ω| − 1 {|ω|=1} , ce qui se traduit
par
γ (z) = ze
z
− z.