trovare mediana con il tempo minimo in un array

Question

Ho un allineamento permette di dire a = { 1,4,5,6,2,23,4,2}; ora devo trovare mediana di posizione di matrice da 2 a 6 (termini totale dispari), quindi quello che ho fatto, ho preso a[1]-a[5] in arr[0] a arr[4] quindi l'ho ordinato e scrivo lo arr[2] come mediana.

Ma qui ogni volta inserisco i valori da una matrice all'altra, in modo che i valori della matrice iniziale rimangano gli stessi. in secondo luogo ho ordinato, quindi questa procedura sta prendendo più o meno **time**. Quindi voglio sapere se esiste un modo per farlo in modo diverso da less my computation time.

Qualsiasi sito web, materiale per capire, cosa e come fare?

Answer 1

Se si sta facendo più query dello stesso array allora si potrebbe utilizzare un segmento dell'albero. In genere vengono utilizzati per eseguire intervalli di valori minimi/massimi e di intervallo, ma è possibile modificarli in intervalli mediani.

Un albero del segmento per un set con n intervalli utilizza l'archiviazione O (n log n) e può essere costruito nel tempo O (n log n). Una query di intervallo può essere eseguita in O (log n).

Esempio di mediana in albero segmento gamma:

si genera l'albero di segmento dal basso verso l'alto (aggiornamento dall'alto verso il basso):

    [5] 
     [3]      [7] 
[1,2]  [4]   [6]   [8] 
1  2  3  4  5  6  7  8 

Indici coperte dal nodo:

    [4] 
     [2]      [6] 
[0,1]  [3]   [5]   [7] 
0  1  2  3  4  5  6  7 

Una query per mediana per gli indici di intervallo di 4-6 scenderebbe su questo percorso di valori:

    [4] 
          [5] 
0  1  2  3  4  5  6  7 

Facendo una ricerca per la mediana, si conosce il numero di elementi totali nella query (3) e la mediana in tale intervallo sarebbe il 2 ° elemento (indice 5). Quindi stai essenzialmente facendo una ricerca per il primo nodo che contiene quell'indice che è un nodo con valori [1,2] (indici 0,1).

Fare una ricerca della mediana dell'intervallo 3-6 è un po 'più complicato perché devi cercare due indici (4,5) che si trovano nello stesso nodo.

    [4] 
           [6] 
          [5] 
0  1  2  3  4  5  6  7 

Segment tree

Range minimum query on Segment Tree

Answer 2

È possibile trovare la mediana senza ordinare in O (n); gli algoritmi che lo fanno si chiamano selection algorithms.

Answer 3

Per trovare la mediana di un array di meno di 9 elementi, penso che il più efficiente sia utilizzare un algoritmo di ordinamento come tipo di inserimento. La complessità è cattiva, ma per un array così piccolo a causa della k nella complessità di algoritmi migliori come quicksort, l'ordinamento di inserimento è molto efficiente. Fai il tuo benchmark ma posso dire che otterrai risultati migliori con l'ordinamento degli inserimenti rispetto a quelli di shell sort o quicksort.

Answer 4

Usa std::nth_element da <algorithm> che è O (N):

nth_element(a, a + size/2, a + size); 
median = a[size/2]; 

Answer 5

Credo che il modo migliore è utilizzare il bfprt algoritmo di contare il grande elemento k-esimo di una matrice. Puoi trovare l'idea generale dell'algoritmo qui: Median of Medians in Java, su wikipedia: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm o semplicemente navigare in internet. Alcuni miglioramenti generali possono essere apportati durante l'implementazione (evitare l'ordinamento quando si sceglie la mediana di particolari matrici). Tuttavia, si noti che per un array di meno di 50 elementi è più efficiente utilizzare l'ordinamento di inserimento rispetto all'algoritmo mediano di mediani.