Merge sort: differenze tra le versioni

Versione delle 13:26, 14 feb 2006

Versione delle 21:33, 15 apr 2006

Riga 180:

Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(nlogn). Infatti:

- la funzione merge 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

- la funzione mergesort ha costo 2T(n/2)=Θ(nlogn)

2T(n/2)+ Θ(n)

che per il secondo caso del teorema master è Θ(nlogn).

- la funzione merge ha costo T(n)=Θ(n)

il risultato è T(n)=Θ(nlogn)+ Θ(n)=Θ(nlogn)

[[de:Mergesort]]