Eficiența algoritmilor
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 și cerințele originale de te timp și spațiu (în general în Notație asimptotică) ale algoritmului. Fie și timpul și respectiv spațiul necesare pentru noul cod. Dacă , 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.