“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 153 — #163
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
153
Un exemple : la fonction MergeSort
Nous avons vu un algorithme de tri par fusion (« mergesort »). Calculons le temps
d’exécution de cet algorithme. Voici la fonction principale :
fun {MergeSort Xs}
case Xs of nil then nil
[] [X] then [X]
else Ys Zs in
{Split Xs Ys Zs}
{Merge {MergeSort Ys} {MergeSort Zs}}
end
end
Soit T (n) le temps d’exécution de {MergeSort Xs}, où n est la longueur de
Xs. Supposons que Split et Merge sont O(n) dans la longueur de leurs entrées.
Nous savons que Split renvoie deux listes avec longueurs n/2 et n/2, Avec la
définition de MergeSort, cela nous permet de définir les équations de récurrence
suivantes :
T (0) = k 1
T (1) = k 2
T (n) = k 3 + k 4 n + T (n/2) + T (n/2) if n 2
Ces équations utilisent les fonctions plafond (« ceiling ») et plancher (« floor »), dont
la manipulation est un peu délicate. Pour nous en débarrasser, supposons que n est une
puissance de 2, donc n = 2
k pour un entier positif k. Les équations deviennent alors :
T (0) = k 1
T (1) = k 2
T (n) = k 3 + k 4 n + 2T (n/2) if n 2
L’expansion de la dernière équation donne (avec L(n) = k 3 + k 4 n) :
T (n) =
k
L(n) + 2L(n/2) + 4L(n/4) + · · · + (n/2)L(2) + 2T (1)
Le remplacement de L(n) et T (1) par leurs valeurs donne
T (n) =
k
(k 4 n + k 3 ) + (k 4 n + 2k 3 ) + (k 4 n + 4k 3 ) + · · · + (k 4 n + (n/2)k 3 ) + k 2
Simplifier la somme donne
T (n) = k 4 kn + (n − 1)k 3 + k 2
© Dunod – La photocopie non autorisée est un délit