Page 37 - MATINF Nr. 7

Complexitatea algoritmului de sortare rapid˘a (quicksort) 37

Cum N med (1) = 0, obt , inem c˘a
 ‹
1 1 1
N med (n) = 2(n + 1) 1 + + + . . . + − 4n, ∀ n ≥ 1.
2 3 n

1 1 1
Aplicˆand Teorema Stolz-Ces`aro pentru s , irurile a n = 1 + + + . . . + s , i b n = ln n (strict
2 3 n
cresc˘ator s , i avˆand limita ∞) avem

1 1 1
1 + + + . . . +
lim 2 3 n = lim a n = lim a n+1 − a n
n→∞ ln n n→∞ b n n→∞ b n+1 − b n
1
n + 1 n 1 1
= lim = lim ·  ‹ = = 1.
n
n→∞ ln(n + 1) − ln n n→∞ n + 1 1 ln e
ln 1 +
n
Deducem c˘a

N med (n) ln 2 · N med (n)
lim = lim
n→∞ n log n n→∞ n ln n
2 
1 1 1
1 + + + . . . +
2(n + 1) 2 3 n 4
= ln 2 · lim · −
n→∞ n ln n ln n

= 2 ln 2, (11)

deci N med (n) = Θ(n log n),
2

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 1 (optimalitatea algoritmului de sortare rapid˘a). Algoritmul de sortare rapid˘a
este asimptotic-optim (ˆın clasa algoritmilor bazat ,i pe comparat ,ii de chei), ˆın raport cu timpul
mediu de execut ,ie.

ˆ
Observat ,ia 3. In cazul cel mai favorabil, conform relat , iei (8) rezult˘a c˘a num˘arul de comparat , ii
de chei efectuate de algoritmul de sortare rapid˘a este asimptotic echivalent cu n log n.
2
ˆ
In cazul timpului mediu de execut , ie, conform relat , iei (11) rezult˘a c˘a num˘arul de comparat , ii
de chei efectuate de algoritmul de sortare rapid˘a este asimptotic echivalent cu

2 ln 2 · n log n.
2

Deci conform Teoremei 1 din [3] (care afirm˘a s , i c˘a num˘arul de comparat , ii de chei efectuate
de un algoritm optim de sortare a unui vector cu n componente este asimptotic echivalent cu
n log n, atˆat ˆın cazul cel mai defavorabil, cˆat s , i ˆın cazul timpului mediu de execut , ie), rezult˘a c˘a
2
algoritmul de sortare rapid˘a nu este optim ˆın raport cu timpul mediu de execut , ie.

Pe de alt˘a parte, cum 2 ln 2 ' 1,39, rezult˘a c˘a ˆın cazul mediu num˘arul de comparat , ii efectuate
este mai mare doar cu aproximativ 39% decˆat ˆın cazul cel mai favorabil (sau decˆat un algoritm
optim).