unità f1 analisi della complessità degli algoritmi
TRANSCRIPT
![Page 1: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/1.jpg)
Unità F1Unità F1Analisi della complessità degli
algoritmi
![Page 2: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/2.jpg)
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.
![Page 3: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/3.jpg)
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.
![Page 4: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/4.jpg)
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
![Page 5: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/5.jpg)
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.
![Page 6: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/6.jpg)
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)”.
![Page 7: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/7.jpg)
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)”.
![Page 8: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/8.jpg)
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)”.
![Page 9: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/9.jpg)
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.
![Page 10: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/10.jpg)
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
![Page 11: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/11.jpg)
Tipi di complessitàTipi di complessità• lineare;• logaritmica;• quadratica;• esponenziale;• fattoriale.
![Page 12: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/12.jpg)
LineareLineare
• l’algoritmo ha complessità O(n)
• Esempio:o algoritmo di
ricerca sequenziale di un elemento in un array
![Page 13: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/13.jpg)
LogaritmicaLogaritmica
• Esempio ricerca dicotomica in un array
• La ricerca dicotomica ha complessità O(log2(n))
![Page 14: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/14.jpg)
QuadraticaQuadratica
• Un esempio è l’algoritmo di ordinamento bubblesort eseguito su un array di elementi
• l’algoritmo ha complessità O(n2)
![Page 15: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/15.jpg)
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
![Page 16: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/16.jpg)
Torre di HanoiTorre di Hanoi
![Page 17: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/17.jpg)
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!)
![Page 18: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/18.jpg)
logaritmica < lineare < quadratica < esponenziale < logaritmica < lineare < quadratica < esponenziale <
fattorialefattoriale
![Page 19: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/19.jpg)
Alcuni esempiAlcuni esempiCalcolo complessità e confronto
![Page 20: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/20.jpg)
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
![Page 21: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/21.jpg)
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
![Page 22: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/22.jpg)
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
![Page 23: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/23.jpg)
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
![Page 24: Unità F1 Analisi della complessità degli algoritmi](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb4b497959361e8b75dc/html5/thumbnails/24.jpg)
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