Page 35 - MATINF Nr. 7
P. 35
Complexitatea algoritmului de sortare rapid˘a (quicksort) 35
n − 1
−
Pentru k = + 1 avem ϕ(k) = 0, deci N(n) − N (n) ≥ 0.
2
§ ª
n − 1
Pentru k ∈ 1, 2, . . . , , conform (7) avem
2
¡ ¤
−
−
ϕ(k) = N (k − 1) + N (n − k) − N − n − 1 − N − n − 1
2 2
k n−k+1
X X
= dlog ie − k + 1 + dlog ie − n + k
2
2
i=1 i=1
d n−1 e+1 ¡ ¤ b n−1 c+1
2
2
X n − 1 X n − 1
− dlog ie + − dlog ie +
2
2
2 2
i=1
i=1
d n−1 b n−1
n−k+1 2 e+1 2 c+1 k
X X X X
= dlog ie − dlog ie − dlog ie − dlog ie
2
2
2
2
i=1 i=1 i=1 i=1
b n−1
n−k+1 2 c+1
X X
= dlog ie − dlog ie
2
2
i=d n−1 e+2 i=k+1
2
b n−1 c+1−k ¡ ¡ ¤ ¤ b n−1 c+1−k
2
2
X n − 1 X
= log 2 i + + 1 − dlog (i + k)e
2
2
i=1 i=1
b n−1 c+1−k ¡ ¡ ¤ ¤
2
X n − 1
= log 2 i + + 1 − dlog (i + k)e
2
i=1 2
≥ 0.
−
Conform (10) rezult˘a din nou c˘a N(n) − N (n) ≥ 0 s , i astfel demonstrat , ia prin induct , ie a
inegalit˘at , ii (9) este ˆıncheiat˘a.
Astfel Cazul 2) este cel mai favorabil, avˆand num˘arul de comparat , ii dat de relat , ia (8) s , i,
prin urmare, complexitatea Θ(n log n).
2
§ ¡ ¤ª
n + 1 n + 1
Semnal˘am c˘a egalitatea poate avea loc ˆın (9) s , i pentru valori k 6∈ , , de
2 2
−
−
−
−
exemplu pentru n = 10 s , i k = 4 (N (3) + N (6) = 2 + 8 = 10, N (4) + N (5) = 4 + 6 = 10).
Cazul 3) Analiz˘am acum cazul mediu (cazul timpului mediu de execut , ie). Not˘am cu N k (n)
num˘arul de comparat , ii de chei efectuate de algoritm pentru un vector cu n componente ˆın cazul
ˆın care indicele pivotului este k. Evident k poate lua oricare dintre valorile 1, 2, . . . , n, iar toate
aceste situat , ii sunt echiprobabile, deci num˘arul mediu de comparat , ii de chei are valoarea
n
P
N k (n)
k=1
N med (n) = .
n
Conform descrierii algoritmului (a se vedea relat , ia (1)) avem
§
0, dac˘a n ∈ {0, 1},
N k (n) =
N med (k − 1) + N med (n − k) + n − 1, dac˘a n ≥ 2,
