Complessità algoritmo
La complessità dell'algoritmo consiste nell'effettiva applicazione dell'algoritmo per la soluzione di problemi pratici, sia in termini di consumo di risorse macchina ( es. memoria ) che di tempo di elaborazione necessario per giungere al risultato finale.
I limiti della computazione ottimale e completa
La complessità è di fondamentale importanza in campo informatico e nello studio degli algoritmi degli agenti razionali. Un algoritmo è efficace quando trova la migliore soluzione ( ottimalità ) analizzando tutte le possibili soluzioni di un problema ( completezza ).
In questo caso l'algoritmo è completo e ottimale ma non è detto che sia anche fattibile e utilizzabile ( utilità ). Per valutare l'utilità occorre considerare la quantità di memoria necessaria per il calcolo e il tempo di esecuzione dell'elaborazione.
Ad esempio, il tempo di elaborazione è fondamentale nei sistemi di guida automatica di un veicolo con un dispositivo di intelligenza artificiale. Le decisioni dell'agente razionale devono essere efficaci ma anche rapide, quasi istantanee. Un algoritmo troppo lento, seppure efficace e ottimale nella capacità di trovare le soluzioni, è del tutto inutile all'atto pratico.
L'algoritmo potrebbe anche richiedere una quantità di memoria eccessiva, tale da rendere impossibile la sua esecuzione.
Ad esempio, un algoritmo sviluppato con la tecnica delle tabelle può essere usato per risolvere il gioco del tris ma è praticamente impossibile da utilizzare in un sistema di guida automatica, in quanto la capacità di memoria necessaria è notevolmente superiore a quella offerta dalla tecnologia esistente ( es. dispositivi di memoria hardware )..
Le tipologie di complessità computazionale
È possibile distinguere le seguenti tipologie di complessità dell'algoritmo:
- Complessità temporale. La complessità temporale è il tempo di elaborazione necessario all'algoritmo per giungere alla soluzione del problema. È solitamente misurata in secondi, minuti, ore e, in alcuni casi complessi, anche settimane e mesi.
- Complessità spaziale. La complessità spaziale è la quantità di risorse necessarie all'algoritmo per l'elaborazione. È solitamente misurata in termini di byte di memoria necessari per memorizzare le informazioni temporanee nel corso dell'esecuzione dell'algoritmo.
