“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 150 — #160
i
i
i
i
i
i
i
i
150
3
• Techniques de programmation déclarative
Avec le tableau 3.3, nous obtenons l’équation de récurrence suivante pour l’appel
récursif :
T Append (size(I ({Xs, Ys, Zs}))) =
k 1 + max(k 2 , k 3 + T Append (size(I ({Xr, Ys, Zr})))
(Les indices pour size et I ne sont pas nécessaires ici.) Pour simplifier, utilisons
I ({Xs, Ys, Zs}) = {Xs} et supposons que size({Xs}) = n, où n est la longueur de
Xs. Cela donne
T Append (n) = k 1 + max(k 2 , k 3 + T Append (n − 1))
Avec un peu de simplification :
T Append (n) = k 4 + T Append (n − 1)
Nous traitons le cas de base en prenant une valeur particulière de Xs pour laquelle
nous pouvons calculer le résultat directement. Prenons Xs=nil. Cela donne
T Append (0) = k 5
La solution des deux équations est
T Append (n) = k 4 · n + k 5
T Append (n) est donc O(n).
s : :=
skip
k
| |x 1 =x 2
k
| |x=v
k
| |s 1 s 2
T (s 1 ) + T (s 2 )
| local x in s end
k + T (s)
| proc {x y 1 · · · ·y n } s end k
| if x then s 1 else s 2 end k + max(T (s 1 ), T (s 2 ))
| case x of pattern
k + max(T (s 1 ), T (s 2 ))
then s 1 else s 2 end
| {x y 1 · · · ·y n }
T x (size x (I x ({y 1 , . . . , y n })))
Tableau 3.3 Les temps d’exécution des instructions noyau.