Diapositiva 1 - Mondadori Education

Informatica 3
V anno
La complessità computazionale
In cerca di buone soluzioni
Trovare buone soluzioni nella risoluzione di un problema si rivela un aspetto
fondamentale tanto nella vita di tutti i giorni, quanto in informatica.
Anche nella progettazione di algoritmi sarà importante trovare buone soluzioni.
Individuare e progettare un algoritmo efficiente si traduce in un risparmio di
risorse computazionali e, di conseguenza, in un risparmio di tempo e denaro.
Un problema, molte soluzioni
Solitamente esistono diversi algoritmi per risolvere uno stesso problema.
Di ogni algoritmo dobbiamo considerare due aspetti:
- la sua organizzazione interna, ovvero la struttura data alle sue istruzioni e le
strutture dati utilizzate
- le risorse necessarie per eseguirlo (memoria e processore), strettamente
legate allo spazio e al tempo necessari alla sua esecuzione.
Ogni algoritmo può essere tradotto in diversi programmi, scritti in
diversi linguaggi di programmazione.
La bontà di algoritmo
Per valutare la bontà di un algoritmo NON ci si sofferma sull’algoritmo in
sé ma sulle risorse che utilizza e al suo tempo di esecuzione.
Il nostro obiettivo sarà quindi quello di:
Dati uno o più algoritmi che risolvono un problema, confrontarli per
individuare il migliore sulla base di un’analisi qualitativa.
Cercheremo quindi di assegnare agli algoritmi una misura di qualità.
In molti casi, sarà importante valutare il tempo di esecuzione, altre volte
serve valutare differenti caratteristiche.
Nello spazio e nel tempo
L’obiettivo è quello di dare ai nostri algoritmi un’organizzazione interna
tale che il processo corrispondente impieghi il minor numero di risorse
durante la sua esecuzione.
Tra le risorse, molto importanti si rivelano:
- Spazio di esecuzione (risorsa spazio), cioè l’area di memoria occupata
da un processo durante la sua esecuzione.
- Tempo di esecuzione (risorsa tempo), cioè il tempo in cui il processo
legato all’algoritmo è eseguito.
Con i moderni calcolatori, dotati di grande capacità di memoria, la risorsa
spazio è divenuta meno importante.
Sarà, dunque, più importante concentrarsi sui tempi di esecuzione.
Algoritmi buoni, per cominciare
Gli algoritmi che prenderemo in considerazione saranno algoritmi buoni,
cioè dovranno essere:
- soluzioni semplici, efficaci e, soprattutto, generali
- facilmente modificabili in caso di necessità
- indipendenti dal linguaggio di programmazione che si vuole utilizzare
Costo di un algoritmo
Misureremo il tempo di esecuzione di un algoritmo in numero di
operazioni che l’algoritmo deve compiere per fornire i risultati.
Tale numero è detto costo dell’algoritmo.
Per quantificare il costo di un algoritmo ci concentreremo sull’algoritmo in
sé, tralasciando la sua implementazione, in quanto:
- l’algoritmo è la descrizione generale dell’intero processo di calcolo
- l’algoritmo ignora tutti i dettagli implementativi legati al linguaggio
- il tempo necessario per l’esecuzione dell’algoritmo è indicativo del tempo
di esecuzione del processo corrispondente
Costo istruzioni semplici
La prima regola di valutazione per il calcolo del costo delle istruzioni
di un algoritmo riguarda le istruzioni semplici:
Le istruzioni semplici quali lettura, scrittura, assegnamento hanno un
costo pari a uno.
Costo = 1
Costo costrutti iterativi (1)
I costrutti iterativi quali MENTRE…FINEMENTRE, RIPETI…FINCHÉ hanno
un costo pari alla somma dei costi del test e del corpo del ciclo.
In particolare:
- il test del ciclo, essendo un’istruzione semplice ha complessità pari a uno.
- il costo del corpo del ciclo, invece, è dato dalla somma dei costi delle
singole istruzioni.
(NON sono inserite nel calcolo le operazioni di apertura e chiusura del corpo del ciclo).
Se il ciclo viene iterato K volte, allora il costo è:
Costo = CostoTest*K + CostoCorpo*K
Nei cicli a controllo in testa però, il test viene eseguito K+1 volte perché
occorre calcolare il test di uscita dal ciclo, quindi avremo:
Costo = CostoTest*(K+1) + CostoCorpo*K
Costo costrutti iterativi (2)
I costrutti iterativi quali PER…ESEGUI hanno un costo ottenuto dalla
somma dei seguenti costi:
- costo dovuto all’inizializzazione della variabile del ciclo: pari a uno.
- costo di condizione di fine ciclo: pari al numero di volte che il ciclo viene
eseguito più un costo pari a uno dovuto al test finale che consente di
uscire dal ciclo.
- costo del corpo del ciclo: pari alla somma dei costi delle singole
istruzioni, tenendo conto delle K volte che il corpo del ciclo viene eseguito.
- costo di incremento della variabile del ciclo: pari al numero di volte che il
ciclo viene eseguito.
Riassumendo,avremo:
Costo = 1 + CostoTest*(K+1) + CostoIncremento*K + CostoCorpo*K
Costo costrutto di selezione
Il costrutto di selezione SE…ALLORA ha un costo pari alla somma dei
costi del test più quello delle singole istruzioni semplici contenute
all’interno di ALLORA.
Analogamente viene calcolato il costo del costrutto di selezione binaria
SE…ALLORA…ALTRIMENTI, dove sarà utilizzato il costo massimo tra i
due rami.
Avremo, dunque:
Costo = 1 + MAX(CostoRamoALLORA, CostoRamoALTRIMENTI)
Costo chiamata sottoprogramma
L’istruzione di chiamata di un sottoprogramma ha costo pari a quello
dell’intero sottoprogramma, tenendo conto delle regole per le precedenti
situazioni, più il costo dell’istruzione di chiamata, che è pari a uno.
Costo = 1 + CostoSottoprogramma
Costo istruzioni composte
L’istruzione composta (per esempio annidamenti di strutture di controllo e
blocchi di istruzioni) ha una complessità pari alla somma dei costi delle
singole istruzioni semplici che la compongono.
Costo =  CostoIstruzioniSemplici
Regole e costi
Utilizzando queste regole per il calcolo dei vari costi, avremo risultati
approssimati perché è consuetudine occuparsi solo di operazioni dal costo
dominante (confronti, moltiplicazioni ecc.) trascurando le istruzioni meno
onerose dal punto di vista esecutivo (addizioni, incrementi, decrementi ecc.).
Pertanto, il tempo di esecuzione di un algoritmo è proporzionale al suo costo.
Infatti, conoscendo il tempo di esecuzione di un’istruzione di costo unitario
(tempo unitario), espresso in secondi, basterà moltiplicare il costo complessivo
dell’algoritmo per esso, per ottenere il tempo totale di esecuzione dell’algoritmo.
Complessità computazionale
Il numero di operazioni di un algoritmo è legato anche alla dimensione dei
dati di input (N), perciò risulta da essa definibile.
Usiamo la notazione generica T(N) per indicare la funzione matematica
che indica la relazione esistente tra il numero di operazioni di un
programma e la dimensione N dei dati in input.
La funzione T(N) è chiamata complessità computazionale (in tempo) o
semplicemente complessità dell’algoritmo. La dimensione N dei dati in
input è anche detta dimensione del problema.
Sequenza dati in input
Per effettuare una buona analisi dell’algoritmo, spesso è necessario
valutare la sequenza di dati che si presentano in input e i loro specifici
valori.
Pertanto:
La complessità è legata ai valori dei dati in input e a come i dati sono
disposti, oltre che alla loro dimensione.
Caso ottimo, pessimo e medio
Per valutare le prestazioni di alcuni algoritmi si dovrebbero prevedere
tre tipi di analisi, ovvero:
- analisi del caso ottimo
- analisi del caso pessimo
- analisi del caso medio
La funzione va analizzata nei tre casi in base alla disposizione e al tipo di
dati in ingresso.
Utilizziamo le seguenti notazioni:
Tottimo(N)
Tpessimo(N) Tmedio(N)
Per quale analisi optare?
Per decidere quale considerare delle tre, va analizzato il tipo di applicazione.
Per esempio, in sistemi real-time interessa solo la funzione Tpessimo(N), ma in
genere è la funzione Tmedio(N) quella che riveste maggiore importanza.
Pertanto, parlando di complessità di un algoritmo ci riferiamo implicitamente
all’analisi del caso medio.
Quando l’analisi del caso medio si rivela complicata si ricorre al caso
pessimo.
Possiamo considerare che la funzione Tpessimo(N) fornisca una limitazione
alla complessità dell’algoritmo, nel senso che le altre funzioni di complessità
non possono crescere più di come accade nel caso pessimo.
L’algoritmo ottimo
L’obiettivo è quello di risolvere un problema scrivendo un algoritmo con la
minima complessità possibile sia nel caso medio sia in quello pessimo.
Definiremo tale algoritmo un algoritmo ottimo.
Pertanto, per complessità di un problema si intende la complessità degli
algoritmi ottimi che lo risolvono.
Ordine di grandezza della complessità
Molto spesso risulta difficile giungere a una formulazione della complessità
di un algoritmo.
Confrontando due algoritmi, può anche accadere che il primo esegua
meno operazioni con dimensione dal problema bassa, ma che le cose si
ribaltino quando tale dimensione cresce.
In questi casi entra in gioco l’ordine di grandezza della complessità, cioè la
valutazione complessiva per valori molto grandi delle dimensioni del
problema. Si parla di complessità asintotica.
Complessità asintotica
La complessità asintotica si esprime con la notazione matematica:
lim T(N)
N
che si legge: limite per N che tende a infinito della funzione T(N).
Si ottiene, cioè, un’espressione in funzione di N che indica qual è il
comportamento asintotico dell’algoritmo.
Ordine di grandezza
Introduciamo le seguenti definizioni:
Siano f(N) e g(N) due funzioni. Si dice che f(N) è di ordine di grandezza
g(N) e si scrive O(g(N)), che e si legge:
“O grande di g di N” se esiste una costante C > 0 tale che, per tutti i valori
nel dominio di N, f(N) < C * g(N).
Pertanto, dire che T(N) è O(g(N)), significa che g(N) è un limite superiore
alla legge di crescita di T(N), cioè T(N) non cresce più di g(N).
Diremo, inoltre, che:
f(N) è proporzionale a g(N) se f(N) è O(g(N)) e g(N) è O(f(N)).
Pertanto, f(N) e g(N) sono dello stesso ordine (di grandezza).
Grafico ordine di grandezza
Il grafico di T(N) da un certo punto in poi sarà al di sotto di quello di C*g(N)
Costante di proporzionalità
Possiamo, ora affermare che:
T(N), ossia la complessità computazionale di un algoritmo X, è
proporzionale a N2 ovvero è dell’ordine di N2 : O(N2).
Consideriamo T(N) = 2N2 + 5: essendo comportamenti asintotici, sia la
costante 5, sia la costante moltiplicativa 2 (perché si parla di limiti),
risultano irrilevanti, per determinare l’ordine di grandezza. Ciò che
interessa è il termine N2.
Più formalmente:
Classi di complessità
Possiamo individuare alcuni ordini di grandezza per le funzioni T(N) che
individuano le cosiddette classi di complessità (o di computabilità).
Abbiamo i seguenti casi:
- Complessità costante O(1) o O(C)
- Complessità logaritmica O(logN)
- Complessità lineare O(N)
- Complessità NlogN O(NlogN)
- Complessità polinomiale O(NK)
- Complessità esponenziale O(KN)
Complessità costante O(1) o O(C)
La Complessità costante O(1) o O(C) indica la complessità degli algoritmi
che eseguono lo stesso numero di operazioni indipendentemente dalla
dimensione dei dati in input.
Complessità logaritmica O(logN)
La Complessità logaritmica O(logN) indica la complessità degli algoritmi
che eseguono un numero di operazioni proporzionale a log N.
Complessità lineare O(N)
La Complessità lineare O(N) indica la complessità degli algoritmi che
eseguono un numero di operazioni proporzionale a N, cioè proporzionale
alle dimensione del problema.
Complessità NlogN O(NlogN)
La Complessità NlogN O(NlogN) è la classe di molti algoritmi di ordinamento.
Complessità polinomiale O(NK)
La caratteristica della Complessità polinomiale O(NK) è di avere dimensioni
del problema come base da elevare a un esponente K.
Quando K=2 si parla di complessità quadratica.
Quando K=3 si parla di complessità cubica.
Complessità esponenziale O(KN)
La caratteristica della Complessità esponenziale O(KN) è di avere
dimensioni del problema come esponente.
Algoritmi con medesima classe di complessità
Due algoritmi appartenenti alla stessa classe di complessità possono
essere confrontati relativamente al tempo di esecuzione.
Due algoritmi appartengono alla stessa classe di complessità quando:
Siano f1(N) e f2(N) due funzioni con la stessa classe di complessità
computazionale, relative, rispettivamente, agli algoritmi A1 e A2 che
risolvono lo stesso problema.
Diremo che A1 e A2 appartengono alla stessa classe di complessità se:
Efficienza di un algoritmo
Visto quando due algoritmi appartengono alla stessa classe di
complessità, possiamo, ora, valutare l’efficienza di tali algoritmi.
In particolare, diremo che:
1. A1 è più efficiente di A2 se:
2. A2 è più efficiente di A1 se:
Tempo di esecuzione in base alla classe di complessità
Data una classe di complessità, dalla seguente tabella possiamo notare come varia il tempo
di esecuzione di un algoritmo (espresso in secondi) al variare della dimensione N del
problema con un computer che esegue un milione di operazioni elementari al secondo.
Problemi facili e difficili
L’analisi della complessità computazionale degli algoritmi permette di
classificare i problemi.
Dati due problemi A e B, supponiamo che:
- esista un algoritmo per risolvere A in tempo O(N) nel caso pessimo;
- il migliore algoritmo per B abbia complessità O(2N) nel caso pessimo.
Possiamo concludere che:
- B è un problema “più difficile” di A;
- B non ammette soluzioni altrettanto efficienti quanto A.
Problemi trattabili e intrattabili
La classificazione basata sulla complessità computazionale è una
classificazione “fine”, ma in generale è utile classificare i problemi sulla
base di una classificazione più “grossolana”:
- un problema con complessità polinomiale nel caso pessimo, cioè O(NP)
per qualche P, è considerato trattabile
- un problema con complessità almeno esponenziale nel caso pessimo,
ovvero O(CN) per qualche C, è considerato intrattabile.
Gli algoritmi con complessità esponenziale sono da considerare con
diffidenza perché possono richiedere tempi di esecuzione lunghi anche per
valori di N piccoli e indipendentemente dalla velocità dell’elaboratore.
Purtroppo esistono ancora molti problemi, detti intrattabili, per cui NON è
presente un algoritmo NON esponenziale.
Nel caso dei sistemi di crittografia questo è un bene.
Problemi P e NP
La classe di problemi risolvibili in tempo polinomiale è chiamata P.
Esiste una classe di problemi, chiamata NP, per ciascuno dei quali esiste
un algoritmo esponenziale che lo risolve, ma non si sa se esistano
algoritmi polinomiali che lo risolvano.
La classe P è contenuta nella classe NP o coincide con essa, ma è ancora
un problema aperto dimostrare che P è contenuta strettamente in NP.
Complessità computazionale spaziale
In conclusione, accenniamo alla complessità computazionale spaziale,
intesa come dimensione della struttura dati necessaria a supportare
l’esecuzione di un algoritmo.
Generalmente si associa la complessità spaziale all’ordine di grandezza
della memoria e computazionale all’ordine di grandezza del tempo
necessario alla computazione.
In conclusione…
Lo studio qualitativo condotto deve farci riflettere sul tipo di considerazioni
che vanno fatte quando si affronta la progettazione di un algoritmo o
quando si confrontano due o più algoritmi.
Lo studio asintotico, infatti, indaga sulla qualità intrinseca di un algoritmo.
Ci serve per stabilire quale sia l’algoritmo “migliore” al crescere della
dimensione del problema.
Ogni algoritmo deve, comunque, essere esaminato caso per caso, perché
NON è possibile condurre lo studio su schemi preordinati.