• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Analiza algoritmilor

9
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 18 iul., 2009 at 1:21 pm

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 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. 😉

Etichete: analiza algoritmilorliniaritatelogaritmnotatia asimptoticasortaresortarea selectiva

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Office 2010 Free
  • Articolul următor Calcularea CMMDC si a CMMMC

9 Comentarii

  1. miculprogramator spune:
    iulie 18, 2009 la 6:09 pm

    Deci Bubble sort are O(n^2) si QuickSort are (n*log n). QSort este defavorabila si BSort este favorabila?

  2. Avadanei Andrei spune:
    iulie 18, 2009 la 6:20 pm

    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. 😀

  3. miculprogramator spune:
    iulie 19, 2009 la 10:04 am

    Per total..:|

  4. Nytro spune:
    iulie 20, 2009 la 11:37 am

    Fa si tu analiza concentratiei de alcool din bauturi 🙂

  5. Leocrux spune:
    iulie 20, 2009 la 3:05 pm

    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:)

  6. Avadanei Andrei spune:
    iulie 20, 2009 la 3:11 pm

    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. 😀

  7. Byby spune:
    decembrie 10, 2009 la 7:06 pm

    sincer nu am intzeles nimik si maine am teza:P:P:Pdeci sunt varza….:P

  8. Best4him spune:
    octombrie 19, 2010 la 10:25 pm

    imi pare bine ca am gasit sit-ul asta! Multumesc pentru articole! Chiar explici bine!

  9. Gabriel spune:
    iulie 18, 2012 la 9:57 pm

    ” vectorului in doua vectori mai” – your argument is now invalid :).


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • iunie 2022
    L Ma Mi J V S D
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Analiza algoritmilor
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons