Il modo più efficace per trovare i valori migliori

Gli m più grandi elementi di una sequenza di lunghezza n possono essere trovati con O ( n log ( m )), supponendo che il confronto di singoli elementi possa essere fatto in un tempo costante.

Inizia con il caso banale che m = 1.

ROUTINE Maximum
INPUT
    items[1…n] : Ordered
OUTPUT
    max : Ordered
REQUIRES
    n ≥ 1
VARIABLES
    i : Integer
BEGIN
    max ← Ordered.MIN_VALUE
    FOR i ← 1 TO n DO
        IF items[i] > max THEN max ← items[i] FI
    DONE
END

Dovrebbe essere ovvio che questo algoritmo ha complessità O ( n ).

Ora sostituisci la variabile a valore singolo max con un min-heap a dimensione costante di m elementi.

ROUTINE Maxima
INPUT
    items[1…n] : Ordered
OUTPUT
    max[1…m] : Ordered
REQUIRES
    n ≥ m
VARIABLES
    i : Integer
BEGIN
    FOR i ← 1 TO m DO max[i] ← Ordered.MIN_VALUE DONE
    FOR i ← 1 TO n DO
        IF items[i] > max[1] THEN
            ;; Replace the smallest of the current m maximum values by the
            ;; new value and restore the heap property if needed.
            max[1] ← items[i]
            CALL MinHeapifyDown(max)
        FI
    DONE
END

La complessità del caso peggiore verrà raggiunta quando gli input sono ordinati in ordine crescente. In questo caso, l'heap dovrà essere modificato in ogni iterazione, cioè, O ( n ) volte. Il ripristino della proprietà heap di un heap di valore m dopo la sostituzione dell'elemento superiore presenta la complessità O (log ( m )). Quindi, la complessità complessiva non è peggiore di O ( n log ( m )).

Epilogo:

Se m è piccolo, l'algoritmo mostrato sopra avrà prestazioni molto buone e un pattern di accesso alla memoria desiderabile (piccolo set di lavoro ad accesso casuale in max e uno- attraversamento lineare in avanti del tempo di articoli ). Inoltre, non richiede accesso casuale o funzionalità multi-pass della sequenza di input, il che significa che potrebbe essere utilizzato per elenchi collegati o anche dati online che non vengono mai memorizzati nella memoria nella sua interezza. Tuttavia, se m è nell'ordine di O ( n ) e elementi fornisce accesso casuale, quindi un algoritmo di partizionamento come Introselect come suggerito (o suggerito) da Jerry Coffin sarebbe preferito quando raggiunge la complessità O ( n ). In C ++, è persino disponibile nella libreria standard .

Gli elementi M più grandi possono essere trovati con la complessità di O (N).

Sebbene sia generalmente noto per trovare la mediana, l'algoritmo "mediana delle mediane" può essere usato per trovare l'oggetto che sarebbe atterrato in qualsiasi punto in una matrice di quell'array. Ancora più importante (per la situazione attuale) divide anche la matrice in quegli elementi più piccoli di quelli scelti, e quelli più grandi di quelli scelti.

Sebbene tecnicamente sia qualcosa di simile a O (N ² ), l'algoritmo Select di Hoare è solitamente più veloce e decisamente più semplice. È molto simile a Quicksort (che anche Hoare ha inventato). La differenza di base è abbastanza semplice: con Quicksort, si partiziona l'array, quindi si ordina in modo ricorsivo ogni metà. Con Seleziona, partiziona l'array, quindi seleziona ricorsivamente solo nella partizione che contiene l'elemento che ti interessa.

Nel peggiore dei casi, questo elimina solo un elemento per step di partizione - ma a meno che l'ordine di partenza non sia impostato con premeditazione, questa possibilità è abbastanza rara (specialmente con ragionevole cura nella scelta del tuo elemento pivot).

Sebbene non conosca nessuno che lo abbia provato per questa applicazione, sembra che la strategia utilizzata nel Pattern che sconfigge Quicksort si applicherebbe ugualmente bene a questo compito. Non sono sicuro di come funzioni da un punto di vista teorico, ma da un punto di vista pratico sembra probabile (almeno per me) che essenzialmente garantisca la complessità complessiva di O (N).