Algoritmi e strutture dati

IF

If condizione che richiede tempo O(f)

then qualcosa che richiede tempo O(g)

else qualcosa che richiede tempo O(h) T()= O(f)+ O (max[g,h])

FOR

for i=1 to n do { n

Qualcosa che richiede tempo O(f(n))

T()= n*O(f(n)) = O (n * f(n)) [per la proprietà del prodotto ]

}

for j=1 to n do{ n

for x=1 to m do m

qualcosa che richiede tempo O(g(n)) m * O(g(n))

T()= O(m*n*g(n))

}

T[totale]()= O(m*n*g(n)) + O (n * f(n)) 18

Mileva Matteo

Dimostrazione del Select Sort (A) [p=taglia ed n=lenght(A)]

Select Sort(A){

for ( i=1 to lenght(A)-1){ n-1

k=indice_minimo(A[i…lenght(A)]); O(n)* T(n)=(n²)**

scambia A[i] con A[k] O(1)

}

Return a; O(1)

}

indice_minimo(B)

m=1; O(1)

for (j=2 to lenght(B)) p-1

if( B[m]> B[j]) then O(1) O(p)

m<j O(1)

return m

*la ricerca dell’indice minimo in un intervallo è O(cardinalità dell’intervallo) che sarà i-j = j-i+ 1, nel

nostro caso sarà n-i+1

T[indice_minimo](length(A[i..n]))) = O(n − i + 1) = O(max{n, i, 1}) = O(n)

perché i ≤ length(A) − 1 < n. Quindi il corpo del for, linee 2-3, ha costo O(n) + O(1) = O(n). Infine le

iterazioni del for delle linee 1-4 sono n − 1, ragion per cui abbiamo:

**T(n) =(n-1) * [O(n) + O(1)] = (n-1)* O(n) = O((n-1)*n) = O(n² - n) = O(n²)

□

Nb: per risolvere la ricorrenza – cioè per ottenere dei limiti asintotici θ e O per la soluzione, si

usano tre metodi

Metodo di sostituzione (srotolamento) ipotizziamo un limite e poi usiamo l’ induzione matematica

per dimostrare che la nostra ipotesi sia corretta.

Metodo dell’ albero di ricorsione converte la ricorrenza in un albero i cui modi rappresentano i

costi ai vari livelli della ricorsione; per risolvere la ricorrenza adotteremo delle tecniche che

limitano le sommatorie.

Il metodo dell’esperto fornisce i limiti per ricorrenze nella forma T(n)= aT(n/b)+ f(n) 19

Mileva Matteo

5)Relazioni di ricorrenza

Quando vuoi analizzare un algoritmo ci sono due strade, o si usa la tabella dei costi che presa riga

per riga si costruisce la funzione lineare che è la funzione tempo dopo diche si studia l’ordine di

grandezza con algebra di O e le proprietà, un altro approccio se l’obiettivo e dire la complessità del

tempo ( O ,θ) e non quindi andare a valutare le costanti moltiplicative, andare con precisione le

cose allora si può applicare direttamente questi “bound” istruzione per istruzione, non si fa un

discorso di linea ma un analisi composizionale dell’algoritmo (singole istruzioni oppure dei if, for)

,questo va bene se gli algoritmi sono iterativi, ma quando sono ricorsivi?

La funzione tempo di un algoritmo ricorsivo è ricorsivo, perché ad un determinato punto

richiamerà se stesso.

dove l’incognita è la funzione , e per trovarla bisogna srotolare la T sostituendola

ps: .. +d rappresenta il numero dei confronti che l’algoritmo con taglia n.

metto k=n in modo da osservare tutti gli elementi, mi metto all’estremo., ma T(0) è una costante e

nd€ O(n) quindi O(1) + O(n) =O(n).

La ricerca di un minimo (o massimo) su una struttura [array] avrà come complessità di tempo

T(n)=T(n-1)+d che appartiene a O(n) dove n è la dimensione della struttura, si nota che tutti questi

