Merge sort: differenze tra le versioni

Versione delle 00:27, 23 ott 2011

Versione delle 09:09, 23 ott 2011

Riga 161:

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

Da notare che questa complessità si mantiene tale in ogni caso, da quello migliore a quello peggiore, ed è questo uno dei punti di forza dell'algoritmo.

Questa complessità si ha nel caso peggiore, cioè quando l' array viene diviso in due sottovettori che hanno valori entrambe crescenti, ma l' elemento i-esimo del primo array è minore dell' elemento i-esimo del secondo array e maggiore dell' elemento (i-1)-esimo del secondo array (come ad esempio v[]={1,3,5,7,2,4,6} che viene diviso in v1[]={1,3,5,7} e in v2[]={2,4,6}).

Nel caso migliore , cioè il caso di un array già ordinato, durante la procedura di merge si fanno al più n/2 confronti (se n è la dimensione dell' array).Per cui nel caso migliore la complessità è Θ(n).

== Altri progetti ==