Analiza algoritmilor
9Analiza 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 ti unde ti 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. 😉
Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!
Deci Bubble sort are O(n^2) si QuickSort are (n*log n). QSort este defavorabila si BSort este favorabila?
Nu.Este exact invers.Uite sa luam doua exemple concrete.Sa zicem ca avem 1000 de elemente.
1000*1000 = 1.000.000(1 milion de pasi).
1000*10 = 10.000 (10 mii de pasi).
Log2 n este Logaritm in baza 2(deoarece avem injumatatiri repetate).Logaritmul unui numar n intr`o baza b este un numar k, astfel incat k*b = n. (aproximativ egal cu n).
Log2 100 = 6
Log10 1000 = 3
Sper ca ai inteles. 😀
Per total..:|
Fa si tu analiza concentratiei de alcool din bauturi 🙂
Excelent! am inteles tot:D si chiar azi cautam ceva despre analiza algoritmilor, si nu stiu ce mia venit sa intru pe WorldIT, si am vazut asta :))
Insa la partea cu logaritmul m-am imbarligat:|
Din cate stiu eu(wikipedia), logaritmul este o putere la care trebuie ridicata baza pt a obtine un numar dat.
b^n=k => Log in baza b de k = n, adica la ce putere trebuie ridicat b ca sa obtinem k.
insa in Log2 100 = 6, 2^6=64 nu 100 😐
Oricum felicitari pentru tutorial:)
Corect.Insa ar trebui un numar real si din dorinta de a simplifica tot cel mai apropiat numar era defapt Log2 100 este aproximativ 7.Mi-a scapat atunci la simplificari :”> . Multumesc de observatie si ma bucur ca a fost pe intelesul tau.
Practic numarul de impartiri repetate simuleaza aflarea logaritmului (in cazul actual al logaritmului in baza 2) datorita faptului ca noi incercam sa facem injumatatiri pe vectorul in cauza. 🙂
P.S : Nu ezita sa mai intri din cand in cand.Vor aparea o serie de articole atat pentru incepatori cat si pentru cei avansati in ultima perioada , odata cu noii pasionati de IT ce au intrat in echipa WorldIT. 😀
sincer nu am intzeles nimik si maine am teza:P:P:Pdeci sunt varza….:P
imi pare bine ca am gasit sit-ul asta! Multumesc pentru articole! Chiar explici bine!
” vectorului in doua vectori mai” – your argument is now invalid :).