casi si ha un zig-zag dentro un segmento e la somma di questo andare avanti e indietro viene a

costare O(n²), vedi algoritmo del Insert-sort; tutti gli algoritmi di scansione di una struttura lineare

hanno questa struttura sono O(n), molte volte questi piccoli algoritmi sono parti di algoritmi più

complessi.

Vediamo la relazione di ricorrenza del Insert-Sort:

si noti che l’inserimento è una semplice iterazione ripetuta più volte.

T[insert](n) perché al massimo attraverso tutto il segmento n quindi ,dove “dn” dipende da n.

T(n-1) è la chiamata a funzione ricorsiva e l’inserimento lavora su n,

Rifaccio lo srotolamento per insert sort: 20

Mileva Matteo

tempo troppo alto visto O(cᶰ) sono algoritmi di scheduling.

Quindi possiamo generalizzare ,dalla forma posso troviamo l’ordine di grandezza, c’è ne sono di

due tipi.

Relazione lineari a partizioni costanti (scende linearmente in n che ha grado 1, e partizione

costante perché i è limitato da h che è il massimo ), il lavoro polinomiale è il lavoro(passi) che

viene fatto ogni volta in modo esplicito, viene tolta una parte costante.

Quello che determina l’ordine di grandezza della T è la “a” (c negli altri esempi) , quando a =1

T(n)€ O(nᴯ⁺¹)dove b è il lavoro, quando a≥2 si moltiplica con una funzione esponenziale con base a.

Select-sort ricorsivo

T(n)= n-1 + T(n-1) ≤ T(n-1) + cn per c ≥1 ed h=1, a=1 e B=1 21

Mileva Matteo

Minimo ricorsivo (caso pessimo)[qui non c’è n quindi B=0]

T(n)= T(n-1) + c per c >0 ed h=1, a=1 e B=0

Torri di Hanoi

T(n) = 2T (n-1) + c per c =1 ed h=1, a=2 e B=0

In pratica l’esercizio consiste nel scegliere queste costanti in modo tale che questa espressione

diventi un caso particolare di quella vista ,dopo di che vado a vedere nella mia tabellina come sta

“a” e leggo quello che voglio sapere [nei teoremi in giallo].

Tutto gli algoritmi visti finora si possono fare in maniera iterativa e la ricorsione serve per

accelerare il tempo per risolvere un dato problema e la tecnica si chiama Divide et Impera

Divide et Impera

Si suddivide il problema in sottoproblemi di dimensione circa uguali e risolvere i sottoproblemi

con la ricorsione infine si combinano i risultati, metodo di sviluppo in modo ricorsivo.

DivideEtImpere (P,n) //Pre : n è la dimensione di P

If n ≤ k then risolvi direttamente P

else dividi P nei sottoproblemi P1…Ph di dimensioni n1…nh

for i=1 to h do

Ris[i]= DivideEtImpera (Pi,ni)

return combinazione di Ris1….Ris[h]

questo metodo porta a buoni risultati se riesco a soddisfare certi vincoli

Nel algoritmo del massimo/minimo in A[p…q] 22

Mileva Matteo

ci sono (3/2) n -2 confronti, dove n=2ᴷ

Dim: ( simile al select sort) 0 se n=1

se n=lunghezza(A) cioè q-p+1 allora i confronti sono C(n) e sono: 1 se n=2

C([n/2])+C([n/2])+2 se n>2 (ci sono le chiamate ricorsive e sono due e fatte sulla parte intera

inferiore e superiore di n/2, più i due confronti impliciti )

per semplicità supponiamo n=2ᴷ con k>1,usiamo il metodo “indovina e prova”

2((3/2)*2ᴷ -2 )+2 = (3/2)*2ᴷ⁺¹ - 4 +2 =(3/2)*2ᴷ⁺¹-2 per induzione su k , quindi ragionando per

induzione su k>1, se ne conclude che C(2ᴷ)= (3/2)n -2 dove n=2ᴷ, in pratica si migliora che il

coefficiente di n è passato da 2 a 3/2.

