Pages: [1]   Go Down
Print
Author Topic: Esercizio Compito  (Read 584 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: 29-08-2011, 19:04:01 »

Ragazzi mi potreste aiutare a ragionare su questo esercizio?
Il testo è il seguente:
sia A un array di n numeri tutti compresi tra 0 e n^2 -1. Quali dei seguenti algoritmi di ordinamento conviene usare?
a. heapsort
b. counting sort
c. radix sort
d. bucket sort

Secondo me la risposta corretta è la "b" counting sort!Ho risposto così per il seguente ragionamento: l'heapsort ha una complessità O(nlogn) che rispetto ai restanti 3 è nettamente superiore(infatti negli altri 3 è lineare!) quindi l'ho escluso a priori!Il radix sort si basa sul numero di cifre è sinceramente non mi pare di avere informazioni sul numero di cifre,il bucket sort invece si basa su numeri inclusi nell'intervallo [0,1[ che a meno che non stia dimenticando qualcosa non dovrebbe rientrare tra i valori dati nell'esercizio!!Il counting sort invece ordina dei numeri tra 0 e k e per esempio k=n^2 -1!! Che ne pensate di questo ragionamento è corretto e quindi la risposta data è corretta o no???Grazie a tutti!!!
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: 29-08-2011, 20:54:47 »

Anche io ho visto questo proprio ieri. Io ero indeciso tra la b) e la d). Istintivamente mi veniva da dire d) perchè:
Se consideri che counting sort se non erro ordina in \theta(n+k) la complessità dovrebbe essere \theta(n^2). Mentre bucket sort ordina in tempo lineare se non erro. Questo è l' unico motivo per cui mi verrebbe da dire d), però considerando il tuo ragionamento sul fatto che bucket impone che l' input sia distribuito in un intervallo, mi porta ad essere d' accordo con te.
Leggi qui:

http://forum.sdai.unict.it/index.php?topic=13516.0

Forse in questo caso, in cui c' è un insieme con interi compresi in un intervallo preciso, numerico e specificato si può usare bucket. Qui visto che sono n compresi tra 0 ed n^2-1 si può usare counting sort con k=n^2-1.
Non resta che sperare in una luce dall' alto  yoh.
« Last Edit: 29-08-2011, 20:58:40 by Daréios » Logged

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