Analiza complexitatii algoritmilor

Analiza complexitatii algoritmilor

Exista mai multi algoritmi de rezolvare a unei probleme date. Prin urmare, se impune o analiza a acestora, in scopul determinarii eficientei algoritmilor de rezolvare a problemei si pe cat posibil a optimalitatii lor. Criteriile in functie de care vom stabili eficienta unui algoritm sunt complexitatea spatiu si complexitatea timp.

Prin complexitate spatiu intelegem dimensiunea spatiului de memorie utilizat de program. Un program necesita un spatiu de memorie constant, independent de datele de intrare, pentru memorarea codului sau, a constantelor, a variabilelor simple si a structurilor de date de dimensiune constanta alocate static si un spatiu de memorie variabil, a carui dimensiune depinde adesea de datele de intrare, constand din spatiul necesar pentru structurile de date alocate dinamic, a caror dimensiune depinde de instanta problemei de rezolvat si din spatiul de memorie necesar apelurilor de proceduri si functii.

De exemplu, sa consideram urmatoarea problema:

Fie A o multime cu n elemente si x o valoare de tipul elementelor multimii A. Sa se decida daca x apartine sau nu multimii.

Vom scrie o functie iterativa care va cauta secvential valoarea x in vectorul folosit pentru memorarea multimii A, functie care intoarce valoarea true daca x se gaseste in vector si false in caz contrar.

function cauta : boolean;

var i: integer; gasit: boolean;

begin

i := 1; gasit := false;

while (i n) and not gasit do

if ai = x then gasit := true

else i := i+1;

cauta := gasit;

end;

Functia cauta va fi apelata o singura data. Neavand parametri, va necesita spatiu de memorie doar pentru variabilele locale si pentru adresa de revenire. Deci nu este necesar spatiu de memorie variabil. Aceeasi problema o putem rezolva cu ajutorul unei functii recursive rcauta.

Functia are un parametru intreg care indica pozitia de la care incepe cautarea in vectorul a. Evident, initial apelam rcauta(1).

function rcauta (poz: integer): boolean;

begin

if poz > n then rcauta := false

else if apoz = x then rcauta := true

else rcauta := rcauta(poz+1);

end;

Spatiul de memorie utilizat pentru un apel al functiei este cel necesar pentru memorarea parametrului (2 octeti) si pentru adresa de revenire (2 octeti). Daca x nu se gaseste in vector se fac n apeluri recursive, deci spatiul de memorie variabil este de 4n octeti. Daca x se gaseste in vector, dimensiunea spatiului de memorie variabil depinde de pozitia pe care x se gaseste in vectorul a. Deci, varianta recursiva necesita un spatiu de memorie mult mai mare decat varianta iterativa.

Progresele tehnologice fac ca importanta criteriului spatiu de memorie utilizat sa scada, prioritar devenind criteriul timp.

Prin complexitate timp intelegem timpul necesar executiei programului. Inainte de a evalua timpul necesar executiei programului ar trebui sa avem informatii detaliate despre sistemul de calcul folosit. Pentru a analiza teoretic algoritmul, vom presupune ca se lucreaza pe un calculator 'clasic', in sensul ca o singura instructiune este executata la un moment dat. Astfel, timpul necesar executiei programului depinde de numarul de operatii elementare efectuate de algoritm. Privind din perspectiva calculului paralel, acest mod de analiza a complexitatii timp a unui algoritm va fi, probabil, total inadecvat pentru viitoarele generatii de calculatoare. Dar pentru algoritmii 'clasici' ofera un criteriu general de comparatie, fara a fi necesara implementarea si rularea pe un calculator. De altfel, din motive practice, pe calculator nu putem testa algoritmul pentru cazuri oricat de mari si nu putem obtine informatii asupra comportarii in timp a algoritmilor decat pentru seturi particulare de date de intrare.

Primul pas in analiza complexitatii timp a unui algoritm este determinarea operatiilor elementare efectuate de algoritm si a costurilor acestora. Numim operatie elementara o operatie al carei timp de executie este independent de datele de intrare ale problemei. Timpul necesar executiei unei operatii elementare poate fi diferit de la o operatie la alta, dar este fixat, deci putem spune ca operatiile elementare au timpul marginit superior de o constanta. Fara a restrange generalitatea, vom presupune ca toate operatiile elementare au acelasi timp de executie, fiind astfel necesara doar evaluarea numarului de operatii elementare, nu si a timpului total de executie a acestora. Analiza teoretica ignora toti factorii care depind de masina sau de limbajul de programare ales si se axeaza doar pe determinarea ordinului de marime a numarului de operatii elementare.

Scopul analizei teoretice a algoritmilor este de fapt determinarea unor functii care sa limiteze superior, respectiv inferior comportarea in timp a algoritmului. Functiile depind de caracteristicile relevante ale datelor de intrare.

9.1. Notatia asimptotica

Notam T_A(n) timpul necesar executiei algoritmului A.

Fie f: N R₊^* o functie arbitrara. Spunem ca algoritmul este de ordinul lui f(n) ( notat O(f(n)) ), daca si numai daca exista c > 0 si n N, astfel incat T_A(n) c^.f(n), n n

De exemplu:

a)     Daca T_A(n) = 3n+2, atunci T_A(n)O(n), pentru ca 3n+2 4n,

n

Mai general, daca T_A(n) = an+b, a > 0, atunci T_A(n)O(n) pentru ca exista c = a+1 > 0 si n₀ = bN, astfel incat an+b (a+1)n, n b.

b)     Daca T_A(n) = 10n²+4n+2, atunci T_A(n)O(n²), pentru ca 10n²+4n+2 11n², n

Mai general, daca T_A(n) = an²+bn+c, a > 0, atunci T_A(n)O(n²), pentru ca an²+bn+c (a+1)n², n max(b,c)+1.

c) Daca T_A(n) = 6 2ⁿ+n², atunci T_A(n)O(2ⁿ), pentru ca T_A(n) = 6 2ⁿ+n² 2ⁿ,n

Propozitie

Daca T_A(n) = a_kn^k+a_k-1n^k-1++a₁n+a₀, atunci T_A(n)O(n^k).

Demonstratie

T_A(n) = T_A(n) a_kn^k+a_k-1n^k-1++a₁n+a₀ a_kn^k+a_k-1n^k-1++a₁n+a₀ a_k a_k-1 a₁ a₀)n^k, n

Alegand c = a_k a_k-1 a₁ a₀ si n₀ = 1 T T_A(n)O(n^k

Q.E.D.

Observatii

1. Notatia O ofera o limita superioara a timpului de executie a unui algoritm.

2. Un algoritm cu T_A(n)O(1) necesita un timp de executie constant.

Un algoritm cu T_A(n)O(n) se numeste liniar. Daca T_A(n)O(n²) algoritmul se numeste patratic, iar daca T_A(n)O(n³), cubic. Un algoritm cu T_A(n)O(n^k) se numeste polinomial, iar daca T_A(n) O(2ⁿ) algoritmul se numeste exponential.

3. Notatia asimptotica O defineste o relatie de ordine partiala pe multimea algoritmilor :

O(1)O(log n)O(n)O(n log n)O(n²)O(n^k)O(2ⁿ), k>2.

Putem astfel clasifica algoritmii din punctul de vedere al performantei.

Figura de mai jos ilustreaza comportarea a cinci din cele mai importante functii de complexitate. Observati ca functiile de O(n) si O(log n) cresc mult mai lent decat celelalte, in timp ce un algoritm exponential va putea fi folosit in practica doar pentru valori mici ale lui n. Daca T_A(n)O(2ⁿ), pentru n=40, pe un calculator care face 1 bilion (10 ) de operatii pe secunda, sunt necesare aproximativ 18 minute. Pentru n=50, acelasi program va rula 13 zile pe acest calculator, iar pentru n=60, vor fi necesari peste 310 ani, iar pentru n=100 aproximativ 4^.10 ani.

Utilitatea algoritmilor polinomiali de grad mare este de asemeni limitata. De exemplu, pentru O(n ), pe un calculator care executa 1 bilion de operatii pe secunda sunt necesare 10 secunde pentru n=10, aproximativ 3 ani pentru n=100 si circa 3^.10 ani pentru n=1000.

Uneori este util sa determinam si o limita inferioara pentru timpul de executie a unui algoritm. Notatia matematica este

Definitie

Spunem ca T_A(n)(f(n)) daca si numai daca c>0 si n N astfel incat T_A(n) c f(n) ,n n

De exemplu :

a)     daca T_A(n) = 3n+2, atunci T_A(n)(n), pentru ca 3n+2 3n,

