Page 41 - MATINF Nr. 1

Optimalitatea algoritmului de c˘autare binar˘a 41

Evident, algoritmul MAX-MIN efectueaz˘a cel put , in n − 1 s , i cel mult 2n − 2 astfel de comparat , ii
(iar celelalte operat , ii nu dep˘as , esc ordinul de cres , tere al acestora), deci are complexitatea Θ(n).

Se poate demonstra us , or prin induct , ie c˘a orice algoritm A care calculeaz˘a maximul dintre n
elemente, bazat pe comparat , ii de chei, necesit˘a cel put , in n − 1 astfel de comparat , ii, deci are
complexitatea Ω(n). Astfel T A (n) = Ω(T MAX-MIN (n)), sau, echivalent, T MAX-MIN (n) = O (T A (n)),
deci algoritmul MAX-MIN este asimptotic-optim (ˆın clasa algoritmilor bazat , i pe comparat , ii de
chei). Pe de alt˘a parte, el nu este optim, din punct de vedere al timpului de execut , ie ˆın cazul
cel mai defavorabil, deoarece exist˘a algoritmi (bazat , i pe comparat , ii de chei) care ˆın cazul cel
mai defavorabil efectueaz˘a mai put , in de 2n − 2 comparat , ii de chei, cˆat efectueaz˘a algoritmul
MAX-MIN. Un astfel de exemplu este urm˘atorul algoritm, ce compar˘a a 1 cu a 2 , a 3 cu a 4 , . . . ,
s , i calculeaz˘a maximul dintre maximele acestor perechi s , i minimul dintre minimele perechilor.

MAX-MIN-PER(A, n, M, m) :
M ← a n ; m ← a n ;
for i = 1, bn/2c do
if a 2i−1 > a 2i then
if a 2i−1 > M then
M ← a 2i−1 ;
if a 2i < m then
m ← a 2i ;
else
if a 2i > M then
M ← a 2i ;
if a 2i−1 < m then
m ← a 2i−1 ;

(bxc reprezint˘a partea ˆıntreag˘a a num˘arului real x). Evident, algoritmul MAX-MIN-PER
n
õ û
efectueaz˘a exact 3 · comparat , ii de chei, indiferent de ordinea dintre elementele vectorului A
2
(iar celelalte operat , ii nu dep˘as , esc ordinul de cres , tere al acestora), deci are complexitatea Θ(n).

Teorema Master

Prezent˘am un rezultat celebru, deosebit de util ˆın determinarea complexit˘at , ii algoritmilor
specifici metodei de programare Divide et Impera s , i nu numai.

Consider˘am o relat , ie de recurent , ˘a de forma
T(n) = T(n/b) + . . . + T(n/b) +f(n), ∀ n > n 0 ,
| {z }
a termeni
∗
unde T, f : N → R + , n 0 ∈ N, a ∈ N , b ∈ R, b > 1 s , i, prin convent , ie, fiecare termen n/b
n n
õ û ° §
reprezint˘a fie , fie .
b b
Ment , ion˘am c˘a dxe = min{k | k ∈ Z, k ≥ x} reprezint˘a aproximarea ˆıntreag˘a prin adaos a
ˆ
num˘arului real x, numit˘a s , i partea ˆıntreag˘a superioar˘a a lui x. In acest context, partea ˆıntreag˘a
uzual˘a, bxc (notat˘a de obicei cu [x]), se numes , te s , i partea ˆıntreag˘a inferioar˘a a lui x.

Prin abuz de notat , ia de ˆınmult , ire, aceast˘a relat , ie de recurent , ˘a este convent , ional rescris˘a
prescurtat sub forma
T(n) = aT(n/b) + f(n), ∀ n > n 0 . (1)