Questa voce sull'argomento teorie dell'informatica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia.

In informatica, si intende per "efficienza" la capacità di un software (in particolare di un algoritmo) di utilizzare meno risorse informatiche possibile durante la sua esecuzione. Principalmente vengono considerati solo due fattori:

• Il tempo di utilizzo della CPU
• Lo spazio occupato dal programma e dai dati in memoria

L'altro fattore, spesso non dipendente dalla programmazione del software, sono i tempi di latenza delle periferiche, in particolare dell'hard disk. Questo tempo può essere ridotto da minori accessi da parte del programma (utilizzando ad esempio sistemi cache), ma molto spesso è influenzato dall'hardware sotto il quale viene eseguito il programma.

Nell'analisi di un algoritmo viene spesso lasciata in secondo piano l'analisi dell'utilizzo di memoria^[1], mentre viene principalmente studiata la complessità computazionale. Questo avviene grazie all'utilizzo delle notazioni asintotiche, in particolare O-grande che rappresenta il massimo tempo (o spazio) impiegato dal programma a meno di una costante.

Lo stesso argomento in dettaglio: NP-Completo.

I problemi NP (in particolari NP-Completi) non sono ancora stati risolti in tempo polinomiale e non si conosce se è possibile farlo^[2]. L'utilizzo di algoritmi sempre più vicini a una soluzione non esponenziale sono fondamentali per quei software che utilizzano problemi così complessi. Sono molto più frequenti di quanto si pensi, per esempio il problema dello zaino è alla base dei nostri navigatori satellitari.

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica