Efficienza (informatica)

capacità di utilizzare meno risorse informatiche possibile durante la sua esecuzione

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.

L'analisi di un algoritmo

modifica

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.

Problemi "difficili"

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

  1. ^ Introduzione agli algoritmi e strutture dati, McGraw-Hill, 2009.
  2. ^ Problema del millennio P=NP? Archiviato il 14 ottobre 2013 in Internet Archive.
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica