Page 18 - REVISTA MATINF Nr. 5

18 C. B˘alc˘au

Metoda 1) Vom estima efectiv timpul de execut , ie T(n). Vom num˘ara numai operat , iile de
comparat , ie de chei (comparat , ii ˆın care intervin elemente ale vectorului) s , i de deplas˘ari
(atribuiri ˆın care intervin elemente ale vectorului). Celelalte operat , ii care se efectueaz˘a au acelas , i
ordin de cres , tere cu cele pe care le analiz˘am. Avem

T(n) = c 1 · N c (n) + c 2 · N d (n), (1)

unde N c (n) s , i N d (n) reprezint˘a num˘arul de comparat ,ii de chei, respectiv num˘arul de deplas˘ari
efectuate de algoritm, iar c 1 , c 2 > 0 sunt constante ce reprezint˘a costurile ˆın timp ale execut˘arii
unei comparat ,ii de chei s , i, respectiv, ale unei deplas˘ari.

Conform descrierii recursive a algoritmului, rezult˘a c˘a numerele N c (n) s , i N d (n) verific˘a,
respectiv, relat , iile de recurent , ˘a

(
0, dac˘a n = 1,
n
n
n
n
N c (n) = l m j k l m j k (2)
N c + N c + N c , , dac˘a n > 1,
2 2 2 2
(
0, dac˘a n = 1,
n
n
n
n
N d (n) = l m j k l m j k (3)
N d + N d + N d , , dac˘a n > 1,
2 2 2 2
n n n n
l m j k l m j k
unde N c , s , i N d , reprezint˘a num˘arul de comparat ,ii de chei, respectiv
2 2 2 2
num˘arul de deplas˘ari efectuate la interclasarea celor doi subvectori sortat , i, (a 1 , . . . , a m ) s , i
› ž
n + 1 l m l m l m
n
n
n
(a m+1 , . . . , a n ), cu m = = , de dimensiuni m = , respectiv n − m = n − =
2 2 2 2
n
j k
.
2
Conform descrierii procedurii de interclasare, la interclasarea celor doi subvectorilor avem:
n n
l m j k
• Num˘arul de deplas˘ari N d , este egal cu dublul num˘arul de componente ale
2 2
lui A (fiecare component˘a - fie c˘a se afl˘a ˆın primul subvector, fie c˘a se afl˘a ˆın al doilea
subvector - este mutat˘a o dat˘a ˆın vectorul intermediar B s , i o dat˘a adus˘a ˆınapoi ˆın A),
deci
n n n n
l m j k l m j k
N d , = 2 + = 2n. (4)
2 2 2 2
n n
l m j k
• Num˘arul de comparat ,ii de chei N c , este egal cu num˘arul de execut , ii ale
2 2
ciclului while. Cu fiecare astfel de comparat , ie are loc s , i o copiere ˆın vectorul B a unei
componente din A, adic˘a o deplasare. La ies , irea din ciclul while, componentele unuia
dintre cei doi subvectori ai lui A au fost toate copiate ˆın B, iar ˆın cel˘alalt subvector au
mai r˘amas r componente necopiate ˆın B, care vor fi s , i ele copiate ˆın B, dar dup˘a ies , irea
din acest ciclu. Rezult˘a c˘a
n n
l m j k
N c , = n − r.
2 2
Evident,
n n n
nl m j ko l m
1 ≤ r ≤ max , = ,
2 2 2
deci
n n n n
l m j k nj k j k o
N c , ∈ , + 1, . . . , n − 1 . (5)
2 2 2 2