Relazioni lineari a partizione bilanciata ( perché divide in parti tutti uguali e ci si guadagna nel

mantenere la taglia dei sottoproblemi uguale in modo da poter guadagnare)

Nel caso della ricerca lineare (stiamo vedendo le relazioni lineari a partizione bilanciata)

In realtà questa volta c’è differenza dal punto di vista asintotico perché la ricerca lineare sappiamo

che è O(n) ma questa ricerca mi da questa forma

Si nota che ora il k che sta in k*b , k non è il numero di volte che sottraggo n ma è il numero dell’

esponente di b, che è tanto [d(k-1) è sbagliato il -1], si nota che la funzione viene chiamata su se

stessa dove quello che cambia da una volta all’altra è che il denominatore di questa frazione (b)

cresce esponenzialmente nel numero di volte che la funzione chiama se stessa (unfollowing) però

attenzione a noi non piace molto l’esponenziale ma in questo caso si trova sotto quindi a noi va

23

Mileva Matteo

bene perché molto rapidamente riusciamo a convergere sul caso di base dove risolvo, non andrò

avanti all’ infinito con k perché è limitata al log di base b di n infatti se faccio il giochetto di

sostituire all’ estremo k con log base b di n mi viene n/log(b) di n cioè n

…-d è un errore… sono tutte costanti tranne log n , e c’è stato un guadagno rispetto all’algo senza

ricorsione.

Ordinamento per fusione

Consiste nel dividere l’insieme in due parti uguali, si ordina i due sotto insieme e poi si fa una

fusione, il metodo fusione vede i primi due elementi , sceglie il minimo e lo inserisce nell’ insieme

finale, si nota che quando non ho più elementi in un sotto insieme (1..i) significa che basta che

aggiungo direttamente i componenti ancora da sistemare del secondo sotto insieme in quando

saranno maggiori.

Merge-Sort

Nella complessità del Tmergre, n rappresenta la taglia d’ingresso, c è una costante che si può

togliere e (n-1) rappresenta la fila C e B, va a livelli.

Complessità del merge-sort:

quando prendo un array di taglia n faccio due volta il T(n/2) + chiamo merge sul numero totale

degli elementi C e B.

si nota che è una partizione bilanciata perché n/2, invece di svilupparlo con lo srotolamento uso gli

alberi di ricorsione dove ogni livello ha un costo n da pagare e tutti i costi vanno sommati con i figli

24

Mileva Matteo

log n è altezza dell’ albero quindi si ha O(nlogn) ma con l’albero delle decisione abbiamo visto che

nlogn è il confine superiore per qualsiasi algoritmo che fa confronto d’ordinamento.

Esistono degli algoritmi per fare il merge con complessità O(n) ma usano array caratteristico dove

c’è ogni elemento non può essere maggiore di k quindi ce un limite k, ma essendo lungo k e scelgo

gli elementi maggiori di k, visto che ci metto O(1) a scandire e lo ricostruisco nel farlo, il costo

maggiore è costruire array caratteristico cioè O(1).

A= coefficiente costante , T(n/b) è la funzione lineare , b= valore della parz. Bilanciata tutte uguali,

cnᴯ è il lavoro polinomiale , il master teoren dice che:

1)confronto il rapporto α= log a( numero di chiamate ricorsive consecutive) / log b ( fattore per cui

divido la taglia) se questo numero è maggiore di B allora la complessità di T è polinomiale e α

domina e determina il grado del polinomio

2) c’è un bilanciamento e α=B , viene un costo polinomiale in α e B ma moltiplicato al log n.

3) è lo stesso solo che ᴯ

Ricerca Binaria:

Merge Sort: 25

Mileva Matteo

Moltiplicazione veloce :

Quick Sort

Bello ed elegante, l’algoritmo d’ordinamento è molto rapido, l’idea consiste nel non dividere in

due la collezione di elementi ma scelgo a caso un elemento e chiamo sto elemento “pivot” o

“perno” e lo uso come numero centrale creando due insieme