Page 40 - MATINF Nr. 1

40 C. B˘alc˘au

Propozit , ia 1. Fie f, g : N \ A → R + dou˘a funct ,ii, unde A este o mult ,ime finit˘a, A ⊂ N.
f(n)
Presupunem c˘a exist˘a lim = L. Atunci:
n→∞ g(n)

a) f(n) = O (g(n)) dac˘a s , i numai dac˘a L ∈ [0, +∞);
b) f(n) = Ω(g(n)) dac˘a s , i numai dac˘a L ∈ (0, +∞];

c) f(n) = Θ(g(n)) dac˘a s , i numai dac˘a L ∈ (0, +∞).

Corolarul 1. Fie f, g : N \ A → R + dou˘a funct ,ii, unde A este o mult ,ime finit˘a, A ⊂ N. Dac˘a
f(n) ∼ g(n), atunci f(n) = Θ(g(n)).

Definit , ia 4. Fie A un algoritm s , i f : N\A → R + o funct ,ie, unde A este o mult ,ime finit˘a, A ⊂ N.
Spunem c˘a algoritmul A are ordinul de complexitate (complexitatea) O (f(n)), Ω(f(n)),
respectiv Θ(f(n)) dac˘a T A (n) = O (f(n)), T A (n) = Ω(f(n)), respectiv T A (n) = Θ(f(n)).

Observat ,ia 1. Notat , ia O se utilizeaz˘a pentru a exprima complexitatea unui algoritm cores-
punz˘atoare timpului de execut ,ie ˆın cazul cel mai defavorabil, fiind astfel cea mai adecvat˘a analizei
algoritmilor. Notat , ia Ω este corespunz˘atoare timpului de execut ,ie ˆın cazul cel mai favorabil, caz
practic irelevant, fiind astfel mai put , in utilizat˘a. Notat , iile ∼ s , i Θ se utilizeaz˘a atunci cˆand se
constat˘a c˘a timpii de execut , ie corespunz˘atori cazurilor cel mai defavorabil s , i cel mai favorabil
fie sunt chiar asimptotic echivalent , i (notat , ia ∼, deci s , i notat , ia Θ), cazul cel mai simplu fiind
acela al algoritmilor a c˘aror executare depinde doar de dimensiunea setului de date de intrare,
nu s , i de valorile acestor date, fie au m˘acar acelas , i ordin de cres , tere (notat , ia Θ). Tot aceste
notat , ii se utilizeaz˘a s , i atunci cˆand se poate determina timpul mediu de execut ,ie al algoritmului,
calculat ca medie aritmetic˘a ponderat˘a a timpilor de execut , ie pentru toate seturile de date de
intrare posibile, ponderile fiind frecvent , ele de aparit , ie ale acestor seturi.

Definit , ia 5. Un algoritm A este considerat asimptotic-optim dac˘a (se demonstreaz˘a c˘a) nu
exist˘a un algoritm avˆand un ordin de complexitate mai bun pentru rezolvarea problemei date,
0
adic˘a pentru orice algoritm A care rezolv˘a problema dat˘a avem T A (n) = O (T A 0(n)).

Evident, orice algoritm optim este asimptotic-optim. Reciproca acestei afirmat , ii nu este
adev˘arat˘a, ˆın continuare fiind prezentat un exemplu ˆın acest sens.
Exemplul 1. Consider˘am problema determin˘arii maximului s , i minimului dintre elementele unui
vector dat A = (a 1 , a 2 , . . . , a n ), n ≥ 1, adic˘a se cere s˘a se determine perechea (M, m), unde
M = max{a i | 1 ≤ i ≤ n}, m = min{a i | 1 ≤ i ≤ n}.
Un algoritm uzual de rezolvare este urm˘atorul.

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

Pentru evaluarea complexit˘at , ii algoritmilor care rezolv˘a problema dat˘a, vom analiza numai com-
parat , iile ˆın care intervin elemente ale vectorului sau valorile M s , i m, numite comparat ,ii de chei.