n

b) daca T_A(n) = 10n +4n+2, atunci T_A(n)(n), pentru ca 10n +4n+2 n n

c) daca T_A(n) = 6^.2ⁿ+n , atunci T_A(n) ⁿ), pentru ca 6^.2ⁿ+n ⁿ n

Observatie

Exista functii f care constituie atat o limita superioara cat si o limita inferioara a timpului de executie a algoritmului.

Propozitie

Daca T_A(n) = a_kn^k+a_k-1n^k-1++a n+a , a_k >0 atunci T_A(n)(n^k

Demonstratie

Q.E.D.

Definitie

Spunem ca T_A(n)(f(n)) daca si numai daca c₁, c₂>0 si n N astfel incat c₁ f(n) T_A(n) c₂ f(n) ,n n

In acest caz f(n) constituie atat o limita inferioara cat si o limita superioara pentru timpul de executie a algoritmului. Din acest motiv se poate numi ordin exact.

(f(n))=O(f(n))(f(n)).

Observatie

Daca T_A(n) = a_kn^k+a_k-1n^k-1++a n+a , a_k>0 atunci T_A(n)Q (n^k

9.2. Cazul mediu si cazul cel mai defavorabil

Am aratat ca timpul de executie al unui algoritm este direct proportional cu numarul de operatii elementare si am stabilit o notatie asimptotica pentru timpul de executie.

Totusi, numarul de operatii elementare efectuate de algoritm poate varia considerabil pentru diferite seturi de date de intrare.Vom exprima numarul de operatii elementare ca o functie de anumite caracteristici ale datelor de intrare (de exemplu, numarul de date de intrare sau ordinul de marime a unei anumite date de intrare). De altfel, pentru a stabili semnificatia exacta a notiunii de operatie elementara in contextul algoritmului pe care il analizam trebuie sa specificam care sunt caracteristicile datelor de intrare in functie de care estimam timpul de executie a algoritmului. O operatie elementara este o secventa computationala independenta de caracteristici (de exemplu, 10 adunari pot constitui o operatie elementara, dar daca n este o caracteristica relevanta a datelor de intrare, n adunari nu constituie o operatie elementara).

Determinarea complexitatii timp a algoritmului ca o functie de caracteristicile datelor de intrare este o sarcina usoara doar pentru algoritmi relativ simpli, dar in general problema este dificila si analizam complexitatea algoritmilor in medie sau in cazul cel mai defavorabil.

Complexitatea in cazul cel mai defavorabil este numarul maxim de operatii elementare efectuate de algoritm.

Dar chiar daca este cunoscut cazul cel mai defavorabil, datele utilizate efectiv in practica pot conduce la timpi de executie mult mai mici. Numerosi algoritmi foarte utili au o comportare convenabila in practica, dar foarte proasta in cazul cel mai defavorabil. Cel mai cunoscut exemplu este algoritmul de sortare rapida (quicksort) care are complexitatea in cazul cel mai defavorabil de O(n²), dar pentru datele intalnite in practica functioneaza in O(n log n ).

O alta modalitate de a studia performantele unui algoritm consta in determinarea complexitatii in medie. Pentru a determina complexitatea in medie este necesara cunoasterea repartitiei probabilistice a datelor de intrare si din acest motiv analiza complexitatii in medie este mai dificil de realizat. Pentru cazuri simple, de exemplu un algoritm de sortare care actioneaza asupra unui tablou cu n componente intregi aleatoare sau un algoritm geometric pe o multime de N puncte in plan de coordonate aleatoare cuprinse in intervalul , putem caracteriza exact datele de intrare.

Daca notam : D-spatiul datelor de intrare

p(d)-probabilitatea aparitiei datei dD la intrarea algoritmului

T_A(d)-numarul de operatii elementare efectuate de algoritm pentru

intrarea dD

atunci complexitatea medie este p(d)^.T_A(d).

dD

9.3. Exemple

9.3.1. Calcularea maximului

Fiind date n elemente a₁, a₂, , a_n, sa se calculeze

max a₁, a₂, , a_n

max := a

for i := 2 to n do

if ai > max then max := ai

Vom estima timpul de executie al algoritmului in functie de n, numarul de date de intrare. Fiecare iteratie a ciclului for o vom considera operatie elementara. Deci complexitatea algoritmului este O(n), atat in medie cat si in cazul cel mai defavorabil.

9.3.2. Sortarea prin selectia maximului

Fiind dat a, un vector cu n componente, sa ordonam crecator elementele vectorului.

for dr := n downto 2 do

begin

max := a ; pozmax := 1;

for i := 2 to dr do

if ai > max then

begin

ai := max;

pozmax := i

end;

apozmax := adr

adr := max;

end;

Estimam complexitatea algoritmului in functie de n, dimensiunea vectorului. La fiecare iteratie a ciclului for exterior este calculat maxa₁, a₂, , a_dr si plasat pe pozitia dr, elementele de la dr+1 la n fiind deja plasate pe pozitiile lor definitive.

Conform exemplului anterior, pentru a calcula maxa₁, a₂, , a_dr sunt necesare dr-1 operatii elementare, in total 1+2++n-1 = n (n-1)/2. Deci complexitatea algoritmului este de O(n ). Sa observam ca timpul de executie a algoritmului este independent de ordinea initiala a elementelor vectorului.

9.3.3. Sortarea prin insertie

Este o metoda de asemeni simpla, pe care o utilizam adesea cand ordonam cartile la jocuri de carti.

for i := 2 to n do

begin

val := ai; poz := i;

while apoz-1 > val do

begin

apoz := apoz-1

poz := poz-1;

end;

apoz := val

end;

Analizam algoritmul tot in functie de n, dimensiunea vectorului a ce urmeaza a fi sortat. La fiecare iteratie a ciclului for elementele a₁, a₂, , a_i-1 sunt deja ordonate si trebuie sa inseram valorea ai pe pozitia corecta in sirul ordonat. In cazul cel mai defavorabil, cand vectorul este initial ordonat descrescator, fiecare element ai va fi plasat pe prima pozitie, deci ciclul while se executa de i-1 ori. Considerand drept operatie elementara comparatia apoz-1>val urmata de deplasarea elementului de pe pozitia poz-1, vom avea in cazul cel mai defavorabil 1+2++n-1 = n (n-1)/2 operatii elementare, deci complexitatea algoritmului este de O(n

Sa analizam comportarea algoritmului in medie. Pentru aceasta, vom considera ca elementele vectorului sunt distincte si ca orice permutare a lor are aceeasi probabilitate de aparitie. Atunci probabilitatea ca valoarea a_i sa fie plasata pe pozitia k in sirul a , a , , a_i, k1,2,.,ieste 1/i. Numarul mediu de operatii elementare, pentru i fixat este:

Pentru a sorta cele n elemente sunt necesare

operatii elementare. Deci complexitatea algoritmului in medie este tot O(n

9.3.4. Sortarea rapida (quicksort)

Elaborat de C.A.R. Hoare in 1960, este unul dintre cei mai utilizati algoritmi de sortare.

procedure quicksort (st, dr : integer);

var m: integer;

begin    //sorteaza vectorul ast..dr

if st < dr then

begin

m := divide(st, dr);

quicksort(st, m-1);

quicksort(m+1, dr);

end;

Initial apelam quicksort(1, n).

function divide (st, dr: integer): integer;

var i, j, val: integer;

begin

//plaseaza primul element (a [st]) pe pozitia sa corecta in sirul ordonat. //In stanga sa se vor gasi numai elemente mai mici, in dreapta numai //elemente mai mari decat el

val := ast

i := st; j := dr;

while i < j do

begin

while (i < j) and (aj val) do    j := j - 1 ;

ai := aj

while (i < j) and (ai val) do i := i + 1 ;

aj := ai

end ;

ai := val ;

divide := i ;

end ;

Observatie

Vectorul a este considerat variabila globala.

In cazul cel mai defavorabil, cand vectorul a era initial ordonat, se fac n -1 apeluri succesive ale procedurii quicksort, cu parametrii (1,n), (1,n-1), , (1, 2) (daca vectorul a era initial ordonat descrescator) sau (1,n), (2,n), , (n -1,n) (daca vectorul a era ordonat crescator).

La fiecare apel al procedurii quicksort este apelata functia divide(1,i) (respectiv divide(i, n) ) care efectueaza i -1, (respectiv n -i -1) operatii elementare. In total numarul de operatii elementare este n-1+n-2++1=n (n-1)/2. Complexitatea algoritmului in cazul cel mai defavorabil este de O(n

Sa analizam comportarea algoritmului in medie. Consideram ca orice permutare a elementelor vectorului are aceeasi probabilitate de aparitie si notam cu T_n numarul de operatii elementare efectuate pentru a sorta n elemente.

Probabilitatea ca un element al vectorului sa fie plasat pe pozitia k in vectorul ordonat, este de 1/n.

(pentru a ordona crescator n elemente, determinam pozitia k in vectorul ordonat a primului element, ceea ce necesita n-1 operatii elementare, sortam elementele din stanga, ceea ce necesita T_k-1 operatii elementare, apoi cele din dreapta, necesitand T_n-k operatii elementare).

Problema se reduce la a rezolva relatia de recurenta de mai sus. Mai intai observam ca T +T + +T_n-1 = T_n-1+ +T +T _.

Deci,

Inmultim ambii membrii ai acestei relatii cu n. Obtinem :

Scazand din aceasta relatie, relatia obtinuta pentru n -1, adica

obtinem

Impartind ambii membrii cu n^.(n+1) obtinem

Deci

Am demonstrat astfel ca, in medie, complexitatea algoritmului este de O(n log n).

9.3.5. Problema celebritatii

Numim celebritate o persoana care este cunoscuta de toata lumea, dar nu cunoaste pe nimeni. Se pune problema de a identifica o celebritate, daca exista, intr-un grup de n persoane pentru care relatiile dintre persoane sunt cunoscute.

Observatie

Putem reformula problema in limbaj de grafuri astfel : fiind dat un digraf cu n varfuri, verificati daca exista un varf cu gradul exterior 0 si gradul interior n-1.

Reprezentam graful asociat problemei prin matricea de adiacenta a_nxn

O prima solutie ar fi sa calculam pentru fiecare persoana p din grup numarul de persoane pe care p le cunoaste (out) si numarul de persoane care cunosc persoana p (in). Cu alte cuvinte, pentru fiecare varf din digraf calculam gradul interior si gradul exterior. Daca gasim o persoana pentru care out = 0 si in = n-1, aceasta va fi celebritatea cautata.

celebritate := 0;

for p := 1 to n do

begin

in := 0; out := 0;

for j := 1 to n do

begin

in := in+aj,p

out := out+ap,j

end;

if (in = n-1) and (out = 0) then celebritate := p;

end;

if celebritate = 0 then

writeln('In grup nu exista celebritati !')

else

writeln(p, ' este o celebritate.');

Se poate observa cu usurinta ca algoritmul este de O(n ). Putem imbunatati algoritmul facand observatia ca atunci cand testam relatiile dintre persoanele x si y apar urmatoarele posibilitati :

ax,y = 0 si in acest caz y nu are nici o sansa sa fie celebritate, sau

ax,y = 1 si in acest caz x nu poate fi celebritate.

Deci la un test eliminam o persoana care nu are sanse sa fie celebritate. Facand succesiv n-1 teste, in final vom avea o singura persoana candidat la celebritate. Ramane sa calculam numarul de persoane cunoscute si numarul de persoane care il cunosc pe acest candidat, singura celebritate posibila.

candidat := 1;

for i := 2 to n do

if acandidat, i = 1 then

candidat := i;

out := 0; in := 0;

for i := 1 to n do

begin

in := in+ai, candidat

out := out+acandidat, i

end;

if (out = 0) and (in = n-1) then

writeln(candidat, ' este o celebritate .')

else

writeln('Nu exista celebritati in acest grup.');

In acest caz algoritmul a devenit liniar.

9.4. Exercitii

1. Aratati ca :

a) n n (n

_{b) n}2ⁿ ₊₆ ⁿ_(n2ⁿ₎

c) 2n +n logn(n

d) n^k+n+n^klogn(n^k log n), k

e) log_an(log_bn), a, b > 0, a 1, b

2. Demonstrati prin inductie ca pentru a determina maximul a n numere sunt necesare n-1 comparatii.

3. Care este timpul de executie a algoritmului quicksort pentru un vector cu n componente egale?

4. Sa consideram urmatorul algoritm de sortare a unui vector a cu n componente:

repeat

ok := true;

for i := 1 to n-1 do

if ai > ai+1 then

begin

aux := ai

ai := ai+1

ai+1 := aux;

ok := false

end

until ok;

Analizati algoritmul in medie si in cazul cel mai defavorabil.

5. Analizati complexitatea algoritmului de interclasare a doi vectori ordonati, a cu n componente, respectiv b cu m componente :

i := 1; j := 1; k := 0;

while (i n) and(j m) do

begin

k := k+1;

if ai < bj then

begin

ck := ai

i := i+1

end

else

begin

ck := bj

j := j+1

end;

end;

for t := i to n do

begin

k := k+1;

ck := at

end;

for t := j to m do

begin

k := k+1;

ck := bt

end;

6. Fiind dat a, un vector cu n componente distincte, verificati daca o valoare data x se gaseste sau nu in vector. Evaluati complexitatea algoritmului in cazul cel mai defavorabil si in medie.

7. Problema turnurilor din Hanoi.

Avem la dispozitie 3 tije numerotate 1, 2, 3 si n discuri de diametre diferite. Initial, toate discurile sunt plasate pe tija 1 in ordinea descrescatoare a diametrelor, considerand sensul de la baza la varf. Problema consta in a muta discurile de pe tija 1 pe tija 2, folosind ca tija de manevra, tija 3, respectand urmatoarele reguli :

- la fiecare pas se muta un singur disc;

- orice disc nu poate fi asezat decat peste un disc cu diametru mai mare.

Aceasta problema a fost propusa la sfarsitul secolului trecut de catre matematicianul francez Eduard Lucas, care a comercializat-o sub forma unui joc cu 8 discuri si 3 baghete numit 'Turnul din Hanoi'. Jocul este inspirat dintr-o straveche legenda hindusa, dupa care zeul Brahma ar fi fixat pe o masa a templului sau din Benares 3 baghete verticale de diamant, pe una din ele plasand 64 de discuri de aur in ordinea descrescatoare a diametrelor. Zi si noapte calugarii templului mutau discuri de pe tija 1 pe tija 2, folosind ca tija de manevra tija 3, respectand ordinea descrescatoare a diametrelor. Legenda spune ca atunci cand toate discurile vor fi mutate va fi "sfarsitul lumii".

Scrieti un algoritm de rezolvare a problemei turnurilor din Hanoi si estimati complexitatea acestuia. Estimati, in particular, durata legendara a vietii pe Pamant.

8. Se da a un vector cu n componente. Scrieti un algoritm liniar care sa determine cea mai lunga secventa de elemente consecutive de valori egale.

9. Fie T un text. Verificati in timp liniar daca un text dat T este o permutare circulara a lui T.

10. Fie X = x₁, x₂, , x_n o secventa de numere intregi. Fiind dat x, vom numi multiplicitate a lui x in X numarul de aparitii ale lui x in X. Un element se numeste majoritar daca multiplicitatea sa este mai mare decat n/2. Descrieti un algoritm liniar care sa determine elementul majoritar dintr-un sir, daca un astfel de element exista.

11. Fie si , doua multimi de numere intregi, nenule (m < n). Sa se determine , o submultime a multimii pentru care functia f(x , x , , x_m) = a x +a x +a_nx_m ia valoare maxima, prin doi algoritmi de complexitate diferita.