 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Domande] Per orale
Clicca QUI per vedere il messaggio nel forum |
| miles |
| qualcuno mi può spiegare come modificare quicksort' per avere una pronfondità della stack di O(lgn) nel caso peggiore e come funziona bucketsort per gli interi? |
| mapenzi81 |
Allora....
l ordinamento con quicksort lo puoi risolvere ricorsivamente 2 volte o gestire una delle due chiamate in "locale" e solamente nell'altra usi la ricorsione (ovvero butti nello stack uno dei due array).
Se provi il caso peggiore per le velocita di qs ti ritrovi due array uno d dimensione 1 e l'altro di dimensione n-1.
Mandando nello stack l'array piu grande ti ritrovi a risolvere subito la soluzione piccola (banale ha un solo elemento) mentre nello stack metti la soluzione piu grande....(n-1)...(n-2)......
In realta ci sta per poco tempo perchè la riprendi subito e quindi lo stack si riempie e si svuota immediatamente...
cmq sia..se provi con soluzioni intermedie mettendo l'array piu grande hai una ricorsione che al piu è lg(n)
Per bucketsort devi creare una funzione che trasformi il tuo input da intero a 0<=k<1
Una possibile puo essere
h(k)=(k-min)/(max-min+1)
min e max sono i minimi e i massimi input
provala perchè sto andando a memoria.... |
|
|
|
|
