Definizione di Complessità Computazionale di un Algoritmo

Definizione di Complessità Computazionale di un Algoritmo

Dato un problema, è possibile determinare un insieme, generalmente finito, di algoritmi in grado di risolverlo. La scelta di un algoritmo piuttosto che un altro può essere basata su differenti fattori. Ad esempio il tempo di esecuzione, le risorse necessarie alla sua esecuzione, etc. Tra essi, quello che gioca un ruolo essenziale è la complessità computazionale, che può essere misurata come tempo necessario all’esecuzione dell’algoritmo su un computer di architettura tradizionale.

La valutazione della complessità computazionale deve soddisfare due requisiti:

  1. Non deve dipendere da una particolare macchina o da un particolare compilatore. Ciò è richiesto in quanto:
    1. Il tempo di esecuzione di ogni istruzione in un qualunque linguaggio (ad esempio in linguaggio macchina), non è uguale per tutti i calcolatori ma varia in dipendenza ad esempio della frequenza di lavoro della CPU (clock), dall’architettura del calcolatore o dal set di istruzioni di cui la macchina dispone (ad esempio la decodifica di ogni singola istruzione prima della sua esecuzione, è più rapida in una macchina che usa un set limitato di istruzioni, ossia in una macchina RISC).
    2. Il numero di istruzioni in linguaggio macchina che vengono generate in corrispondenza ad un programma scritto in un linguaggio ad alto livello, dipende dal particolare compilatore. È possibile dunque che uno stesso programma venga tradotto in programmi in linguaggio macchina di lunghezza (ossia numero di istruzione) differenti.
  2. Deve essere espressa in funzione dei dati in ingresso. Dato che un algoritmo elabora dei dati in ingresso per fornirne altri che rappresentano la soluzione del problema, quello che interessa sapere è come il tempo di esecuzione dell’algoritmo varia al variare dei dati in ingresso. In particolare, la dipendenza del tempo di esecuzione dai dati in ingresso al problema può essere relativa sia alla dimensione dei dati in ingresso che al loro valore.
    1. Dipendenza dalla Dimensione dei Dati. La complessità computazionale di un algoritmo dipende sempre dal numero dei dati che devono essere elaborati dall’algoritmo, ossia dai dati in ingresso. Tale numero viene definito dimensione dei dati in ingresso. Ad esempio, nel caso di un algoritmo di ordinamento di un file o di un array, la dimensione coincide con la lunghezza del file o dell’array. Nel seguito verrà indicata con n la dimensione dei dati in ingresso.
    2. Dipendenza dai Valori dei Dati. In molti casi la complessità computazionale di un algoritmo dipende non solo dalla dimensione dei dati in ingresso ma anche dai particolari valori assunti dai dati in ingresso. In particolare, può accadere che i tempi di calcolo di un algoritmo in corrispondenza di una determinata dimensione dei dati in ingresso, varino in funzione dei valori assunti dagli stessi dati in ingresso. Al fine di tener conto dell’influenza dei valori assunti dai dati in ingresso sulla complessità computazionale, in genere vengono considerati due possibili scenari: un tempo di calcolo massimo e uno medio. Nel primo caso, il legame tra tempo di esecuzione e parametro n viene fissato considerando i valori dei dati in ingresso che comportano il massimo tempo di esecuzione. Nel secondo caso viene considerato il tempo medio di esecuzione su dati di dimensione n, ottenuto considerando tutti i possibili valori dei dati in ingresso, per ciascuno di essi determinando la complessità computazionale e, infine, eseguendo la media dei valori di complessità computazionale ottenuti. Nella pratica ha interesse la valutazione del tempo massimo, ossia del caso peggiore. Tra l’altro, tale parametro è il più facile da misurare. Infatti se volessimo calcolare il tempo medio di esecuzione, dovremmo considerare uno scenario piuttosto significativo di dati in ingresso di dimensione n, e mediare sui relativi tempi di calcolo.

Definizione di Complessità Computazionale di un Algoritmo

Per quanto detto, lo studio della complessità computazionale di un algoritmo consiste nell’individuare una relazione tra il tempo di esecuzione, la dimensione dei dati, n, e la dipendenza dal particolare valore del dato o dei dati in ingresso. Vista la complessità di quest’ultimo legame, molto spesso si preferisce semplificare la relazione da individuare, considerando solo il legame tra il tempo di esecuzione e la dimensione dei dati, n, in ingresso. Tra tutti gli scenari legati ai valori dei dati in ingresso, si considera quello caratterizzato dal caso peggiore. In ogni caso, la relazione che si vuole individuare deve prescindere sia dalla particolare macchina che dal compilatore utilizzato.
Nel seguito indicheremo con T(n) il tempo di esecuzione di un algoritmo, in funzione di n, considerando il caso peggiore, nel caso in cui tale tempo dipenda dai valori dei dati ingresso.
Il calcolo della complessità computazionale consiste dunque nell’individuare l’espressione della funzione T(n).

Pubblicato da Vito Lavecchia

Lavecchia Vito Ingegnere Informatico (Politecnico di Bari) Email: [email protected] Sito Web: www.vitolavecchia.altervista.org

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *