“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 151 — #161
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
151
Les équations de récurrence
Avant de regarder d’autres exemples, examinons de plus près les équations de récurrence. Une équation de récurrence a l’une des deux formes suivantes :
– Une équation qui définit une fonction T (n) en termes de T (m 1 ), . . . , T (m k ), où
m 1 , . . . , m k < n.
– Une équation qui donne la valeur de T (n) pour certaines valeurs de n, comme
T (0) or T (1).
Dans les calculs des temps d’exécution, il y a certaines formes d’équations de récurrence qui apparaissent souvent. Le tableau 3.4 montre certaines de ces équations et
leurs solutions. Le tableau suppose que les k i sont des constantes non nulles. Il y a
beaucoup de techniques pour calculer ces solutions. Nous en verrons quelques-unes
dans les exemples à venir. La boîte explique deux des plus utiles.
Équation
Solution
T (n) = k + T (n − 1)
O(n)
T (n) = k 1 + k 2 .n + T (n − 1) O(n
2 )
T (n) = k + T (n/2)
O(log n)
T (n) = k 1 + k 2 .n + T (n/2)
O(n)
T (n) = k + 2.T (n/2)
O(n)
T (n) = k 1 + k 2 .n + 2.T (n/2) O(n log n)
T (n) = k 1 .n
k 2 + k 3 .T (n − 1) O(k 3
n ) (si k 3 > 1)
Tableau 3.4 Quelques équations de récurrence courantes et leurs solutions.
La résolution d’équations de récurrence
Les techniques suivantes sont souvent utiles :
– Une technique simple qui fonctionne presque toujours en pratique. D’abord,
obtenez des nombres exacts pour quelques petites entrées (par exemple :
T (0) = k, T (1) = k + 3, T (2) = k + 6). Ensuite, devinez la forme du
résultat (par exemple : T (n) = an + b, pour des valeurs inconnues de a et
b). Enfin, substituez cette forme dans les équations. Dans notre exemple, cela
donne b = k et (an + b) = 3 + (a · (n − 1) + b). Donc a = 3, ce qui donne le
résultat final T (n) = 3n + k. Cette technique fonctionnera si la forme devinée
est correcte.
– Une technique bien plus puissante, les fonctions génératrices, permet souvent
d’obtenir une formule exacte ou asymptotique sans la nécessité de deviner la
forme. Elle nécessite certaines connaissances des séries infinies et de l’analyse,
mais pas plus que dans un premier cours universitaire. Voir Knuth [50] et
Wilf [98] pour de bonnes introductions aux fonctions génératrices.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
151
Les équations de récurrence
Avant de regarder d’autres exemples, examinons de plus près les équations de récurrence. Une équation de récurrence a l’une des deux formes suivantes :
– Une équation qui définit une fonction T (n) en termes de T (m 1 ), . . . , T (m k ), où
m 1 , . . . , m k < n.
– Une équation qui donne la valeur de T (n) pour certaines valeurs de n, comme
T (0) or T (1).
Dans les calculs des temps d’exécution, il y a certaines formes d’équations de récurrence qui apparaissent souvent. Le tableau 3.4 montre certaines de ces équations et
leurs solutions. Le tableau suppose que les k i sont des constantes non nulles. Il y a
beaucoup de techniques pour calculer ces solutions. Nous en verrons quelques-unes
dans les exemples à venir. La boîte explique deux des plus utiles.
Équation
Solution
T (n) = k + T (n − 1)
O(n)
T (n) = k 1 + k 2 .n + T (n − 1) O(n
2 )
T (n) = k + T (n/2)
O(log n)
T (n) = k 1 + k 2 .n + T (n/2)
O(n)
T (n) = k + 2.T (n/2)
O(n)
T (n) = k 1 + k 2 .n + 2.T (n/2) O(n log n)
T (n) = k 1 .n
k 2 + k 3 .T (n − 1) O(k 3
n ) (si k 3 > 1)
Tableau 3.4 Quelques équations de récurrence courantes et leurs solutions.
La résolution d’équations de récurrence
Les techniques suivantes sont souvent utiles :
– Une technique simple qui fonctionne presque toujours en pratique. D’abord,
obtenez des nombres exacts pour quelques petites entrées (par exemple :
T (0) = k, T (1) = k + 3, T (2) = k + 6). Ensuite, devinez la forme du
résultat (par exemple : T (n) = an + b, pour des valeurs inconnues de a et
b). Enfin, substituez cette forme dans les équations. Dans notre exemple, cela
donne b = k et (an + b) = 3 + (a · (n − 1) + b). Donc a = 3, ce qui donne le
résultat final T (n) = 3n + k. Cette technique fonctionnera si la forme devinée
est correcte.
– Une technique bien plus puissante, les fonctions génératrices, permet souvent
d’obtenir une formule exacte ou asymptotique sans la nécessité de deviner la
forme. Elle nécessite certaines connaissances des séries infinies et de l’analyse,
mais pas plus que dans un premier cours universitaire. Voir Knuth [50] et
Wilf [98] pour de bonnes introductions aux fonctions génératrices.
© Dunod – La photocopie non autorisée est un délit