Algoritmo d'ordinamento ottimo
Devo ordinare un array di dimensione n che contiene numeri nell'intervallo [0...n^3] in un tempo O(n) ma non sò proprio su quale algoritmo basarmi.
Un altro esercizio simile è quello in cui mi si chiede di trovare un algoritmo ottimo per ordinare un array di dimensione n che contiene numeri dell'intervallo [0...n^2], potete aiutarmi per favore?
Un altro esercizio simile è quello in cui mi si chiede di trovare un algoritmo ottimo per ordinare un array di dimensione n che contiene numeri dell'intervallo [0...n^2], potete aiutarmi per favore?
Risposte
Che cosa significa in questo caso esattamente "in un tempo O(n)"? Trovare un algoritmo con quella complessità nel caso migliore o in media è fattibile, ma non mi viene in mente nessun algoritmo che garantisca quella complessità nel caso peggiore.
In particolare sto pensando all'uso del bucket sort con \(n\) bucket. Se i valori sono uniformemente distribuiti allora ogni bucket avrà in media un singolo valore per ogni bucket e quindi l'ordinamento di ogni bucket avverrebbe in tempo costante. Ma nel caso peggiore tutti gli elementi dell'array si potrebbero trovare in un singolo bucket e quindi il tempo di ordinamento dipenderebbe dall'algoritmo usato per ordinare i diversi bucket.
In particolare sto pensando all'uso del bucket sort con \(n\) bucket. Se i valori sono uniformemente distribuiti allora ogni bucket avrà in media un singolo valore per ogni bucket e quindi l'ordinamento di ogni bucket avverrebbe in tempo costante. Ma nel caso peggiore tutti gli elementi dell'array si potrebbero trovare in un singolo bucket e quindi il tempo di ordinamento dipenderebbe dall'algoritmo usato per ordinare i diversi bucket.
Se hai un intervallo di valori numerici interi con il Counting Sort dovresti riuscire ad ordinare in tempo O(n+k).
@davide163: ma in questo caso ha \(k = n^3\)...
Ripensandoci è però invece possibile avere la complessità desiderata anche nel caso peggiore utilizzando il radix sort in modo opportuno.
Ripensandoci è però invece possibile avere la complessità desiderata anche nel caso peggiore utilizzando il radix sort in modo opportuno.
"davide163":
Se hai un intervallo di valori numerici interi con il Counting Sort dovresti riuscire ad ordinare in tempo O(n+k).
il conunting sort non può essere considerato in questo caso.
Si dice esplicitamente che il range dei valori è $[0,n^3]$, e per la complessità del CountSort $k$ è indicato come il massimo valore rappresentabile.
In questo caso $k in O(n^3)$ perciò il counting sort avrebbe complessità $O(max{n,n^3})$ per somma.
#RemovedQuasar:
cosa intendi nel titolo per "algoritmo ottimo"? ha significati diversi a seconda da come lo utilizzi...
EDIT:
ok, mi ha preceduto apatriarca sorry
Come avete consigliato, il Counting Sort è stato il mio primo pensiero ma dopo appunto il costo diventa O(n+k) con k=n^3 e non va bene.
Il Radix Sort dici? Ma quindi dovrei usare però anche un altro algoritmo d'ordinamento "dentro" al Radix Sort.
Costo minimo.
Ah ehm se devo essere sincero non lo sò, questo algoritmo non lo avevo ancora preso in considerazione e me lo devo ripassare
Ripensandoci è però invece possibile avere la complessità desiderata anche nel caso peggiore utilizzando il radix sort in modo opportuno.
Il Radix Sort dici? Ma quindi dovrei usare però anche un altro algoritmo d'ordinamento "dentro" al Radix Sort.
cosa intendi nel titolo per "algoritmo ottimo"? ha significati diversi a seconda da come lo utilizzi...
Costo minimo.
In particolare sto pensando all'uso del bucket sort con n bucket. Se i valori sono uniformemente distribuiti allora ogni bucket avrà in media un singolo valore per ogni bucket e quindi l'ordinamento di ogni bucket avverrebbe in tempo costante. Ma nel caso peggiore tutti gli elementi dell'array si potrebbero trovare in un singolo bucket e quindi il tempo di ordinamento dipenderebbe dall'algoritmo usato per ordinare i diversi bucket.
Ah ehm se devo essere sincero non lo sò, questo algoritmo non lo avevo ancora preso in considerazione e me lo devo ripassare
Non c'è alcun algoritmo dentro al radix sort, forse ti stai confondendo con il già menzionato bucket sort?
Io sapevo che il Radix Sort era un algoritmo usato per ordinare le schede perforate con il seguente codice:
Radix-Sort (A,d)
for i <-1 to d
//us un ordinamento stabile per ordinare l'array A sulla cifra i
La procedura suppone che ogni elemento nell'array A di n elementi abbia d cifre dove la cifra 1 è quella di ordine più basso e d quella di ordine più alto ma non si parla di intervalli (come serve a me invece).
Radix-Sort (A,d)
for i <-1 to d
//us un ordinamento stabile per ordinare l'array A sulla cifra i
La procedura suppone che ogni elemento nell'array A di n elementi abbia d cifre dove la cifra 1 è quella di ordine più basso e d quella di ordine più alto ma non si parla di intervalli (come serve a me invece).
avete ragione ragazzi! scusate mi ricordavo male....
In ogni caso, prova a immaginare i numeri come se fossero in base \(n\) e ad utilizzare il radix sort in questo caso.
"RemovedQuasar":
cosa intendi nel titolo per "algoritmo ottimo"? ha significati diversi a seconda da come lo utilizzi...
Costo minimo.
Algoritmo con costo minimo (o complessità minima), mi pare più accettabile
Per dire "algoritmo ottimo" devi valutare e calcolare il costo del problema (con una limitazione inferiore), che si fa a parte (non è valida la classica limitazione $Omega(nlogn)$ visto che non si utilizza un algoritmo basato su confronti).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo