Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Jump to navigation Jump to search
Se k è invece maggiore di n, l'algoritmo può risultare peggiore anche dei più classici algoritmi di ordinamento per confronto a tempo quasi lineare, come [[Quicksort]] o [[Mergesort]].
 
Usando come base dell'algoritmo un valore B = Θ(n) il tempo di ordinamento diviene <math>\mathcal{O}(n * (1 + {log (k) \over log (n) } ))</math>
 
La precedente definizione è dimostrabile ricordando che ci sono <math>log_n (k) = \mathcal{O}(log_n (k))</math> passate di [[Integer sort]] e ciascuna richiede tempo <math>\mathcal{O}(n)</math>.
 
Usando le regole per il cambiamento di base dei [[logaritmo|logaritmi]], il tempo totale è dato da <math>\mathcal{O}(n log_n (k)) = \mathcal{O}(n {log (k) \over log (n)})</math>. A questa quantità va aggiunto <math>\mathcal{O}(n)</math> per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.
 
==Implementazione in Java==
1

contributo

Menu di navigazione