Complexitatea algoritmilor

Analiza algoritmilor

Adeseori in programare, elaborarea unui algoritm care rezolva o anumita problema nu este privita ca o reusita deplina. De foarte multe ori se pune problema analizei performantelor algoritmului creat: portabilitatea pe diferite sisteme, complexitatea si nu in ultimul rand, eleganta si simplitatea.

Complexitatea este masura prin care un algoritm poate fi evaluat, in vederea compararii sale cu alti algoritmi care rezolva aceeasi problema. Scopul evaluarii complexitatii este acela de a oferi o informatie despre performantele unui algoritm inainte de a-l transpune intr-un limbaj de programare si fara a tine cont de particularitatile setului de date de intrare. Altfel, odata creata o implementare, pe baza ei nu se vor putea analiza decat performantelor pentru anumite seturi de intrare, date particulare, nepermitand o generalizare asupra comportamentului algoritmului in cauza pentru orice set de date de intrare.

Evaluarea complexitatii

Evaluarea complexitatii unui algoritm presupune, pe de o parte, estimarea volumului suplimentar de memorie utilizata, si pe de alta parte, estimarea timpului de calcul necesar executiei.

Dimensiunea problemei

Cele doua masuri ale complexitatii (memoria suplimentara si timpul de calcul) sunt dependente de dimensiunea n a problemei, adica de marimea datelor ce trebuie prelucrate (datele de intrare) si, deci, vor fi exprimate in functie de aceasta. De exemplu, in algoritmii de prelucrare a masivelor de date (cum ar fi determinarea minimului sau maximului, cautare, sortare samd.), memoria suplimentara si timpul de calcul sunt exprimate in functie de dimensiunea masivului, in algoritmii dedicati verificarii unor proprietati ale numerelor naturale (numar prim, perfect samd.), dimensiunea problemei este chiar numarul analizat.

Timpul de calcul

Precizarea timpului de calcul se realizeaza prin estimarea numarului de operatii executate de algoritm in cazul unui set de date de intrare. Asa cum vom vedea, alegerea volumului datelor de intrare si a naturii lor nu este deloc arbitrara.

Pentru ilustrarea procedeului de numarare a operatiilor executate, sa consideram problema determinarii maximului unui masiv de volum n. Avem asadar o problema de dimensiune n, ce poate fi rezolvata cu urmatorul algoritm:

Algoritmul nu necesita memorie suplimentara semnificativa (variabila MAX nu prezinta interes). Pentru evaluarea complexitatii sale ne ramane de estimat numarul de operatii ce se executa. In acest sens, vom construi schema logica a acestui algoritm si vom marca pe arcele sale numarul de executii ale fiecarui pas in parte. Se va avea in vedere faptul ca numarul intrarilor unui nod trebuie sa fie egal cu numarul iesirilor (de cate ori se incepe o operatie, ea se si termina, algoritmul nu se opreste in mijlocul executiei), regula numita "prima lege a lui Kirchhoff".

Fig. III . Numarul de executii ale operatiilor

Avem asadar ca:

Tabel III . Numarul de executii

Pasul P4, actualizarea variabilei MAX, are loc numai atunci cand valoarea curenta a sa este mai mica decat elementul curent din vector. Pentru ca nu se cunoaste setul de date de intrare, numarul de executii ale acestui pas nu va putea fi evaluat aprioric, insa se va face o estimare a sa.

Operatia de baza

Fiecare operatie efectuata presupune o anumita durata de executie dependenta de mai multi factori, cum ar fi complexitatea articolelor si a cheilor dupa care determinam maximul, in exemplul nostru. Din acest motiv, in practica, se alege cea mai semnificativa operatie specifica problemei ce trebuie rezolvata, numita operatie de baza, a carei numar de executii poate fi evaluat in functie de n (dimensiunea problemei).

Asadar, daca alegem ca operatie de baza comparatia ce implica elemente ale masivului (pasul 3: comparatia repetata intre elementul curent al masivului si MAX), atunci vom sti ca pentru un vector de intrare de volum n sunt necesare n-1 comparatii, datorate parcurgerii masivului pana la capat.

Pe de alta parte, daca, spre exemplu articolele masivului au o structura complexa, atunci copierea lor in variabila MAX va fi operatia semnificativa (de baza) si in acest caz vom fi nevoiti sa estimam numarul de executii ale atribuirii de la pasul 4. Aceasta deoarece numarul de executii nu poate fi determinat aprioric, el depinde de organizarea datelor de intrare, iar aici intervine teoria probabilitatilor.

Timpul maxim, minim, mediu

Pentru evaluarea numarului de executii ale atribuirii se pot utiliza trei masuri: timpul minim (prezinta mai putin interes in practica), obtinut in cazul cel mai optimist, timpul maxim, obtinut in cazul cel mai defavorabil, si timpul mediu, pentru care se iau in calcul toate situatiile posibile.

In problema amintita mai sus, in cel mai bun caz maximul este se afla pe prima pozitie in masiv, ceea ce inseamna ca nu se efectueaza nici o atribuire la pasul 4. Cazul cel mai defavorabil corespunde situatiei in care elementele masivului sunt ordonate crescator, cand determinarea maximului presupune efectuarea a n-1 atribuiri succesive. Pentru timpul mediu se iau in calcul toate cele n! ordonari posibile ale elementelor in vector (diferite ordonari ale unui vector sunt practic permutari ale elementelor sale) si se alcatuieste o medie.

Pentru exemplificare, sa consideram situatia in care n=3. Avem urmatoarele sase ordonari posibile (presupunem ca elementele masivului sunt distincte):

Tabel III . Ordonari posibile ale elementelor masivului

Vom avea, asadar, (2+1+1+0+1+0)/6=5/6 atribuiri.

In general, timpul mediu de executie este:

unde k sunt valorile posibile ale numarului de executii, iar p(n,k) este probabilitatea de realizare. In exemplul de mai sus, avem: p(3, 0)=2/6=1/3; p(3,1)=3/6=1/2; p(3,2)=1/6. Este evident ca: _.

I.1          Ordinul timpului de executie

In scopul evaluarii timpului de calcul asociat unui algoritm, ajungem sa exprimam numarul de executii ale unei operatii (operatia de baza) in functie de dimensiunea n a problemei.

Fie T(n) timpul necesitat de un algoritm. Daca exista o functie f si doua constante C₁ si C₂, astfel ca, incepand de la un n₀ cunoscut, sa avem relatia:

,

atunci vom spune ca algoritmul are complexitatea O(f(n)).

De exemplu, daca intr-un algoritm se executa o operatie de ori, cum:

,

va rezulta ca algoritmul este de complexitate O(n²).

Trebuie remarcat ca prin aceasta notatie sunt neglijate constantele.

Dupa forma functiei f(n), se disting doua clase importante de algoritmi:

polinomiali de ordin k (in timp polinomial) daca algoritmul este de complexitate O(n^k).

In particular, daca k este 1, atunci avem un algoritm liniar. De exemplu, algoritmul de determinare a maximului unui masiv (considerand ca operatie de baza comparatia). Se scrie O(n).

exponentiali de ordin k, daca algoritmul este de complexitate O(kⁿ).

In aceasta categorie intra si algoritmii carora li se asociaza un timp O(n!), de exemplu, asa cum vom vedea mai tarziu, problemele de Backtracking necesita timpi de calcul de ordin exponential.

Algoritmii exponentiali sunt acceptati in practica numai si numai atunci cand nu exista alternative de rezolvare, aceasta datorita timpului mare de calcul, chiar si pentru valori relativ mici ale dimensiunii problemei. De exemplu, problema generarii tuturor submultimilor unei multimi cu n elemente are asociat un timp exponential de ordin 2: O(2ⁿ). Aceasta presupune efectuarea a 2¹⁰=1024 operatii de baza pentru o problema de dimensiune n=10. Pentru o problema cu numai o unitate mai mare, numarul de operatii de baza se dubleaza: 2¹¹=2(2¹⁰)=2*1024. Pentru n dublat, n=20, vom avea 2²⁰=(2¹⁰)²=1024²=1048574, peste 1000 de ori mai multe decat pentru n=10.

Rezulta de aici importanta analizei timpului de calcul -chiar si in generatia calculatoarelor extrem de performante!- si evitarea, acolo unde este posibil, a algoritmilor exponentiali. Adeseori in practica, atunci cand se doreste rezolvarea in timp util a unei probleme ce necesita timpi exponentiali, se recurge la diferite compromisuri, cum ar fi renuntarea la optimalitatea solutiei.