Esercizio Lezione 6 - Equazioni di ricorrenza

CS-Swap / Algoritmi-1

Repository destinato alla condivisione di materiale e soluzioni per gli esercizi ed esami assegnati dal Prof. Monti Angelo in preparazione all'esame di Algoritmi 1

9 stars 1 forks source link

Esercizio Lezione 6 - Equazioni di ricorrenza #6

Open AglaiaNorza opened 8 months ago

AglaiaNorza commented 8 months ago

notedo commented 8 months ago

Amici, ho caricato i principali (ne mancano 2/3), una volta che uno sa fare questi, il procedimento per fare gli altri è pressoché lo stesso. Ho alternato i metodi tra iterativo e albero.

ESERCIZI - Algoritmi-22 ESERCIZI - Algoritmi-23 ESERCIZI - Algoritmi-24 ESERCIZI - Algoritmi-25 ESERCIZI - Algoritmi-26

Ultimo esercizio in versione iterativa 318260692-b454c3d2-2cf2-4136-b0b5-ff1a89a71d10

thegeek-sys commented 8 months ago

Ho risolto gli ultimi esercizi che mancavano a @notedo

T(n)=4T(n/2)+Θ(n) Immagine Immagine 2

T(n)=3T(n/2)+Θ(n log n)

Volevo inoltre proporre una versione iterativa di: T(n)=16T(n/4)+Θ(n²)

AglaiaNorza commented 8 months ago

in caso servissero a qualcuno, propongo versioni alternative di alcuni esercizi

3T(n/4) + Θ(n) in versione iterativa:

4T(n/2) + Θ(n) in versione albero:

e 2T(n/2) + Θ(n^3) in versione iterativa: Nella sommatoria è 2^j non 2^i, è solo un errore di scrittura, il procedimento è corretto