Big Oh per (n log n)

Question

Attualmente sto studiando algoritmi di base per Big Oh. Mi stavo chiedendo se qualcuno può mostrarmi quale sia il codice per (n log n) in Java usando Big Oh sarebbe come o indirizzarmi a qualsiasi pagina SO in cui esista.

Dato che sono solo un principiante, posso solo immaginare il codice prima di scriverlo. Quindi, teoricamente (almeno), dovrebbe contenere uno per ciclo in cui abbiamo qualcosa di n volte. Quindi per il log n, possiamo usare il ciclo while. Quindi il ciclo viene eseguito n volte e il ciclo while viene eseguito base di log 2 volte. Almeno è così che lo sto immaginando nella mia testa ma vedere il codice chiarirebbe le cose.

Answer 1

Un algoritmo O (n log n) molto popolare è un tipo di unione. http://en.wikipedia.org/wiki/Merge_sort ad esempio dell'algoritmo e dello pseudocodice. La parte di registro n dell'algoritmo viene ottenuta suddividendo il problema in sottoproblemi più piccoli, in cui l'altezza dell'albero di ricorsione è log n.

Un sacco di ordinamenti di algortihms ha il tempo di esecuzione di O (n log n). Fare riferimento a http://en.wikipedia.org/wiki/Sorting_algorithm per ulteriori esempi.

Answer 2

http://en.wikipedia.org/wiki/Heapsort

Semplice esempio è proprio come lei ha descritto - eseguire n volte qualche operazione che prende log (n). Gli alberi binari bilanciati hanno altezza log (n), quindi alcuni algoritmi ad albero avranno una tale complessità.

Answer 3

int n = 100 
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n) 
{ 
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times 
    { 

    } 
} 

Spiegazione: Il ciclo for esterno dovrebbe essere chiaro. Viene eseguito n volte. Ora al ciclo interno. Nel ciclo interno basta prendere n e dividerlo sempre per 2. quindi ti chiedi: quante volte posso dividere n per 2.

Si scopre che questo è in O (log n). (in effetti la base del log è 2, ma nella notazione Big-Oh lasciamo la base poiché aggiungerebbe solo alcuni fattori al nostro log che non ci interessano).

Quindi si sta eseguendo un ciclo n volte e all'interno di quel ciclo si sta eseguendo un altro ciclo log(n) volte in modo da avere O(n) * O(log n) = O(n log n).

Answer 4

Algoritmi con una complessità di tempo O(.) che coinvolge log n implicano in genere alcune forme di divisione e conquista.

Ad esempio, in MergeSort l'elenco viene dimezzato, ogni parte viene singolarmente fusa e quindi le due metà vengono unite. Ogni lista è dimezzata.

Ogni volta che il lavoro viene dimezzato o ridotto di dimensioni di un fattore fisso, di solito si finisce con un componente log n dello O(.).

In termini di codice, dare un'occhiata all'algoritmo di MergeSort. La caratteristica importante, tipica delle implementazioni, è che è ricorsiva (si noti che lo TopDownSplitMerge si chiama due volte nel codice fornito su Wikipedia).

Tutti gli algoritmi di ordinamento di buon livello hanno complessità temporale O(n log n) e non è possibile fare di meglio nel caso peggiore, vedere Comparison Sort.

Per vedere come appare nel codice Java, solo search! Here's one example.