Un algoritmo di ordinamento O (n)

Question

Questa è una domanda sui compiti a casa, quindi vorrei evitare risposte complete e molto preferire suggerimenti se possibile.

Dato un array di numeri casuali A [1 ... x], il programma deve restituire i primi elementi dell'array y in ordine crescente dove 1 < = y < = sqrt (x). Quindi, fondamentalmente, dato un array [5,9,2,8] y = 2, il programma dovrebbe restituire [2,5].

La risposta "ordina prima, restituisci prima articoli" è fuori dalla finestra poiché il meglio che possiamo fare è n * tempo logn con fusione o quicksort. La risposta deve quindi sfruttare il fatto che restituiamo solo al massimo gli elementi sqrt (x), e l'unica altra risposta che ho finora è fare una ricerca for-loop per l'elemento minimo dell'array, rimuovendo il minimo da l'array, stashing in una nuova matrice, dire B, e ripetendo il processo della versione ora più piccolo modificata di a di lunghezza x-1, che ci dà tempo di esecuzione in questo modo:

x + (x-1) + (x-2) + ... + (x-y) 

che conta il numero di iterazione for-loop della ricerca min e ci dà al massimo y o sqrt (x) iterazioni nello scenario peggiore, e ci sono al massimo x elementi nell'array. Quindi abbiamo sqrt (x) * x, che è migliore di O (n * logn) ma non è ancora abbastanza O (n): /.

Answer 1

Suggerimento: Supponete di avere una (n) algoritmo di tempo O di scegliere il y ^esimo elemento ...

Answer 2

realtà sqrt (x) cresce più velocemente di log (x), quindi O (x * sqrt (x)) è peggio di O (n * log (x)). Quindi non hai (ancora) fatto di meglio che ordinare l'intera lista.

Ci sono diversi modi per risolvere questo problema. Per uno di essi, guarda su http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms e guarda tutti gli algoritmi di ordinamento comuni. Quale algoritmo può darti i primi elementi in modo più efficiente?

Answer 3

dove 1 < = y < = sqrt (x)

Nota ciò che questo requisito si dà. Se y ≤ √ x, allora y log y ≤ (√ x log x)/2 ∈ O (x ^{& frac12;} log x) ⊂ O (x).

Il filtro di ordinamento può essere estratto dalla finestra, ma il filtro, quindi l'ordinamento, è accettabile.

Answer 4

Per y, utilizzare le idee di ordinamento rapido, selezionare un numero casuale e dividerlo in 2 parti. Parte 1 (più piccola) e parte 2 (più grande).
Se la lunghezza del Part1 < y, poi fare la partizione in Part2 con y '= y - len (Parte 1) Se la lunghezza del Part1> y, poi fare la partizione in Part1 con y' = y Se la lunghezza del Part1 == y, quindi ordina Part1.

per il partizionamento, la media dovrebbe essere quasi in O (n) (I non può approvare ora, ma è molto veloce) (cercherò di trovare un po 'di materiale per questa parte) ..
Ordina per y richiede ylog (y) < sqrt (x) log (sqrt (x)) -> 1/2 * sqrt (x) * log (x) < 1/2 * sqrt (x) * sqrt (x) => 1/2 x.

Answer 5

Vuoi solo un suggerimento, giusto?

Leggi il commento di random_hacker molto con attenzione nel caso in cui hai perso il grande indizio che sta dando. C'è un algoritmo per l'ordinamento di un array in cui un piccolo, minuscolo cambiamento produrrà il tuo algoritmo.

In generale, se y non è limitato a sqrt (x), si ottiene un algoritmo che funziona in O (x + y * log x), che è O (x) se y = O (x/log x), che è ovviamente il caso in cui y < = sqrt (x).