Eficienţa algoritmilor
De la Wikipedia, enciclopedia liberă
Alte formulări: eficienţa algoritmică, analiza complexităţii algoritmilor.
În informatică, eficienţă este un termen utilizat pentru a descrie câteva atribute dezirabile ale unui algoritm sau al unui alt construct, în afara unui concept curat, a funcţionalităţii, etc. Eficienţa în general e conţinută în două proprietăţi: viteză (timpul cât îi ia unei operaţii până se încheie), şi spaţiu (memoria sau depozitul nevolatil utilizat de către construct). Optimizarea este procesul prin care se produce cod care este cât mai eficient posibil, câteodată accentul punându-se pe spaţiu în detrimentul vitezei, sau viceversa.
Viteza unui algoritm este măsurată în diverse moduri. Cea mai simplă metodă utilizează complexitatea în timp pentru a determina Ordinul unui algoritm: de multe ori, este posibilă realizarea unui algoritm mai rapid în detrimentul spaţiului utilizat. Acesta este şi cazul când reutilizezi rezultatele unui calcul intensiv decât să le obţii prin recalculare la comandă. Aceasta este şi o metodă foarte obişnuită de a creşte viteza, chiar într-atât încât limbajele adaugă de obicei elemente speciale pentru a o facilita, cum ar fi în C++ cuvântul cheie "mutable" (în engleză).
Spaţiul unui algoritm este de fapt alcătuit din două lucruri separate dar în legătură. Prima parte este spaţiul pe disc (sau echivalentul acestuia, depinzând de hardware şi limbaj) ocupat de către executabilul compilat din codul sursă reprezentare a algoritului. În multe cazuri acesta poate fi redus dacă se preferă mecanisme de decizie în momentul execuţiei (cum ar fi funcţii virtuale şi informaţia de tip la rulare) în dauna anumitor mecanisme de luare a deciziei în momenul compilării (cum ar fi macro substituţia şi şablon). Oricum, costul acestor operaţii va fi reflectat în viteza de execuţie.
Cealaltă parte măsurată a spaţiului unui algoritm este cantitatea de memorie alocată temporar în timpul procesării. De exemplu, rezultatele precalculate, cum a fost menţionat anterior, îmbunătăţesc viteza în dauna acestui atribut (creşte necesarul de memorie temporară alocată).
Optimizarea algoritmilor depinde în mod frecvent de proprietăţile maşinii pe care algoritmul va fi executat. De exemplu, cineva ar putea optimiza cod pentru eficienţă în domeniul timp în aplicaţii pentru calculatoare personale cu cantităţi apreciabile de memorie, în acelaşi timp cod ce trebuie introdus în dispozitive mici şi cu puţină memorie la dispoziţie probabil va trebui făcut să funcţioneze mai lent pentru a economisi spaţiu.
O modalitate simplă de a afla dacă merită încercată optimizarea este următoarea: Fie O1 şi O2 cerinţele originale de te timp şi spaţiu (în general în Notaţie asimptotică) ale algoritmului. Fie N1 şi N2 timpul şi respectiv spaţiul necesare pentru noul cod. Dacă N1N2 < O1O2, ar trebui îndeplinită operaţiunea de optimizare. Oricum, a fost menţionat anterior, s-ar putea să nu fie întotdeauna cazul, iar această metodă empirică poate da greş.
Trebuie acordată o atenţie sporită ca nu cumva , în goana după un stil adecvat de editare a codului sursă, să fie eclipsată eficienţa. Aproape tot timpul, un concept curat şi utilizabil e mult mai important decât un concept mic, rapid. Există excepţii la această regulă (cum ar fi sistemele integrate, unde spaţiul este strâns, şi puterea de procesare minimă) dar acestea sunt mai rare decât s-ar putea aştepta cineva.
