È un algoritmo di ordinamento più veloce di O (n * log (n))

Question

È un algoritmo di ordinamento più veloce di O (n * log (n))

#1 da (13 voti)
#2 da (0 voti)
#3 da (-1 voti)

2

Se ci sono n variabili ognuna con m possibili valori. (Per intero, m è 2 miliardi qualcosa.)

In primo luogo, mappare ogni valore possibile su un numero intero da 0 a m-1 nell'ordine. E definire le funzioni di mappatura.

index(v): value to integer
value(i): integer to value

Secondo, annulla le variabili n e conta quante volte è apparso ogni valore.

for v in variables {
    counter[index(v)] += 1
}

Infine, metti in loop il contro-array e inserisci i valori nella matrice dei risultati.

for i in 0...m-1 {
    for j in 1...counter[i] {
        result.append(value(i))
    }
}

L'array dei risultati dovrebbe essere ordinato e la complessità di questo algoritmo è O (n + m).

Potrebbe essere migliore di O (n * log (n)) per grandi n e piccole m.

algorithms sorting

posta Jeffrey Chen 19.12.2018 - 08:07

fonte

3 risposte

Leggi altre domande sui tag algorithms sorting

Solo test quando necessario nello sviluppo di software agile: buona o cattiva idea? Creazione di nuovi costruttori per sovrascrivere le variabili di istanza esistenti a scopo di test

score 13 · Answer 1

Congratulazioni, hai re-inventato contando come ! (Non sono sarcastico, le cose indipendentemente vengono re-inventate più volte è una cosa buona , ciò dimostra che è un modo naturale e buono per risolvere i problemi.)

La complessità temporale del conteggio degli ordinamenti è effettivamente migliore di O (n * log n). Si noti che la "barriera" solitamente citata di Ω (n * log n) per "ordinamento" è errata . Questo è il limite inferiore per l'ordinamento basato sul confronto e non per l'ordinamento tutto .

In particolare, l'ordinamento del conteggio non è basato sul confronto, e quindi il limite inferiore per l'ordinamento basato sul confronto non si applica.

score 0 · Answer 2

Se n è grande, allora log (n) è definitivamente maggiore di 1 e n * log (n) maggiore di n . Se m è molto piccolo rispetto a n , allora O (n + m) è vicino a O (n) . Quindi con queste condizioni date, il tuo algoritmo sarebbe più veloce.

Tuttavia, questa migliore prestazione temporale ha un costo in termini di prestazioni nello spazio.

score -1 · Answer 3

-1

Il tuo metodo è ancora N * log (n).

L'indice di funzione (v) è probabilmente una ricerca binaria che è log (x). Esegui n volte, quindi il tuo algoritmo è n * log (n).

risposta data 19.12.2018 - 11:37

fonte