Page 22 - REVISTA MATINF Nr. 5

22 C. B˘alc˘au

−
t
−
Cum N (1) = 0 obt , inem c˘a N (2 ) − t · 2 t−1 = 0, deci
c
c
−
t
N (2 ) = t · 2 t−1 , ∀t ∈ N. (15)
c
Din (14), (15) s , i (13) rezult˘a c˘a ˆın cazul cel mai favorabil num˘arul de comparat ,ii de chei verific˘a
inegalit˘at , ile
1 1
−
∗
N (n) ≥ blog nc · 2 blog nc−1 > · n log n − · n, ∀n ∈ N . (16)
2
c
2
2
4 4
Din (11) s , i (16) rezult˘a c˘a num˘arul de comparat ,ii de chei verific˘a inegalit˘at , ile
1 1
∗
· n log n − · n < N c (n) < n log n + 1, ∀n ∈ N . (17)
4 2 4 2
Din relat , iile (3) s , i (4) rezult˘a c˘a num˘arul de deplas˘ari efectuate de algoritm verific˘a relat , ia
de recurent , ˘a
(
0, dac˘a n = 1,
n
n
N d (n) = l m j k
N d + N d + 2n, dac˘a n > 1.
2 2
Aceast˘a relat , ie se rezolv˘a analog relat , iei (6), obt , inˆandu-se
€ Š
∗
N d (n) = 2 ndlog ne − 2 dlog ne + n , ∀n ∈ N ,
2
2
deci
∗
2n log n − 2n < N d (n) < 2n log n + 2n, ∀n ∈ N . (18)
2
2
Din relat , iile (1), (17) s , i (18) rezult˘a c˘a T(n) = Θ(n log n).
2
Metoda 2) Vom aplica Teorema Master. Conform descrierii recursive a algoritmului
n n
l m j k
s , i utilizˆand complexitatea procedurii de interclasare (formulele pentru N c , s , i
2 2
n n
l m j k
N d , ), timpul de execut , ie T(n) verific˘a relat , ia de recurent , ˘a
2 2
T(n) = 2T(n/2) + Θ(n), ∀ n > 1,
cu convent , iile de notat , ie din Teorema Master (Teorema 1 din [2]). Conform Cazului 2 al acelei
teoreme (pentru a = 2, b = 2, c = 1 = log a s , i k = 0) rezult˘a c˘a T(n) = Θ(n log n).
2
b
Urm˘atorul rezultat este o consecint , ˘a direct˘a a teoremei anterioare s , i a Teoremei 1 din [3]
(care afirm˘a c˘a orice algoritm optim de sortare, bazat pe comparat , ii de chei, are complexitatea
Θ(n log n)).
2
Corolarul 4 (optimalitatea algoritmului de sortare prin interclasare). Algoritmul de
sortare prin interclasare este asimptotic-optim (ˆın clasa algoritmilor bazat ,i pe comparat ,ii de
chei), atˆat ˆın raport cu timpul de execut ,ie ˆın cazul cel mai defavorabil, cˆat s , i ˆın raport cu timpul
mediu de execut ,ie.

Observat ,ia 3. Mai mult, conform relat , iilor (11) s , i (17) s , i Teoremei 1 din [3] rezult˘a c˘a, exact
ca la algoritmii optimi de sortare bazat , i pe comparat , ii de chei, num˘arul de comparat , ii de chei
efectuate de algoritmul de sortare prin interclasare a unui vector cu n componente este chiar
asimptotic echivalent cu n log n, atˆat ˆın cazul cel mai defavorabil, cˆat s , i ˆın cazul mediu (cazul
2
timpului mediu de execut , ie).