Post on 01-May-2015
Unità F1Unità F1Analisi della complessità degli
algoritmi
Obiettivo principaleObiettivo principale• Confrontare algoritmi corretti che risolvono lo
stesso problema, allo scopo di scegliere quello migliore in relazione a uno o più parametri di valutazione.
Valutazione con un Valutazione con un parametroparametro
• Se si ha a disposizione un solo parametro per valutare un algoritmo, per esempio il tempo d’esecuzione, è semplice la scelta: il più veloce.
• Ogni altra caratteristica non viene considerata.
Valutazione con più Valutazione con più parametriparametri
• Nel caso di due parametri normalmente si considerao il tempo.
• numero di passi (istruzioni) che occorrono per produrre il risultato finale.
• Passi e non secondi o millisecondi perché il tempo varia al variare delle potenzialità del calcolatore.
o lo spazio• occupazione di memoria
Durata delle istruzioniDurata delle istruzioni• Le istruzioni non hanno tutte lo stesso
tempo di esecuzione.• Il tempo di esecuzione di un algoritmo è
una somma pesata delle istruzioni:
Ttotale=(i0*t0*n0)+(i1*t1*n1)+…+(im*tm*nm)
o ij è l’istruzione, o tj è il costo dell’istruzione, il tempo di esecuzione o nj è il numero di volte che viene eseguita.
Misura Misura delldell’’efficienzaefficienza
• L ’approssimazione di una funzione con una funzione asintotica è molto utile per semplificare i calcoli sul tempo di esecuzione di un algoritmo.
• La notazione asintotica di una funzione consente di descriverne il comportamento in modo semplificato, ignorando dettagli della formula.
• Esempio: per valori sufficientemente alti di x il comportamento della funzione f(x) = x2 – 3x + 1 è approssimabile con la funzione f(x) = x2.
• Per un algoritmo con un input di dimensione n, possiamo definirne l’efficienza dicendo che “l’algoritmo per calcolare il risultato finale impiega al più f(n) passi”, “l’algoritmo ha complessità f(n)”.
TerminologiaTerminologia• O (O grande) equivale al simbolo <=.
o Corrisponde a “al più come”. o “la complessità dell’algoritmo è O(f(n))” equivale a “il
tempo d’esecuzione dell’algoritmo è <= a f(n)”.
• o (o piccolo) equivale al simbolo <. o “la complessità dell’algoritmo è o(f(n))” equivale a “il
tempo d’esecuzione dell’algoritmo è strettamente < a f(n)”.
• Θ (teta) corrispondente al simbolo =. o “la complessità dell’algoritmo è Θ(f(n))” equivale a “il
tempo d’esecuzione dell’algoritmo è = a f(n)”.
TerminologiaTerminologia• Ω (omega grande) equivale al simbolo
>=.o “la complessità dell’algoritmo è Ω(f(n))”
equivale a dire “il tempo d’esecuzione dell’algoritmo è >= a f(n)”.
• ω (omega piccolo) equivale al simbolo >.o “la complessità dell’algoritmo è ω(f(n))” è uguale a “il tempo
d ’esecuzione dell’algoritmo è strettamente > di f(n)”.
Complessità Complessità computazionalecomputazionale
• La complessità computazionale di un algoritmo è la quantità di tempo necessaria per produrre il risultato finale.
• La complessità si esprime sotto forma di una funzione matematica che mette in relazione il tempo di esecuzione di un algoritmo con la dimensione dei dati di input.
• Il caso peggiore per un algoritmo è il caso in cui questo, per generare il risultato, impiega più tempo.
ComplessitàComplessità• In molti casi la complessità è legata al tipo
o al numero dei dati di inputo Ad esempio la ricerca di un valore in un vettore
ordinato dipende dalla dimensione del vettore
• La complessità può dipendere anche dalla disposizione e dal tipo di datio Sempre nell’algoritmo di ricerca in un vettore
ordinato avremo il caso:• Ottimo• Pessimo• Medio
Tipi di complessitàTipi di complessità• lineare;• logaritmica;• quadratica;• esponenziale;• fattoriale.
LineareLineare
• l’algoritmo ha complessità O(n)
• Esempio:o algoritmo di
ricerca sequenziale di un elemento in un array
LogaritmicaLogaritmica
• Esempio ricerca dicotomica in un array
• La ricerca dicotomica ha complessità O(log2(n))
QuadraticaQuadratica
• Un esempio è l’algoritmo di ordinamento bubblesort eseguito su un array di elementi
• l’algoritmo ha complessità O(n2)
EsponenzialeEsponenziale• l’algoritmo della Torre di Hanoi
ha complessità Ω(2n),• La Torre di Hanoi è un
rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.
• Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono.
• Lo scopo del gioco è portare tutti dischi sull’ultimo paletto, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo
Torre di HanoiTorre di Hanoi
FattorialeFattoriale
• E’ quella che cresce più velocemente rispetto a tutte le precedenti.
• Esempio: algoritmo che calcola tutti gli anagrammi di una parola di n lettere distinte.
• la complessità di un tale algoritmo è Θ(n!)
logaritmica < lineare < quadratica < esponenziale < logaritmica < lineare < quadratica < esponenziale <
fattorialefattoriale
Alcuni esempiAlcuni esempiCalcolo complessità e confronto
Algoritmo 1 – Calcolo Algoritmo 1 – Calcolo xx55
ALGORITMO 1x,i,p: intero
INIZIOleggi(x)i1p xMENTRE i<5 ESEGUI
p p*xi i+1
FINEMENTREscrivi(p)
FINE
1111x5
2x4
117
Algoritmo 2 – Calcolo Algoritmo 2 – Calcolo xxnn
ALGORITMO 2x,i,p: intero
INIZIOleggi(x)leggi(n)inp 1MENTRE i>0 ESEGUI
p p*xi i-1
FINEMENTREscrivi(p)
FINE
1111
3xn+1
13n+6
Ricerca sequenzialeRicerca sequenzialeFUNZIONE
RicercaSequenziale(V:vettore;N,P:Intero):BooleanoTrovato : BooleanoI : InteroINIZIOTrovato FalsoI 1MENTRE (I<N) AND (NOT Trovato) ESEGUI
SE V[I]=X ALLORATrovato Vero
FINESEI I+1
FINEMENTRERITORNO(Trovato)FINE
Ciclo eseguito:
•Caso ottimo 1 volta
•Caso pessimo n volte
•Caso medio n/2 volte
Ricerca binariaRicerca binariaFUNZIONE RicercaBinaria(V:vettore;N,X:Intero):BooleanoPrimo, Ultimo, Centro : Intero ; Trovato : BooleanoINIZIO Primo 1; Ultimo N; Trovato FalsoMENTRE (Primo<=Ultimo) AND (NOT Trovato) Centro (Primo+Ultimo)/2
SE V[Centro]=X ALLORATrovato Vero
ALTRIMENTI SE V[Centro]<X ALLORA Primo Centro+1 ALTRIMENTI Ultimo Centro-1 FINESE FINESEFINEMENTRERITORNO(Trovato)FINE
Ciclo eseguito:
•ottimo 1 volta
•pessimo log n volte
•medio log n volte
Confronto fra n - n/2 - Confronto fra n - n/2 - log(n)log(n)
n n/2 log(n)10 5 3,32192820 10 4,32192830 15 4,90689140 20 5,32192850 25 5,64385660 30 5,90689170 35 6,12928380 40 6,32192890 45 6,491853100 50 6,643856300 150 8,2288191000 500 9,96578410000 5000 13,28771100000 50000 16,60964