Page 39 - MATINF Nr. 1

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Optimalitatea algoritmului de c˘autare binar˘a

Costel B˘alc˘au 1

ˆ
In acest articol vom demonstra c˘a algoritmul de c˘autare binar˘a este optim. Pentru aceasta
vom prezenta s , i utiliza cˆateva not , iuni s , i rezultate de baz˘a din teoria algoritmilor: ordine de
complexitate, Teorema Master, propriet˘at , i ale arborilor binari strict , i.

Ordine de complexitate

Timpul de execut , ie al unui algoritm depinde, ˆın general, de setul datelor de intrare, iar pentru
fiecare astfel de set el este bine determinat de num˘arul de operat , ii executate s , i de tipul acestora.
Astfel timpul de execut , ie al unui algoritm poate fi interpretat s , i analizat drept o funct , ie pozitiv˘a
ce are ca argument dimensiunea datelor de intrare.

Definit , ia 1. Pentru orice algoritm A, not˘am cu T A (n) timpul de execut , ie pentru algoritmul
A corespunz˘ator unui set de date de intrare avˆand dimensiunea total˘a n.
Definit , ia 2. Un algoritm A este considerat optim dac˘a (se demonstreaz˘a c˘a) nu exist˘a un
algoritm avˆand un timp de execut ,ie mai bun pentru rezolvarea problemei date, adic˘a pentru orice
0
algoritm A care rezolv˘a problema dat˘a avem T A (n) ≤ T A 0(n), pentru orice n.

Obt , inerea de algoritmi pur optimi - ˆın sensul definit , iei anterioare - este posibil˘a ˆın put , ine
situat , ii, iar demonstrarea optimalit˘at , ii acestora este de obicei dificil˘a. Mult mai des se ˆıntˆalnesc
algoritmi cu o comportare apropiat˘a de cea optim˘a, pentru valori suficient de mari ale dimensiunii
setului datelor de intrare. Prezent˘am ˆın continuare cˆateva not , iuni prin care se cuantific˘a aceast˘a
apropiere.

Definit , ia 3. Fie f, g : N \ A → R + dou˘a funct ,ii, unde A este o mult ,ime finit˘a, A ⊂ N.
f(n)
a) f s , i g se numesc asimptotic echivalente s , i not˘am f(n) ∼ g(n) dac˘a ∃ lim = 1.
n→∞ g(n)

b) Spunem c˘a f este asimptotic m˘arginit˘a superior de g, iar g este asimptotic
m˘arginit˘a inferior de f s , i not˘am f(n) = O (g(n)) s , i g(n) = Ω(f(n)) dac˘a ∃ c > 0, ∃ n 0 ∈ N
astfel ˆıncˆat f(n) ≤ c · g(n), ∀ n ≥ n 0 .

c) Spunem c˘a f s , i g au acelas , i ordin de cres , tere s , i not˘am f(n) = Θ(g(n)) dac˘a
f(n) = O (g(n)) s , i f(n) = Ω(g(n)).

Urm˘atorul rezultat este o consecint , ˘a imediat˘a a definit , iei anterioare.
1
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com

39