Perché è mergesort O (log n)?

È O (n * log (n)), non O (log (n)). Come hai accuratamente ipotizzato, l'intero input deve essere iterato e ciò deve avvenire O (log (n)) volte (l'input può essere solo dimezzato O (log (n)) volte). n item iterated log (n) times fornisce O (n log (n)).

È stato dimostrato che nessun tipo di confronto può operare più velocemente di così. Solo gli ordinamenti basati su una proprietà speciale dell'input come radix sort possono superare questa complessità. I fattori costanti di mergesort non sono in genere così grandi, anche se gli algoritmi con una complessità peggiore spesso richiedono meno tempo.

La complessità dell'ordinamento di unione è O (nlogn) e NOT O (logn).

Unisci ordinamento è un algoritmo di divisione e conquista. Pensaci in termini di 3 passaggi -

1. La divisione divide calcola il punto medio di ciascuno dei sottosegmenti. Ognuno di questi passaggi richiede solo O (1) tempo.
2. Il passo di conquista ordina in modo ricorsivo due subarray di n / 2 (per anche n) ciascuno di elementi.
3. Il passo fusione unisce n elementi che richiedono O (n) tempo.

Ora, per i passi 1 e 3 cioè tra O (1) e O (n), O (n) è più alto. Prendiamo in considerazione i passaggi 1 e 3, che impiegano O (n) in totale. Dì che è cn per qualche costante c.

Quante volte vengono eseguiti questi passaggi?

Per questo, guarda l'albero sottostante - per ogni livello dall'alto al basso Il livello 2 chiama il metodo di unione su 2 sotto-array di lunghezza n / 2 ciascuno. La complessità qui è 2 * (cn / 2) = cn Il livello 3 chiama il metodo di unione su 4 sotto-array di lunghezza n / 4 ciascuno. La complessità qui è 4 * (cn / 4) = cn e così via ...

Ora, l'altezza di questo albero è (logn + 1) per un dato n. Quindi la complessità complessiva è (logn + 1) * (cn). Questo è O (nlogn) per l'algoritmo di merge sort.

Creditidell'immagine: Khan Academy

Unisci ordinamento è un algoritmo ricorsivo e la complessità temporale può essere espressa come segue la relazione di ricorrenza.

T(n) = 2T(n/2) + ɵ(n)

La ricorrenza sopra può essere risolta usando il metodo Recurrence Tree o il metodo Master. Cade nel caso II del Metodo Master e la soluzione della ricorrenza è ɵ (n log n).

La complessità temporale di Merge Sort è ɵ (nLogn) in tutti e 3 i casi (peggiore, medio e migliore) poiché l'ordinamento di merge divide sempre l'array in due parti e prende il tempo lineare per unire due metà.

Divide l'array di input in due parti, chiama se stesso per le due metà e quindi unisce le due metà ordinate. La funzione merg () viene utilizzata per unire due metà. L'unione (arr, l, m, r) è un processo chiave che presuppone che arr [l..m] e arr [m + 1..r] siano ordinati e unisca i due sub-array ordinati in uno. Vedi la seguente implementazione C per i dettagli.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Se osserviamo più da vicino il diagramma, possiamo vedere che l'array è diviso ricorsivamente in due parti fino a quando la dimensione diventa 1. Una volta che la dimensione diventa 1, i processi di fusione entrano in azione e iniziano a unire gli array fino a l'array completo è unito.

Gli algoritmi di ordinamento basati su confronto hanno un limite inferiore