Misure di complessità degli algoritmi.

Misure di complessità degli algoritmi.


Quando dobbiamo confrontare vari algoritmi per la risoluzione di un dato problema possiamo seguire diversi criteri basati o sulle caratteristiche strutturali degli algoritmi o sulle risorse (tempo e/o memoria) richieste dalla loro esecuzione.Nel primo caso usiamo una informazione di carattere statico e le caratteristiche considerate sono indipendenti dai dati di ingresso:esempi di questo tipo di misure di complessità che andremo a chiamare “strutturali” possono essere la lunghezza dell'algoritmo o il massimo numero di cicli o di definizioni ricorsive nidificate utilizzate.Nel secondo caso la misura di complessità ha un carattere dinamico;essa esprime il costo di esecuzione dell'algoritmo al variare della dimensione dei dati:le grandezze che possono essere utilizzate per esprimere il costo di esecuzione,e che chiamiamo misure di tipo “computazionale”,possono essere, ad esempio il numero dei passi di calcolo richiesti, il numero di operazioni di un determinato tipo (operazioni aritmetiche, confronti ecc) o, se si vuole spingere molto la precisione dell'analisi, il tempo di unità centrale richiesto dall'esecuzione di un programma su una macchina reale. Nell'ambito della teoria della complessità computazionale lo studio delle proprietà delle misure di complessità statiche o dinamiche, dei bilanci che si verificano tra di esse, delle classificazioni di funzioni di cui danno luogo è stato sviluppato ampiamente. Tra i vari risultati cui si ve ne sono anche alcuni, a prima vista sorprendenti, che stabiliscono una precisa corrispondenza tra misure di tipo strutturale e misure di tipo computazionale. Ad esempio, utilizzando un opportuno linguaggio di programmazione si dimostra che tutte e sole le funzioni che possono essere definite con programmi che richiedono al più due livelli di ciclo nidificati sono calcolabili in una quantità di tempo e con una memoria limitate da una funzione superesponenziale.


Risultati simili sono stati dimostrati anche per altre classi di funzioni. Tuttavia, per il tipo di problemi cui sono interessati i risultati stabiliscono un legame così preciso tra complessità computazionale e struttura dei programmi non esistono. Un secondo motivo per cui non riprenderò in esame le misure di tipo strutturale è dovuto al fatto che realizzare un'economia nella struttura di un programma non offre vantaggi interessanti {può anzi rendere illeggibile la descrizione stessa} mentre è molto più importante realizzare una economia nella quantità di tempo o di memoria per eseguire il calcolo. Rispetto all'ampia gamma di metodi con cui possiamo misurare la complessità di un algoritmo o di un programma, le misure di tipo computazionale {tempo e spazio di calcolo} hanno dunque un ruolo centrale ed è ad esse che farò riferimento sia quando dovremo confrontare la bontà di due algoritmi sia quando dovremo caratterizzare la difficoltà di un problema.


Funzioni superesponenziali sono funzioni del tipo:


2\eta


.


.


. } k volte


f(n)=2\frac{2}{}


con k intero


function FACT1 (n:integer) : integer:


var k,i : integer :


begin


k := l ;


if (n > 0) then


for i :=1 to n do k := k*i ;


FACT1 := k


end:


A1 - Algoritmo FACT 1


function FACT2 (n : integer) : integer:


begin


if (n = 0) then FACT2 :=1


else FACT2 := FACT2 (n-1) * n


end:


A.2 Algoritmo FACT2


Consideriamo un semplice esempio, il problema del calcolo del fattoriale e definiamo per esso due classici algoritmi: uno interativo e uno ricorsivo. Come si vede immediatamente le caratteristiche strutturali dei due algritmi presentano aspetti simili, al più la versione ricorsiva potrà apparire leggermente più vantaggiosa: il corpo del programma FACT2 è più corto e più semplice del corpo del programma FACT1. Se consideriamo le caratteristiche dinamiche, osserviamo che dal punto di vista del tempo di esecuzione,sia FACT1 sia FACT2 richiedono un numero di passi, in particolare di operazioni di moltiplicazione tra interi, lineare in n.A questo una affrettata conclusione potrebbe far ritenere che i due programmi abbiano le stesse caratteristche di efficenza. In effetti dal punto di vista delle esigenze di memoria abbiamo una situazione diversa: entrambi i programmi richiedono una memoria di dimensione pari a log n!= = \Sigma\frac{n}{i=1} log per contenere le rappresentazione binaria del risultato ma se confrontiamo la memoria di lavoro verifichiamo che il programma FACT1 fa uso di due variabili {i e k} di dimensione rispettivamente log n e \Sigma\frac{n}{i=1} log i mentre il programma FACT2 ( per l'implementazione delle n chiamate ricorsive ) richiede una memoria sensibile e maggiore ( il lettore può verificare che essa è pari a \Sigma\frac{n}{i=1} \Sigma\frac{j}{i=1} log i. Abbiamo quindi che, a fronte di una maggiore concisione, il programma ricorsivo offre un costo di esecuzione uguale in termini di tempo ma peggiore in termini di memoria. Prima di poter analizzare la complessità di algoritmi espressi in linguaggi ad alto livello è dunque necessario introdurre i principali aspetti metodologici della analisi degli algoritmi introducendo un linguaggio estremamente elementare.