Che tipo utilizza Java Collections.sort (nodes)?

Penso che sia MergeSort, che è O (n log n).

Tuttavia, il seguente output non è d’accordo:

-1,0000000099000391,0000000099000427 1,0000000099000427,0000000099000346 5,0000000099000391,0000000099000346 1,0000000099000427,0000000099000345 5,0000000099000391,0000000099000345 1,0000000099000346,0000000099000345 

Sto classificando un nodelist di 4 nodes per numero di sequenza, e l’ordinamento sta facendo 6 confronti. Sono perplesso perché 6> (4 log (4)). Qualcuno può spiegarmelo?

PS È un mergesort, ma ancora non capisco i miei risultati.

Grazie per le risposte a tutti. Grazie Tom per aver corretto i miei calcoli.

O (n log n) non significa che il numero di confronti sarà uguale o inferiore a n log n, solo che il tempo impiegato verrà ridimensionato proporzionalmente a n log n. Prova a fare test con 8 nodes o 16 nodes o 32 nodes e controlla i tempi.

Hai ordinato quattro nodes, quindi non hai ottenuto l’ordinamento di unione; ordinamento passato a tipo di inserimento.

In Java, i metodi Arrays.sort () utilizzano l’ordinamento di tipo merge o un quicksort sintonizzato in base ai tipi di dati e al passaggio dell’efficienza di implementazione all’ordinamento di inserimento quando vengono ordinati meno di sette elementi di matrice. (Wikipedia, enfasi aggiunta)

Arrays.sort è utilizzato indirettamente dalle classi Collections.

Un bug report recentemente accettato indica che l’implementazione Sun di Java utilizzerà il timsort di Python in futuro: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

(La monografia timsort, linkata sopra, vale la pena leggerla.)

Un algoritmo A (n) che elabora una quantità di dati n è in O (f (n)), per qualche funzione f, se esistono due costanti strettamente positivi C_inf e C_sup tali che:

C_inf. f (n)

Due cose da notare:

  • Le costanti C reali possono essere qualsiasi cosa e dipendono dai costi relativi delle operazioni (a seconda della lingua, della VM, dell’architettura o della definizione effettiva di un’operazione). Su alcune piattaforms, ad esempio, + e * hanno lo stesso costo, in altri il più tardi è un ordine di grandezza più lento.

  • La quantità ascritta come “in O (f (n))” è un conteggio di operazioni previsto , basato su un modello probabilmente arbitrario dei dati con cui si ha a che fare. Ad esempio, se i tuoi dati sono quasi completamente ordinati, un algoritmo di merge-sort sarà per lo più O (n), non O (n. Log (n)).

Ho scritto alcune cose che potrebbero interessarti dell’algoritmo di ordinamento Java e ho preso alcune misurazioni delle prestazioni di Collections.sort () . L’algoritmo al momento è un mergesort con un ordinamento di inserimento una volta che si scende a una certa dimensione di sottoliste ( NB, questo algoritmo molto probabilmente cambierà in Java 7 ).

Dovresti davvero prendere la notazione Big O come un’indicazione di come l’algoritmo sarà scalabile in generale; per un particolare tipo, il tempo preciso si discosterà dal tempo previsto da questo calcolo (come vedrete sul mio grafico, i due algoritmi di ordinamento che sono combinati hanno caratteristiche di performance diverse, quindi il tempo complessivo per un ordinamento è un un po ‘più complesso).

Detto questo, come guida approssimativa, ogni volta che raddoppi il numero di elementi, se moltiplichi il tempo previsto per 2.2, non sarai molto lontano. (Tuttavia non ha molto senso farlo per liste molto piccole di pochi elementi).