Merge sort: differenze tra le versioni

Versione delle 00:26, 23 ott 2011

Versione delle 00:27, 23 ott 2011

Riga 161:

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

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 è maggioreminore 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).