O (N log N) Complessità - Simile al lineare?

Question

Quindi penso che sto per essere sepolto per aver fatto una domanda così banale ma sono un po 'confuso su qualcosa.

Ho implementato quicksort in Java e C e stavo facendo alcuni confronti di base. Il grafico è venuto fuori come due linee rette, con il C che è 4ms più veloce della controparte Java su 100.000 numeri interi casuali.

Il codice per i miei test può essere trovato qui;

android-benchmarks

non ero sicuro di quello che una (n log n) la linea sarebbe simile, ma non pensavo che sarebbe dritto. Volevo solo verificare che questo fosse il risultato previsto e che non dovrei provare a trovare un errore nel mio codice.

Ho bloccato la formula in Excel e per la base 10 sembra essere una linea dritta con un nodo all'inizio. Questo perché la differenza tra log (n) e log (n + 1) aumenta in modo lineare?

Grazie,

Gav

Answer 1

rendere il grafico più grande e vedrete che O (n log n) non è una linea abbastanza dritto. Ma sì, è abbastanza vicino al comportamento lineare. Per capire perché, prendi il logaritmo di alcuni numeri molto grandi.

Ad esempio (base 10):

log(1000000) = 6 
log(1000000000) = 9 
… 

Così, per ordinare 1.000.000 numeri, un O (n log n) Sorting aggiunge un fattore misero 6 (o poco più poiché la maggior parte degli algoritmi di ordinamento dipenderanno base 2 logaritmi). Non molto.

In realtà, questo fattore di registro è così straordinariamente piccola che per la maggior parte degli ordini di grandezza, con sede O (n log n) algoritmi di sovraperformare algoritmi di tempo lineare. Un esempio importante è la creazione di una struttura di dati dell'array suffisso.

Un caso semplice mi ha recentemente morso when I tried to improve a quicksort sorting of short strings by employing radix sort. Risulta, per le stringhe corte, questo ordinamento di tipo (tempo lineare) è stato più veloce di quicksort, ma c'era un punto di svolta per le stringhe ancora relativamente corte, dato che l'ordinamento radix dipende in modo cruciale dalla lunghezza delle stringhe che si ordinano.

Answer 2

log (N) è (molto) più o meno il numero di cifre in N. Così, per la maggior parte, c'è poca differenza tra log (n) e log (n + 1)

Answer 3

Prova tracciare un la linea lineare attuale sopra e vedrai il piccolo aumento. Notare che il valore Y a 50.0000 è inferiore al valore 1/2 Y a 100.000.

È lì, ma è piccolo. Ecco perché O (nlog (n)) è così buono!

Answer 4

1. Di solito gli algoritmi O (n * log (n)) hanno un'implementazione logaritmica a 2 basi.
2. Per n = 1024, log (1024) = 10, quindi n * log (n) = 1024 * 10 = 10240 calcoli, un aumento di un ordine di grandezza.

Quindi, O (n * log (n)) è simile al lineare solo per una piccola quantità di dati.

Suggerimento: non dimenticare che quicksort si comporta molto bene su dati casuali e che non è un algoritmo O (n * log (n)).

Answer 5

Per un divertimento ancora più simile, provare a calcolare il tempo impiegato dalle operazioni n sullo standard disjoint set data structure. E 'stato dimostrato di essere asintoticamente n   α (n) dove α (n) è l'inverso della Ackermann function (anche se il tuo algoritmi soliti libri di testo sarà probabilmente solo mostrare un balzo di n Ceppo n o eventualmente n   log*   n). Per qualsiasi tipo di numero che si sarà probabile incontrare come la dimensione di input, α (n)   ≤   5 (e in effetti il ​​login *   n   ≤   5), anche se lo fa approccio all'infinito asintoticamente.

Ciò che suppongo tu possa imparare da questo è che mentre la complessità asintotica è uno strumento molto utile per pensare agli algoritmi, non è esattamente la stessa cosa dell'efficienza pratica.

Answer 6

proposito, quicksort è in realtà O (n^2), ma con un caso medio di O (nlogn)

proposito, c'è una bella differenza tra O (n) e O (nlogn). Ecco perché non è delimitata da O (n) per nessuna costante.

Per una dimostrazione grafica vedere:

Answer 7

Tutti i dati possono essere rappresentate graficamente su una linea se gli assi sono scelti correttamente :-)

Wikipedia dice Big-O è il caso peggiore (cioè f (x) è O (N) significa f (x) viene "limitata superiormente" di N) https://en.wikipedia.org/wiki/Big_O_notation

Ecco una bella serie di grafici che rappresentano le differenze tra le varie funzioni comuni: 01.239.706,27019 milioni

La derivata di log (x) è 1/x. Questo è quanto velocemente log (x) aumenta con l'aumentare di x. Non è lineare, anche se può sembrare una linea retta perché si piega lentamente. Quando penso a O (log (n)), lo considero come O (N^0 +), cioè il più piccolo potere di N che non è una costante, poiché ogni potere costante positivo di N lo supererà alla fine. Non è preciso al 100%, quindi i professori si arrabbieranno con te se lo spieghi in questo modo.

La differenza tra i registri di due basi diverse è un moltiplicatore costante. Cerca la formula per convertire i registri tra due basi: (sotto "cambio di base" qui: https://en.wikipedia.org/wiki/Logarithm) Il trucco è trattare k e b come costanti.

In pratica, di solito ci sarà qualche singhiozzo in qualsiasi dato che trama. Ci saranno delle differenze nelle cose al di fuori del tuo programma (qualcosa che si sta spostando nella CPU prima del tuo programma, errori di cache, ecc.). Ci vogliono molte esecuzioni per ottenere dati affidabili. Le costanti sono il più grande nemico nel tentativo di applicare la notazione Big O al runtime attuale. Un algoritmo O (N) con una costante elevata può essere più lento di un algoritmo O (N^2) per un numero abbastanza piccolo N.