O (n) algoritmo per trovare la mediana di una raccolta di numeri

Question

Problema: l'input è una sequenza (non necessariamente ordinata) S = k1, k2, ..., kn di n numeri arbitrari. Considerare la raccolta C di numeri n² della forma min {ki, kj}, per 1 < = i, j < = n. Presenta un tempo O(n) e l'algoritmo dello spazio O(n) per trovare la mediana di C.

Finora ho trovato esaminando C per diversi set S che il numero di istanze del numero più piccolo in S in C è uguale a (2n -1), il prossimo numero più piccolo: (2n-3) e così via fino a quando non si dispone di una sola istanza del numero più grande.

C'è un modo per utilizzare queste informazioni per trovare la mediana di C?

Answer 1

Ci sono un certo numero di possibilità. Uno che mi piace è l'algoritmo di Hoare Select. L'idea di base è simile a Quicksort, tranne per il fatto che quando si recita, si recita solo nella partizione che conterrà il numero (i) che si sta cercando.

Ad esempio, se si desidera la mediana di 100 numeri, si inizierà partizionando l'array, proprio come in Quicksort. Riceverai due partizioni, una delle quali contiene l'elemento 50 ^th. Effettua in modo ricorsivo la tua selezione in quella partizione. Continua finché la tua partizione non contiene un solo elemento, che sarà la mediana (e nota che puoi fare lo stesso per un altro elemento di tua scelta).

Answer 2

Wikipedia ha un buon articolo su Selection algorithms. Se si utilizza C++, l'STL include un algoritmo nth_element() con tempo lineare in media.

Answer 3

Sì, buon puzzle. Possiamo trovare la mediana che si sviluppa sulle linee che hai detto.

In C abbiamo 1 occorrenza di max (k), 3 verificarsi di immediatamente superiore, 5 di più alto successivo e così via

1. Se abbiamo ordinato elementi di C, il numero degli elementi a fianco di il numero più alto è m^2 (somma di numeri dispari)

2. I numeri che ci interessano (per calcolare la mediana) a. Se n è dispari è (n^2 + 1)/2 = alfa b. Se n è nemmeno allora alpha1 = n^2/2 e alpha2 = n^2/2 + 1 ma alpha1 = n^2/2 non è mai un numero quadrato => il numero immediatamente a destra di alpha1 è uguale a alpha1 (la somma dei primi numeri dispari è quadrata) => alpha1 = alpha2.

3. Così si riduce a determinare m tale che m^2 (somma di prima m numeri dispari) è solo superiore (n^2/2)

4. Così tutto si riduce a determinare m = soffitto (n/sqrt (2) e il numero più alto nella sequenza originale. (

5. È possibile trovare facilmente il numero più alto (basta osservare prima m il più grande numero da sinistra) o utilizzare la mediana di median algortithm per farlo in tempo lineare