Analiza algoritmilor

Analiza unui algoritm a ajuns sa insemne prevederea resurselor pe care algoritmul le solicita.Uneori, resursele de memorie sunt prima preocupare,dar,de cele mai multe ori, dorim sa masuram timpul de executie necesare algoritmului.Uneori analizand mai multi algoritmi pentru o anumita problema , cel mai eficient poate fi identificat usor.O astfel de analiza poate indica mai multi candidati ce rezolva problema,dar cativa algoritmi inferiori sunt , de obicei, eliminati in timpul analizei.

Inainte de a analiza un algoritm ,trebuie sa avem un model al tehnologiei de implementare care urmeaza sa fie folosita , incluzand un model pentru resursele acesteia si costurile corespunzatoare. Vom presupune ca tehnologia in care sunt implementate exemplele este un model de calcul generic cu un singur procesor (random-access machine,RAM) si vom presupune ca algoritmii sunt implementati ca programare pentru calculator.

Desi, pentru a analiza un algoritm, selectam numai un tip de model de masina de calcul, raman mai multe posibilitati de alegere a felului in care decidem sa exprimam aceasta analiza.Primul lucru ce trebuie facut este de a gasi un mijloc de exprimare care sa fie simplu de scris si de manevrat,care sa arate principalele resurse necesare unui algoritm si sa elimine detaiile inutile. 😀

In acest tutorial ne vom ajuta de sortarea unui vector si doua metode de a face asta ce vor fi analizate independent.

Metoda bubble sort

      void bubble(int a[],int n)
      {
          int i,schimbat,aux;
          do
          {
             schimbat = 0;
             for(i = 0; i < n-1; i++)  
               if(a[i] < a[i+1])                                   
               {                          
                  aux = a[i];
                  a[i] = a[i+1];
                  a[i+1] = aux;
                  schimbat = 1;     
               }
          }while(schimbat);
      }

Metoda Quicksort

void qSort(int vector[],int st,int dr)
{
   int temp,min,max,mijl;
   
   mijl = vector[st+(dr-st)/2];              
   min = st; max = dr;
   do
   {
        while(vector[min] < mijl) min++;   
        while(vector[max] > mijl) max--;  
        if(min < = max)                       
        {
            temp = vector[min];
            vector[min++] = vector[max];
            vector[max--] = temp;   
        }
    }while(min <= max);  

    if(st < max) qSort(vector,st,max);  
    if(dr > min) qSort(vector,min,dr); 
}

Definitia dimensiunii datelor de intrare depinde de problema studiata.Pentru multe probleme precum sortarea unui vector, dimensiunea datelor de intrare este data de exemplu de un vector de dimensiune n.Pentru alte probleme spre exemplu inmultirea a doua numere cea mai buna metoda pentru reprezentarea dimensiunii datelor de intrare reprezinta numarul total de biti necesari pentru a reprezenta in format binar datele de intrare.Uneori , pentru a reprezenta datele de intrare e bine sa folosim doua numere in loc de unu.Spre exemplu cand avem o problema ce avem nevoie de o matrice avem nevoie de dimensiunile matricii n si m si astfel vom avea ca date de intrare m*n elemente(puse intr`un vector). In general se poate stabili destul de usor la cine fac referire dimensiunile datele de intrare.

Timpul de executie a unui algoritm pentru un anumit set de date de intrare este determinat de numarul de operatii sau „pasi” executati. In analiza noastra vom considera faptul ca orice linie de cod se executa intr-un timp constant t_i unde t_i este constant.Aceasta intelegerea este in perfecta intelegere cu modelul RAM si poate fi extrem de usor reprezentata atunci cand analizam si un algoritm in pseudocod.

Timpul de executie al unui algoritm in cazul cel mai defavorabil este o marginire superioara a timpului de executie pentru orice date de intrare de dimensiune fixa.Cunoscand aceasta bariera putem fi siguri ca niciodata algoritmul nu va depasi aceasta bariera si se va comporta in cea mai rea situatie intr`un caz cu un timp asemanator de cazul defavorabil.

Cazul mediu este aproape la fel de defavorabil ca si cazul cel mai defavorabil.In aceasta situatie consideram valorile datelor de intrare avand o probabilitate medie de a atinge timpul de executie in cazul cel mai defavorabil si in aceasta situatie algoritmul se comporta in situatia si timpului mediu.

Ordinul de crestere sau rata de crestere reprezinta o abstractizare simplificatoare.Aceasta caracteristica ne ofera posibilitatea de a compara performantele relative ale unor algoritmi alternativi. Un algoritm cu rata de crestere n^2 este mult mai lent ca unul cu rata de crestere n sau log n pe cand un algoritm cu rata de crestere n^3 este mai lent ca unul cu ordinul de crestere n^2.In general pe cazurile mici diferentele sunt aproape nesemnficative insa la valori si dimensiuni mare ale lui n aceste diferente sunt vizibile 🙂

Cand examinam date de intrare de dimensiuni suficient de mari , astfel incat numai ordinul de crestere a timpului de executie sa fie relevant spunem ca studiem eficienta asimptotica a algorimilor.

Notatia O delimiteaza o functie asimptotic inferior si superior.Vom utiliza O-notatia pentru a indica o margine superioara a unei functii pana la un factor constant.De exemplu vom folosi notatia O(n^2) pentrua reprezenta un algoritm ce se executa la limita n in timp patratic si un algoritm de tipul divide si cucereste in timp logaritmic pentru fiecare element deci vom avea o notatie O(n*log n).

Sa incepem analiza primului algoritm,cel prin metoda Bubble Sort:

do
 {
          schimbat = 0;                //c1 n ori
          for(i = 0; i < n-1; i++)     //c2 n-1 or
           if(a[i] < a[i+1])             //c3 n-1 ori                      
           {                          
               aux = a[i];               //c4 n-1 ori
               a[i] = a[i+1];           //c5 n-1 ori
               a[i+1] = aux;           //c6 n-1 ori
               schimbat = 1;          //c7 n-1 ori
           }
      }while(schimbat);              //c8 n ori
}

