Pages: [1]   Go Down
Print
Author Topic: Algoritmo Select e Bucket Sort  (Read 620 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« 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?
« Last Edit: 20-12-2012, 16:51:31 by milos224 » Logged
sisal
Matricola
*
Offline Offline

Posts: 87



« Reply #1 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
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #2 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?
Logged
Pages: [1]   Go Up
Print
Jump to: