Informatica I - l'analisi delle prestazioni di MergeSort

Rilevazioni sperimentali delle prestazioni

Le rilevazioni sperimentali mostrano che l'ordinamento con MergeSort è molto più efficiente di quello con SelectionSort. Cerchiamo di fare una valutazione teorica delle prestazioni T(n), che indicherà il numero di accessi richiesti per ordinare un array di n elementi.

Analisi dei tempi di esecuzione

Analizziamo i tempi di esecuzione delle tre fasi:

• Creazione di due sottoarray: 2n

La creazione dei due sottoarray richiede accessi perché tutti gli n elementi devono essere letti e scritti.

• Ordinamento dei due sottoarray (invocazioni ricorsive): T(n/2)

Le invocazioni ricorsive richiedono ciascuna (per definizione: T(n) è il tempo di esecuzione di mergeSort su un array di dimensione n).

• Fusione dei due sottoarray: 2n

La fusione richiede accessi ai sottoarray ordinati (ogni elemento da scrivere nell'array finale richiede la lettura di due elementi, uno da ciascuno dei due array da fondere) più accessi in scrittura nell’array finale.

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

Sommando tutti i contributi:

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

Ora per passare da una fase all'altra si procede per sostituzioni successive:

Facciamolo di nuovo: T(n) = 2T(n/2) + 5n, T(n) = 2T(n/4) + 5n*2

Quindi: T(n) = 2 x T(n/4) + 5 + 5 + 5,8

Se assumiamo 2, 4, 8 come potenze arbitrarie di 2: T(n) = 2 T(n/4) + 52

Se assumiamo per n si ottiene: T(n) = 2 T(n/2) + 52

= (1) + 5 = + 5 log

Determinazione della notazione O-grande

Per trovare la notazione “O-grande”, osserviamo che il termine 5n*log2n cresce più rapidamente di n. Il fattore 5 è ininfluente, come ogni costante moltiplicativa. Nelle notazioni “O-grande” non si indica la base dei logaritmi, perché un logaritmo si può trasformare in un altro log con un fattore moltiplicativo, che va ignorato.

Conclusione

In conclusione, l'algoritmo MergeSort ha tempi di esecuzione T(n) = O(n log n) e ha quindi prestazioni migliori di O(n²).