Dato un insieme di input di n numeri interi nell'intervallo [0..n^3-1], fornire un algoritmo di ordinamento temporale lineare.Ordinamento in tempo lineare?
Questa è una recensione per il mio test di giovedì, e non ho idea di come affrontare questo problema.
Dai un'occhiata anche ai tipi correlati: pigeonhole sort o counting sort, nonché radix sort come menzionato da Pukku.
Non pensi che n^3-1 sia un po 'troppo grande per usare il conteggio sort? se n = 100 avresti 100^3 spazio solo per ordinare. Deve cambiare la base degli interi e usare l'ordinamento Radix. – unj2
Con l'intervallo di numeri con n cifre in [0, n^3 - 1], il numero di cifre d è 3log (n) e l'algoritmo verrà eseguito in O (dn) => O (nlog (n)). L'ordinamento di Radix non è una soluzione lineare. Inoltre, la pigeonhole non è adatta perché il numero di elementi non è "all'incirca uguale" al numero di possibili chiavi. – Gevorg
Dai un'occhiata allo radix sort.
Solo un avvertimento, l'ordinamento radix è lineare solo se hai una lunghezza massima fissa per le tue chiavi ... dato che hai un intervallo di interi, allora sì, può essere lineare, ma questo non sarà sempre il caso. –
Questo è anche noto come "bucket sort". – GoatRider
Con l'intervallo di numeri con n cifre in [0, n^3 - 1], il numero di cifre d è 3log (n) e l'algoritmo verrà eseguito in O (dn) => O (nlog (n)). L'ordinamento di Radix non è una soluzione lineare. – Gevorg
Un set di un numero limitato di numeri può essere rappresentato da una bitmap di bit RANGE. In questo caso, una bitmap da 500mb, quindi per tutto tranne che per liste enormi, starai meglio con Radix Sort. Quando incontri il numero k, imposta la bitmap [k] = 1. Singolo attraversamento della lista, O (N).
Nota che n potrebbe non essere uguale a 2. – Reunanen
E 'davvero semplice, se n = 2 ed i numeri sono unici:
Complessità => O (2n)
In caso contrario, utilizzare Radix Sort:
Complessità => O (kn) (si spera)
La domanda dice n^31 e non 2^31. Inoltre si assume che nessun numero appare più di una volta. –
Sto assumendo n = 2. Penso che sia un errore di battitura. Dopo tutto, in genere non usiamo altre basi di 2. Hai ragione, io sono (probabilmente erroneamente) assumendo che i numeri non vengano ripetuti! – Ash
danbruc, non conosco il tuo background, ma la mia risposta è molto valida e ben bilanciata (se posso dirlo). L'inizializzazione – Ash
wikipedia mostra abbastanza molti algoritmi di ordinamento differenti e la loro complessità.
Quando la gente dice "algoritmo di ordinamento" spesso si riferisce a "algoritmo di ordinamento di confronto", che è un algoritmo che dipende solo dalla possibilità di chiedere "è questa cosa più grande o più piccola di quella ". Quindi, se sei limitato a porre questa domanda sui dati, non otterrai mai più di n * log (n) (questo è il risultato di una ricerca di log (n) degli ordinamenti fattoriali di un set di dati) .
Se riesci a sfuggire ai vincoli di "sorta di confronto" e a porre una domanda più sofisticata su un dato, ad esempio "qual è la base 10 di questi dati" allora puoi inventare un numero qualsiasi di linee algoritmi di ordinamento del tempo, prendono solo più memoria.
Questo è uno scambio spazio nel tempo. Comparason sort prende poca o nessuna ram e funziona in tempo N * log (n). ordinamento radix (ad esempio) eseguito in memoria O (n) e memoria O (log (radix)).
È possibile eseguire un ordinamento di tipo radix – aaronman
@aaronman si può collegare al algoritmo di ordinamento dello spazio costante di tempo lineare? –
Certo, tieni presente che quando dico spazio costante è in riferimento alla dimensione dell'intervallo, lo spazio di archiviazione non è costante rispetto alla dimensione di ciò che viene ordinato (32 bit a 64 bit). un link ([radix] (https://github.com/aaronjosephs/radix/blob/master/radix.cpp)) alla mia stessa implementazione, il codice è disordinato ma è quello chiamato "msd16_radix', usa il conteggio per esegui l'ordinamento, inoltre chiama std :: sort perché è più veloce per gli array di piccole dimensioni, quindi la mia implementazione non è strettamente inplace (se std :: sort utilizza la memoria) ma è chiaro che è possibile ottenerlo. – aaronman
algo simili è possibile:
M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];
È solo possibile algo per complessità lineare, ma ha complessità O (k * N) dal pistone (N - elementi numero matrice, k - dell'elemento len)
Pensa ai numeri come numeri a tre cifre in cui ogni cifra va da 0 a n-1. Ordina questi numeri con ordinamento digitale. Per ogni cifra è presente una chiamata al tipo di conteggio che sta prendendo il tempo Theta (n + n), in modo che il tempo di esecuzione totale corrisponda a Theta (n).
Potresti controllare di nuovo la domanda? N vs n? [0..n^31] vs [0..2^31] vs [0..2^32-1]? –
@danbruc - Buon punto. Inoltre, la revisione 1 dice [0..n^3-1] - perché è [0..n^31] ora? –
Non ho idea del perché sia cambiato. Non ricordo di aver mai aggiornato. –