Insumand si reducand costurile obtinem faptul ca acest algoritm se executa in cazul cel mai defavorabil in O(n*(n-1)) cand toate elementele trebuie sortate in ordine inversa.Abstractizand putem spune ca algoritmul are ca timp de executie O(n^2) sau "complexitate patratica".
Pentru a calcula numarul de operatii necesare algoritmului pentru orice n putem calcula stiind ca avem 8 operatii cu diferite costuri,aceste costuri le putem considera S = c1 + c2 + .. c8,reprezentand durata unei parcurgeri totale ale algoritmului. Putem spune ca Bubble Sort executa n^2*S operatii sau ca are un timp de executie de n^2*S daca S = timpul pentru executarea celor 8 operatii.O aproximare mai exacta ar spune faptul ca bubble sort are n^2*S-(c4+c5+c6+c7) pasi,daca refuzam abstractizarea facuta mai devreme.
Cazul mediu al acestui algoritm se poate calcula usor.Observam faptul ca loop`ul principal(while) se executa atat timp cat mai sunt elemente de sortat.De aici putem calcula faptul ca acest loop se executa de T`ori unde T reprezinta numarul de numere ce nu au fost sortate inca.Putem spune ca bubble sort are complexitatea medie O(n*T).Acest algoritm este mai rapid spre exemplu ca sortarea selectiva unde cei n^2 pasi se executa indiferent de situatie.Deci putem spune ca acesta este unul dintre cei mai rapizi algoritmi din clasa O(n^2). 😀

Sa incercam sa analizam QuickSort.
Observam ca algoritmul se bazeaza pe o procedura ce incearca partitionarea vectorului in doua vectori mai mici,procesul repetandu-se pana cand vectorul este intreg sortat.Algoritmul incearca ca la fiecare partitionare sa aduca elementele mai mici ca valoare de partitionare in partea stanga si cele mai mari in partea dreapta(aceasta situatie doar cand incercam sa sortam crescator).Dar pentru a aduce toate elementele din partea dreapta in partea stanga si invers este necesar un timp patratic cand toate valorile sunt puse spre exemplu descrescator.Astfel avem n/2 pasi pentru a munta fiecare element din prima jumatate in a doua => n*n/2 pasi pentru a muta toate elementele.Datorita faptului ca algoritmul este baza tehnicii divide si cucereste impartirea are loc pana intreg vectorul este sortat.Acum avem 2 jumatati ce trebuie din nou sortate.Aceasta situatie aduce algoritmul in cazul cel mai defavorabil in complexitate patratica : O(n^2).O alta situatie cand complexitatea este in cazul cel mai defavorabil este cazul in care impartirea este dezechilibrata : un vector de n-1 elemente si unul de 1 element.Este necesara imparirea echilibrata si producerea noilor vector injumatatiti pentru a se ajunge la cazul cel mai favorabil. Daca elementele au o probabilitate medie de a fi in ordine opusa acest algoritm produce o complexitate logaritmica : O(n*log n). Aceasta solutie este complexitatea in cazul cel mai favorabil,ce deseori este atinsa de acest algoritm,datorita si numarului mic de pasi necesari cat si a probabilitatii mici ca valorile sa se afle intr`o situatie ce produce cazul defavorabil.

In acest articol am incercat sa explic putin cum se calculeaza timpul de executie.Daca inca aveti neclaritati nu ezitati sa le puneti, si voi incerca sa le dezbatem impreuna. 😉