Merge sort: differenze tra le versioni

Versione delle 14:19, 29 ott 2011

Versione delle 20:27, 29 ott 2011

Riga 155:

Il tempo di esecuzione dell'algoritmo Merge Sort è [[Stima asintotica#Relazione Theta .CE.98|Θ]](n log n). Infatti:

- la funzione merge qui presentata ha costo Θ(n), e mergesort richiama se stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale

<math>T(n) = 2T\left(\frac{n}{2}\right)+ \Theta(n)</math>

Riga 161:

che per il secondo caso del [[teorema master]] è Θ(''n''log''n'').

LaEsistono implementazioni più efficienti della procedura Mergemerge, che hahanno nel caso migliore complessità O(1),; infatti, se i due array da fondere sono già ordinati, basteràè sufficiente confrontare l' ultimo elemento del primo array con il primo elemento del secondo array per sapere che si può fonderli senza effettuare ulteriori confronti. Per cui si può implementare l'algoritmo mergesort in modo che abbia complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l'array è già ordinato.

Altrimenti se gli array non sono ordinati la procedura Merge ha complessità O(n).

Per cui l' algoritmo di mergesort ha complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l' array è già ordinato.

== Altri progetti ==