Eficienta agloritmilor si optimizarea lor

Eficienta agloritmilor si optimizarea lor

       Optimizarea este procesul prin care un algoritm devine cât mai eficient posibil, de cele mai multe ori punându-se accent pe timpul de executie, dar si pe spatiul ocupat de acesta.
Numim un algoritm eficient atunci cand numarul de pasi pentru a-l finaliza este redus la valoarea cea mai mica, acest lucru micsorand timpul de executie.

 

       
       Stim deja ca un algoritm trebuie sa posede urmatoarele proprietati:
  • Generalitate – un algoritm destinat rezolvarii unei probleme trebuie sa permita obtinerea rezultatului pentru orice date de intrare nu numai pentru valori particulare ale acestora
  • Finitudine – un algoritm trebuie sa admita o descriere finita si fiecare dintre prelucrarile pe care le contine trebuie sa poata fi executata in timp finit. Prin intermediul algoritmilor nu pot fi prelucrate structuri infinite.
  • Rigurozitate – prelucrarile algoritmului trebuie specificate riguros, fara ambiguitati. In orice etapa a executiei algoritmului trebuie sa se stie exact care este urmatoarea etapa si cum poate fi executata aceasta.
  • Eficienta – algoritmii pot fi efectiv utilizati doar daca folosesc resurse de calcul in volum acceptabil. Resursele de calcul se refera la spatiul necesar stocarii datelor si timpul necesar executiei prelucrarilor.Pentru a optimiza un program si a-l face sa ruleze mai eficient trebuie sa reducem ordinul de complexitate fara a altera functiile programului:
  •      Un bun exemplu aici ar fi inlocuirea lui for cu while, deoarece, in bucla lui for instructiunea este repetata de un numar de ori impus de noi, spre deosebire de while, unde bucla este intrerupta imediat ce algoritmul ajunge la rezultatul final:
  •  While este mai eficient decat do while deoarece testeaza conditia la inceputul algoritmului, iar daca aceasta este falsa nu intra in bucla.
  • De asemenea, utilizarea functiilor recursive sporeste cu mult eficienta unui program si micsoreaza timpul de executie.
  • Folosirea sintaxei if in programele nerecursive reprezinta de cele mai multe ori o alegere ineficienta, irosindu-se astfel mai multa memorie si lungind timpul de executie al programului.
Exemplu:
if (conditie1)            if (conditie1 || conditie2)
executa actiune;          executa actiune;
    else 
if (conditie2)
executa actiune;

O tehnica foarte cunoscuta si utilizata de programatori este metoda backtracking, aceasta fiind folosita pentru a solutiona o problema atunci cand nu stim cu ce sa incepem; algoritm ce ia la rand fiecare posibilitate pentru a solutiona problema si care afiseaza rezultatul corect odata obtinut.  O putem numi o metoda buna din punct de vedere al rezolvarii problemei, dar una ineficienta d.p.d.v al eficientei si timpului de executie.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s