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

Question

Quindi penso che verrò 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 risultava come due linee rette, con la C 4ms più veloce della controparte Java su 100.000 numeri interi casuali.

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

benchmark Android

Non ero sicuro di come sarebbe stata una linea (n log n), ma non pensavo che sarebbe stata diritta.Volevo solo verificare che questo sia il risultato atteso e che non dovrei cercare di trovare un errore nel mio codice.

Ho inserito la formula in Excel e per la base 10 sembra essere una linea retta con un angolo all'inizio.Ciò è dovuto al fatto che la differenza tra log(n) e log(n+1) aumenta linearmente?

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 a un comportamento lineare. Per capire perché, basta prendere il logaritmo di un paio di numeri molto grandi.

Ad esempio (base 10):

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

Quindi, per ordinare 1.000.000 numeri, un O (n) logN smistamento aggiunge un fattore misero 6 (o poco più poiché la maggior parte degli algoritmi di ordinamento dipenderanno base 2 logaritmi). Non un sacco.

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 un array suffisso.

Un caso semplice è recentemente morso me quando ho cercato di migliorare una cernita Quicksort di brevi stringhe utilizzando radix sorta . Risulta, per brevi stringhe, questo (tempo lineare) radix sort stato più veloce di Quicksort, ma c'era un punto di svolta per ancora relativamente brevi stringhe, dal momento che dipende radix sort cruciale dalla lunghezza delle stringhe si ordina.

Answer 2

A proposito, quicksort è realmente O (n ^ 2), ma con un caso medio di O (nlogn)

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

Per una dimostrazione vedi grafica:

Answer 3

Per divertirti ancora di più in modo simile, prova a tracciare il tempo impiegato N operazioni sulla norma struttura dati insiemi disgiunti.È stato dimostrato che è asintotico N α(N) dove α(N) è l'inverso di Funzione di Ackermann (anche se il tuo solito libro di testo sugli algoritmi probabilmente mostrerà solo un limite di N registro registro N o forse N tronco d'albero* N).Per qualsiasi tipo di numero che potresti incontrare come dimensione di input, α(N) ≤ 5 (e in effetti log*N≤ 5), sebbene si avvicini all'infinito in modo asintotico.

Ciò che suppongo si possa imparare da ciò è che, sebbene la complessità asintotica sia uno strumento molto utile per pensare agli algoritmi, non è esattamente la stessa cosa dell’efficienza pratica.

Answer 4

1. Solitamente la O (n * log (n)) algoritmi hanno un'implementazione logaritmica 2-base.
2. Per n = 1024, log (1024) = 10, in modo da n * log (n) = 1024 * 10 = 10240 calcoli, un aumento di un ordine di grandezza.

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

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

Answer 5

Tutti i dati possono essere tracciati su una linea se gli assi sono scelti in modo corretto: -)

Wikipedia dice Big-O è il caso peggiore (cioè f (x) è O (n) significa f (x) è "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: http://science.slc.edu/~jmarshall/courses/ 2002 / primavera / CS50 / Bigo /

La derivata di log (x) è 1 / x. Questo è quanto velocemente log (x) aumenta al crescere di x. E non è lineare, anche se può apparire come una linea retta, perché si piega così lentamente. Quando si pensa di O (log (n)), penso a come O (N ^ 0 +), vale a dire la più piccola potenza di N che non è una costante, dal momento che qualsiasi potenza costante positiva di N supererà alla fine. Non è accurato al 100%, in modo da professori otterrà arrabbiato con te se spiegare in questo modo.

La differenza tra i registri delle due basi diverse è un moltiplicatore costante. Guardate la formula per la conversione log tra due basi: (Sotto "cambiamento di base" qui: https://en.wikipedia.org/wiki/Logarithm) Il trucco è quello di trattare k e b come costanti.

In pratica, ci sono normalmente sarà qualche piccolo inconveniente a tutti i dati trama. Ci saranno differenze di cose al di fuori del programma (qualcosa scambiando nella CPU prima del vostro programma, cache miss, ecc). Ci vogliono molti percorsi per ottenere dati affidabili. Le costanti sono il peggior nemico di cercare di applicare o-grande a tempo di esecuzione reale. Un algoritmo O (N) con una elevata costante può essere più lento di un O (N ^ 2) algoritmo per abbastanza piccolo N.

Answer 6

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 7

Prova tracciare una linea lineare reale su di esso e vedrete il piccolo aumento. Si noti che il valore Y a 50,0000 è inferiore al valore di Y 1/2 a 100.000.

E 'lì, ma è piccola. Quale è il motivo per O (nlog (n)) è così buono!