Page 33 - MATINF Nr. 7
P. 33
Complexitatea algoritmului de sortare rapid˘a (quicksort) 33
Reamintim c˘a bxc reprezint˘a partea ˆıntreag˘a (inferioar˘a) a num˘arului real x (adic˘a aproximarea
ˆıntreag˘a prin lips˘a a lui x, notat˘a de obicei cu [x]), iar dxe reprezint˘a partea ˆıntreag˘a superioar˘a
a num˘arului real x (adic˘a aproximarea ˆıntreag˘a prin adaos a lui x).
Rezolv˘am relat , ia de recurent , ˘a (3). Pentru n = num˘ar par, adic˘a n = 2m, m ≥ 1, avem
−
−
−
−
N (n + 1) − N (n) = N (2m + 1) − N (2m)
−
−
−
−
= N (m) + N (m) + 2m − N (m) + N (m − 1) + 2m − 1
−
−
= N (m) − N (m − 1) + 1,
iar pentru n = num˘ar impar, adic˘a n = 2m + 1, m ≥ 1, avem
−
−
−
−
N (n + 1) − N (n) = N (2m + 2) − N (2m + 1)
−
−
−
−
= N (m + 1) + N (m) + 2m + 1 − N (m) + N (m) + 2m
−
−
= N (m + 1) − N (m) + 1,
deci pentru orice n ≥ 2 avem
n − 1 n − 1
−
−
N (n + 1) − N (n) = N − + 1 − N − + 1,
2 2
egalitatea fiind evident valabil˘a s , i pentru n = 1. Notˆand
−
−
v(n) = N (n + 1) − N (n), ∀n ∈ N, (4)
obt , inem c˘a
0, dac˘a n = 0,
v(n) = n − 1 (5)
v + 1, dac˘a n ≥ 1.
2
Demonstr˘am c˘a
v(n) = dlog (n + 2)e − 1, ∀n ∈ N, (6)
2
prin induct , ie.
Pentru n = 0 avem v(0) = 0 = dlog 2e − 1.
2
Presupunem egalitatea adev˘arat˘a pentru orice i ∈ {0, 1, . . . , n − 1} s , i o demonstr˘am pentru
ˆ
n (n ≥ 1). Intr-adev˘ar, folosind relat , ia de recurent , ˘a (5) s , i ipoteza de induct , ie pentru n − 1
2
avem
¡ ¤ ¡ ¤
n − 1 n − 1 n + 1
v(n) = v + 1 = log 2 + 2 = log 2 + 1 .
2 2 2
∗
Dar, notˆand dlog (n + 2)e = r, avem r ∈ N , r ≥ 2 s , i, succesiv:
2
r
r − 1 < log (n + 2) ≤ r; 2 r−1 < n + 2 ≤ 2 ;
2
n + 1
r
2 r−1 ≤ n + 1 < 2 ; 2 r−2 ≤ < 2 r−1 ;
2
n + 1 n + 1
2 r−2 ≤ < 2 r−1 ; 2 r−2 < + 1 ≤ 2 r−1 ;
2 2
n + 1
r − 2 < log 2 + 1 ≤ r − 1;
¡ 2 ¤
n + 1
log + 1 = r − 1,
2
2
