[Algoritmi] Bucket sort
non ho capito bene come funziona il bucket sort, il mio testo dice:
1) abbiamo "n" chiavi prese da un'insieme totalmente ordinato e sono equidistribuite
(nella mia ignoranza chiedo: cosa intende con insieme totalmente ordinato e equidistribuite?)
2) tramite una scansione a tempo lineare determiniamo l'elemento minimo e massimo dell'insieme
3) mettiamo le chiavi all'interno di una tabella hash (da "n" celle) a catene separate utilizzando la funzione hash
$\h(x) = (n-1) (x-min)/(max-min)\$ (la parte intera inferiore)
(con questa funzione determiniamo l'indice della cella, il bucket)
4) dopodiché il testo usa il mergesort per ordinare le le catene.
5) infine le inseriamo sequenzialmente in una lista ordinata
il testo dice che nel caso medio essendo la tabella composta da n celle e gli elementi da inserire sono n, il fattore di carico è 1 e la lunghezza media di ogni catena è 1.
analisi della complessità:
la scansione per determinare min e max è lineare quindi O(n)
inserire una chiave è O(1), quindi inserire n chiavi è O(n)
ordinare col mergesort è O(n) (solo nel caso in cui le catene sono composte da 1 elemento)
inserire sequenzialmente n elementi nella lista ordinata è lineare O(n)
la domanda che mi pongo è:
se una catena si riempie di 2 elementi invece di 1, la complessità dell'ordinamento diventa O(nlogn) ?
1) abbiamo "n" chiavi prese da un'insieme totalmente ordinato e sono equidistribuite
(nella mia ignoranza chiedo: cosa intende con insieme totalmente ordinato e equidistribuite?)
2) tramite una scansione a tempo lineare determiniamo l'elemento minimo e massimo dell'insieme
3) mettiamo le chiavi all'interno di una tabella hash (da "n" celle) a catene separate utilizzando la funzione hash
$\h(x) = (n-1) (x-min)/(max-min)\$ (la parte intera inferiore)
(con questa funzione determiniamo l'indice della cella, il bucket)
4) dopodiché il testo usa il mergesort per ordinare le le catene.
5) infine le inseriamo sequenzialmente in una lista ordinata
il testo dice che nel caso medio essendo la tabella composta da n celle e gli elementi da inserire sono n, il fattore di carico è 1 e la lunghezza media di ogni catena è 1.
analisi della complessità:
la scansione per determinare min e max è lineare quindi O(n)
inserire una chiave è O(1), quindi inserire n chiavi è O(n)
ordinare col mergesort è O(n) (solo nel caso in cui le catene sono composte da 1 elemento)
inserire sequenzialmente n elementi nella lista ordinata è lineare O(n)
la domanda che mi pongo è:
se una catena si riempie di 2 elementi invece di 1, la complessità dell'ordinamento diventa O(nlogn) ?
Risposte
il mio testo dice:
posso chiederti che testo utilizzi
@mathix: Se una catena si riempie di \(c\) elementi (\(c\) costante) il tempo per ordinarli sarà sempre costante. Discorso diverso si avrebbe invece se si supponesse che le catene si riempissero ad esempio di \( \log \, n \) elementi. In questo caso la complessità non sarebbe più costante e dipenderebbe da \(n\). In ogni caso la funzione \(h(x)\) ha bisogno di una struttura di campo totalmente ordinato per essere definita. Non è sufficiente affermare che le chiavi siano prese da un insieme ordinato. Di fatto in questo caso si sta pensando probabilmente ai reali (o al massimo ai razionali).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo