Trovare la mediana di un array non ordinato

Question

Per trovare la mediana di un array non ordinato, possiamo fare un min-heap in O (nlogn) tempo di n elementi, e quindi siamo in grado di estrarre uno per uno n/2 elementi per ottenere la mediana Ma questo approccio richiederebbe tempo (nlogn).

Possiamo fare lo stesso con qualche metodo nel tempo O (n)? Se possiamo, per favore dì o suggerisci qualche metodo.

Answer 1

È possibile utilizzare il Median of Medians algoritmo per trovare mediana di un array non ordinato in tempo lineare.

Answer 2

Quickselect funziona in O (n), questo viene anche utilizzato nella fase di partizione di Quicksort.

Answer 3

Esso può essere fatto utilizzando QuickSelect algoritmo in O (n), fanno riferimento a KTH statistiche d'ordine (algoritmi randomizzati).

Answer 4

L'algoritmo di selezione rapida può trovare il k-esimo elemento più piccolo di un array in tempo di esecuzione lineare (O(n)). Ecco un'implementazione in python:

import random 

def partition(L, v): 
    smaller = [] 
    bigger = [] 
    for val in L: 
     if val < v: smaller += [val] 
     if val > v: bigger += [val] 
    return (smaller, [v], bigger) 

def top_k(L, k): 
    v = L[random.randrange(len(L))] 
    (left, middle, right) = partition(L, v) 
    # middle used below (in place of [v]) for clarity 
    if len(left) == k: return left 
    if len(left)+1 == k: return left + middle 
    if len(left) > k: return top_k(left, k) 
    return left + middle + top_k(right, k - len(left) - len(middle)) 

def median(L): 
    n = len(L) 
    l = top_k(L, n/2 + 1) 
    return max(l) 

Answer 5

come dice Wikipedia, mediana-di-mediane è teoricamente O (n), ma non è utilizzato nella pratica, perché il sovraccarico di trovare perni "buoni" lo rende troppo lento .
http://en.wikipedia.org/wiki/Selection_algorithm

Ecco sorgente di Java per un algoritmo QuickSelect per trovare l'elemento k'th in un array:

/** 
* Returns position of k'th largest element of sub-list. 
* 
* @param list list to search, whose sub-list may be shuffled before 
*   returning 
* @param lo first element of sub-list in list 
* @param hi just after last element of sub-list in list 
* @param k 
* @return position of k'th largest element of (possibly shuffled) sub-list. 
*/ 
static int select(double[] list, int lo, int hi, int k) { 
    int n = hi - lo; 
    if (n < 2) 
     return lo; 

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot 

    // Triage list to [<pivot][=pivot][>pivot] 
    int nLess = 0, nSame = 0, nMore = 0; 
    int lo3 = lo; 
    int hi3 = hi; 
    while (lo3 < hi3) { 
     double e = list[lo3]; 
     int cmp = compare(e, pivot); 
     if (cmp < 0) { 
      nLess++; 
      lo3++; 
     } else if (cmp > 0) { 
      swap(list, lo3, --hi3); 
      if (nSame > 0) 
       swap(list, hi3, hi3 + nSame); 
      nMore++; 
     } else { 
      nSame++; 
      swap(list, lo3, --hi3); 
     } 
    } 
    assert (nSame > 0); 
    assert (nLess + nSame + nMore == n); 
    assert (list[lo + nLess] == pivot); 
    assert (list[hi - nMore - 1] == pivot); 
    if (k >= n - nMore) 
     return select(list, hi - nMore, hi, k - nLess - nSame); 
    else if (k < nLess) 
     return select(list, lo, lo + nLess, k); 
    return lo + k; 
} 

Non ho incluso la fonte dei metodi confrontare e scambiare, quindi è facile cambia il codice per lavorare con Object [] invece di double [].

In pratica, è possibile che il codice precedente sia o (N).

Answer 6

Ho già upvoted la risposta @dasblinkenlight poiché l'algoritmo bfprt infatti risolve questo problema in O (n). Voglio solo aggiungere che questo problema potrebbe essere risolto in tempo O (n) usando anche gli heap. La compilazione di un heap può essere eseguita in tempo O (n) utilizzando il valore bottom-up. Dai uno sguardo al seguente articolo per una spiegazione dettagliata

Supponendo che l'array abbia N elementi, devi creare due heap: Un MaxHeap che contiene i primi N/2 elementi (o (N/2) +1 se N è dispari) e un MinHeap che contiene gli elementi rimanenti. Se N è dispari, la tua mediana è l'elemento massimo di MaxHeap (O (1) ottenendo il massimo). Se N è pari, allora la tua mediana è (MaxHeap.max() + MinHeap.min())/2 anche questo richiede O (1). Pertanto, il costo reale dell'intera operazione è l'operazione di creazione dell'heap che è O (n).

BTW questo algoritmo MaxHeap/MinHeap funziona anche quando non si conosce il numero degli elementi dell'array in precedenza (se si deve risolvere lo stesso problema per un flusso di numeri interi per e.g). È possibile visualizzare ulteriori dettagli su come risolvere questo problema nel seguente articolo Median Of integer streams