“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 152 — #162
i
i
i
i
i
i
i
i
152
3
• Techniques de programmation déclarative
Un exemple : la fonction FastPascal
Dans le chapitre 1, nous avons défini la fonction FastPascal et nous avons prétendu
que {FastPascal N} est O(n
2 ). Nous faisons maintenant une dérivation plus
rigoureuse. Voici la définition :
fun {FastPascal N}
if N==1 then [1] else L in
L={FastPascal N-1}
{AddList {ShiftLeft L} {ShiftRight L}} end
end
Nous pouvons obtenir les équations directement à partir de cette définition, sans
traduire les fonctions en procédures. En inspectant la définition, il est facile de voir
que ShiftRight est O(1), un temps constant. Avec un raisonnement semblable que
pour Append, nous calculons que AddList et ShiftLeft sont O(n) où n est la
longueur de la liste L. Cela nous donne l’équation de récurrence suivante pour l’appel
récursif :
T FastPascal (n) = k 1 + max(k 2 , k 3 + T FastPascal (n − 1) + k 4 · n)
où n est la valeur de l’argument N. Avec un peu de simplification, nous obtenons
T FastPascal (n) = k 5 + k 4 · n + T FastPascal (n − 1)
Dans le cas de base, nous choisissons N=1. Cela donne
T FastPascal (1) = k 6
Pour résoudre ces deux équations, nous « devinons » que la solution est de la forme :
T FastPascal (n) = a · n
2 + b · n + c
Cette estimation vient d’un argument intuitif comme celui du chapitre 1. Nous insérons
cette forme dans les deux équations. Si nous trouvons des solutions pour a, b et c,
nous pourrons conclure que notre supposition était correcte. Nous obtenons les trois
équations en a, b et c :
k 4 − 2a = 0
k 5 + a − b = 0
a + b + c − k 6 = 0
Il n’est pas nécessaire de résoudre ce système complètement ; il suffit de vérifier que
a = 0.
9 Donc T FastPascal (n) est O(n
2 ).
9. Si nous devinons a · n
2 + b · n + c et la vraie solution a la forme b · n + c, nous aurons a = 0.