Pages: [1]   Go Down
Print
Author Topic: Ordinare con Radix sort  (Read 1725 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« on: 01-09-2011, 12:25:10 »

Ragazzi avrei questo esercizio che non sto' proprio capendo come impostarlo:
Si voglio ordinare n numeri interi rappresentabili con m bits.  Si vuole utilizzare il radix sort raggruppando i bits di ogni numero in m cifre. Per utilizzare il radix sort si suddividono i numeri input in gruppi da r cifre. Per quale valore di r il tempo è minimo?
a. r= log m;
b. r= log n;
c. r=2log m;
d. r=2log n;
Come impostare il ragionamento? Grazie a tutti.
« Last Edit: 01-09-2011, 12:31:20 by soeca » Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 01-09-2011, 12:27:34 »

Il tuo esercizio non ha niente ha che fare con le code con priorità. E' un teorema che si trova nel testo nel capitolo su RadixSort.
La risposta è la b), il perchè è spiegato nel testo in questo lemma dopo aver introdotto RadixSort.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #2 on: 01-09-2011, 12:32:07 »

Si scusa.....nel contempo stavo facendo un esercizio sulle code a priorità.......ma di unni mi vinni coda a priorità!!!    

EDIT: Ho trovato il teorema che dicevi.....Grazie del consiglio!!
« Last Edit: 01-09-2011, 12:34:39 by soeca » Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 01-09-2011, 13:50:03 »

Si scusa.....nel contempo stavo facendo un esercizio sulle code a priorità.......ma di unni mi vinni coda a priorità!!!    

EDIT: Ho trovato il teorema che dicevi.....Grazie del consiglio!!

Figurati...XD
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #4 on: 11-09-2011, 17:52:39 »

E' un teorema che si trova nel testo nel capitolo su RadixSort.

Dove esattamente? Non lo trovo!

trovo solo l'esempio pratico.
« Last Edit: 11-09-2011, 19:30:48 by Misa » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #5 on: 12-09-2011, 11:29:30 »

C' è nel paragrafo del radix sort un teorema, ora se non ricordo male(a memoria) dice:

Siano n numeri di b bit ciascuno e r\leq b un intero, allora è possibile ordinare tali numeri con Radix Sort con complessità pari a \theta(b/r)(n+2^r).
E poi in basso spiega meglio la complessità attribuendo i vari valori ad r e b.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #6 on: 12-09-2011, 11:44:53 »

Cavoli, mi servirebbe proprio, e' da ieri sera che sbatto su questa cosa, cercando in ogni angolo della rete esempi pratici. Eppure nel libro sul capitolo del radix sort questa cosa non c'e proprio! Sad
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #7 on: 12-09-2011, 14:17:51 »

Com' è possibile? Io ho pure la seconda edizione, e c' è lì.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: