Page 50 - MATINF Nr. 1

50 C. B˘alc˘au

Conform Propozit , iei 5 s , i Observat , iei 3 rezult˘a c˘a h = dlog (n + 1)e = blog nc + 1. Conform
2
2
Observat , iei 7 rezult˘a c˘a o c˘autare cu succes necesit˘a cel mult h comparat , ii de chei, iar o c˘autare
f˘ar˘a succes necesit˘a h − 1 sau h comparat , ii de chei.

Observat ,ia 8. Conform propozit , iei anterioare, algoritmul de c˘autare binar˘a are timpul de execut , ie
ˆın cazul cel mai defavorabil de ordinul Θ(log n) (celelalte operat , ii nu dep˘as , esc ordinul de cres , tere
2
al comparat , iilor de chei), deci timpul (mediu) de execut , ie are ordinul O (log n). Teorema
2
urm˘atoare ˆımbun˘at˘at , es , te acest rezultat.

Teorema 3. Fie T(n) timpul mediu de execut ,ie al algoritmului de c˘autare binar˘a ˆıntr-un vector
sortat cu n componente. Avem T(n) = Θ(log n).
2

Demonstrat¸ie. Consider˘am c˘a timpul mediu de execut , ie T(n) al algoritmului de c˘autare binar˘a
este dat de num˘arul de comparat , ii de chei efectuate (celelalte operat , ii nu dep˘as , esc ordinul de
cres , tere al acestora). Vom demonstra c˘a T(n) = Θ(log n) prin dou˘a metode.
2
Metoda 1) Vom aplica Teorema Master. Conform descrierii recursive a algoritmului de
c˘autare binar˘a, timpul de execut , ie T(n) verific˘a relat , ia de recurent , ˘a

T(n) = T(n/2) + O (1), ∀ n > 0,

cu convent , iile de notat , ie din Teorema Master. Conform Cazului 2 al acelei teoreme, pentru
a = 1, b = 2, c = 0 = log a s , i k = 0, rezult˘a c˘a T(n) = Θ(log n).
b
2
Observat ,ia 9. Ca o consecint , ˘a imediat˘a a Metodei 1, Propozit , iei 7 s , i Teoremei 2 rezult˘a c˘a
algoritmul de c˘autare binar˘a 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). Pentru a justifica faptul c˘a algoritmul este chiar optim, nu este
suficient˘a evaluarea complexit˘at , ii cu Teorema Master. Aici intervine metoda urm˘atoare, prin
care se num˘ar˘a comparat , iile efectuate de algoritm.

Metoda 2) Vom calcula efectiv timpul mediu de execut , ie T(n). Conform demonstrat , iei
Propozit , iei 7, arborele binar extins de c˘autare asociat algoritmului c˘aut˘arii binare este un arbore
binar strict cu n noduri interne s , i n + 1 noduri externe, iar toate nodurile externe sunt situate
pe ultimul s , i, eventual, pe penultimul nivel. Not˘am cu I mult , imea nodurilor interne, cu E
mult , imea nodurilor externe, iar pentru fiecare nod k not˘am cu D(k) distant , a de la r˘ad˘acina
arborelui la nodul k. Conform Observat , iei 7, timpul mediu de execut , ie are valoarea

(1 + D(k)) + D(k) n + D(k) + D(k)
P P P P
k∈I k∈E k∈I k∈E
T(n) = = .
2n + 1 2n + 1
Conform Propozit , iilor 3 s , i 5 rezult˘a c˘a

2 P D(k) − n dlog (n+1)e
k∈E 2n + 2 n + 2 − 2 · 2 2
T(n) = = · dlog (n + 1)e + . (6)
2
2n + 1 2n + 1 2n + 1
Dar, conform Observat , iei 3, dlog (n + 1)e = 1 + blog nc , deci
2
2
2n + 2 3n + 4 − 4 · 2 blog nc
2
T(n) = · blog nc + .
2
2n + 1 2n + 1