Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: milos224 on 20-12-2012, 16:47:57



Title: Algoritmo Select e Bucket Sort
Post by: milos224 on 20-12-2012, 16:47:57
Due domande:

l'equazione del Select è 3 { [1/2(n/5)]-2 } che viene 3n/10 - 6. Da cui 7n/10 + 6, scritto nel libro. Ma perchè? C'è una spiegazione?Come diventa 7n/10 + 6?

Inoltre nella domanda del compito del bucket, la risposta era la b, quella col segno "+". Come mai?


Title: Re:Algoritmo Select e Bucket Sort
Post by: sisal on 20-12-2012, 17:32:36
Penso sia per il fatto che se gli elementi maggiori della mediana delle mediane sono 3n/10 - 6, quelli minori allora sono tutti gli altri, cioè 7n/10 +6.
Infatti nel caso peggiore (quello in cui l'elemento che cerchiamo è piu piccolo rispetto alla mediana delle mediane), l'algoritmo viene richiamato su 7n/10 elementi piu piccoli


Title: Re:Algoritmo Select e Bucket Sort
Post by: milos224 on 20-12-2012, 17:34:35
Penso sia per il fatto che se gli elementi maggiori della mediana delle mediane sono 3n/10 - 6, quelli minori allora sono tutti gli altri, cioè 7n/10 +6.
Infatti nel caso peggiore (quello in cui l'elemento che cerchiamo è piu piccolo rispetto alla mediana delle mediane), l'algoritmo viene richiamato su 7n/10 elementi piu piccoli
Grazie! Sulla seconda sai qualcosa?