Home

Federica EU

1/14

Massimo Benerecetti » 2.Algoritmi di Ordinamento: InsertionSort e analisi per casi

Il problema dell’ordinamento

Il problema dell’ordinamento di una sequenza di valori (e.g., numeri) può essere così formulato:

Input : una sequenza di valori.
Output: una permutazione (riordinamento) tale che tra ogni coppia di elementi adiacenti valga “qualche” relazione di ordinamento (ad es. ≤)
Una possibile soluzione è l’algoritmo InsertionSort:
- è efficiente solo per piccole sequenze di numeri;
- è un algoritmo di ordinamento sul posto (per ordinare la sequenza utilizza, al più, una quantità costante di memoria).

InsertionSort: intuizioni

La sequenza in ingresso viene scorsa a partire dal secondo elemento; l’indice j, inizialmente assegnato al secondo elemento, indica l’elemento corrente;
Si considera la sottosequenza a sinistra dell’indice j come già ordinata;
Si seleziona l’elemento precedente a j (ultimo della sottosequenza ordinata) assegnando i = j-1;
Si cerca il posto giusto per l’elemento in posizione j nella sottosequenza ordinata da 1 a i.
Si incrementa j, si torna al passo 2. se la sequenza non è terminata.

Intuizione grafica di InsertionSort: l'elemento in posizione j va inserito nel posto corretto tra 1 e i.

Algoritmo InsertionSort

L’algoritmo seguente risolve il problema:

InsertionSort(array A)

1 for j = 2 to Lenght(A) do

2 Key = A[j] /* Scelta del j-esimo elemento da ordinare */ 3 i = j-1 /* [1...i] è la porzione ordinata */ 4 while (i>0 && A[i]>Key) do

5 A[i+1] = A[i] 6 i=i-1

7 A[i-1] = Key

Analisi di InsertionSort

Procediamo con l’analisi del tempo di esecuzione:

InsertionSort(array A)

1 for j = 2 to Lenght(A) do

2 Key = A[j] 3 i = j-1 4 while (i>0 && A[i]>Key) do

5 A[i+1] = A[i] 6 i=i-1

7 A[i-1] = Key

Analisi di InsertionSort

Il numero di volte in cui le linee 4, 5 e 6 dell’algoritmo vengono eseguite non dipende solo dalla dimensione della sequenza, ma anche dai valori contenuti nella sequenza
In altre parole, anche a parità di dimensione n, due sequenze con valori differenti possono indurre numeri di esecuzioni del ciclo while differenti
Per dar conto di questa dipendenza dalla specifica istanza, introdurremo dei parametri aggiuntivi
Per ogni valore $2 \leq j \leq n$ , introduciamo un parametro $t_j$ che rappresenta il numero di volte in cui la testa del ciclo while viene eseguita quando la variabile j assume il valore j.
Per ogni $2 \leq j \leq n$ , $1 \leq t_j \leq j$
Di conseguenza:
- il numero di esecuzioni della linea 4 sarà la somma, al variare di j, di tutti i valori $t_j$ ;
- il numero di esecuzioni delle linee 5 e 6 sarà la somma, al variare di j, dei i valori $(t_j-1)$ (per ogni valore j, il corpo del ciclo while viene eseguito una volta in meno della testa).

Analisi di InsertionSort

Possiamo ora completare l’analisi del tempo di esecuzione:

InsertionSort(array A)

1 for j = 2 to Lenght(A) do

2 Key = A[j] 3 i = j-1 4 while (i>0 && A[i]>Key) do

5 A[i+1] = A[i] 6 i=i-1

7 A[i-1] = Key

Da cui otteniamo: $T(n) = (c_1+c_2+c_3+c_7) n - (c_2+c_3+c_7) + c_4\sum_{i=2}^{n}t_j+(c_5+c_6)\sum_{i=2}^{n} (t_j-1)$

Analisi per casi

Poiché la definizione di T(n) non dipende solo da n, ma anche dai parametri $t_j$ , non è possibile calcolarla direttamente.
L’algoritmo, infatti, può avere un tempo di esecuzione molto diverso anche per sequenze diverse della stessa lunghezza.
Per procedere ad un’analisi asintotica, analizzeremo il tempo di esecuzione in tre casi paradigmatici:

Caso Migliore: il tempo che l’algoritmo impiega nel caso di sequenze di lunghezza n che richedono il minor lavoro possibile;
Caso Peggiore: il tempo che l’algoritmo impiega nel caso di sequenze di lunghezza n che richedono il maggior lavoro possibile;
Caso Medio: il tempo che mediamente l’algoritmo impiega per ordinare una qualsiasi sequenza di lunghezza n.

Analisi per casi e limiti asintotici

La funzione del tempo di esecuzione nel caso migliore, $T_{min}(n)$ , fornisce una stima del limite inferiore asintotico per il tempo di esecuzione dell’algoritmo;

In altre parole, possiamo affermare che $T(n) = \Omega(T_{min}(n))$

La funzione del tempo di esecuzione nel caso peggiore, $T_{max}(n)$ , fornisce una stima del limite superiore asintotico per il tempo di esecuzione dell’algoritmo;

In altre parole, se nel caso peggiore il tempo risulta essere $T_{max}(n)$ , possiamo affermare che $T(n) = O(T_{max}(n))$

La funzione del tempo di esecuzione nel caso medio, $T_{med}(n)$ , fornisce una stima asintotica per il tempo di esecuzione dell’algoritmo nella maggior parte dei casi;
Quando $T_{max}(n) = \Theta(T_{min}(n))$ possiamo affermare che $T(n) = T_{med}(n) = \Theta(T_{min}(n))= \Theta(T_{max}(n))$ . Non è quindi necessario effettuare l’analisi di caso medio.

Analisi InsertionSort: caso migliore

Il caso migliore si ha quando l’array è già ordinato.
Infatti, in questo caso, per ogni valore di j, non viene mai eseguito il corpo del while ( $A[j-1]\leq Key$ ).

Segue che, per ogni valore di j, $t_j = 1$ e $t_j -1 = 0$ .
L’espressione per T(n) si riduce quindi alla seguente:

$T(n) = (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4\sum_{i=2}^{n} 1 = (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4(n-1) = (c_1+c_2+c_3+c_4)n - (c_2+c_3+c_7)$

Nel caso migliore, quindi, InsertionSort impiega tempo lineare sulla dimensione della sequenza.

Analisi InsertionSort: caso peggiore

Il caso peggiore si ha quando l’array è ordinato in ordine inverso
Infatti, in questo caso, per ogni valore di j, il corpo del while viene eseguito fino a che i=0 ( $A[i] > Key$ , per ogni 0<i<j)
Segue che, per ogni valore di j, $t_j = j$ e $t_j -1 = j-1$ .
L’espressione per T(n) si riduce quindi alla seguente:

$\begin{array}{lcl}T(n) &=& (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4\sum_{i=2}^{n} j + (c_5+c_6)\sum_{i=2}^{n} j-1 = \\[3pt] &=& (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4\frac{(n-1)(n+1)}{2}+ (c_5+c_6)\frac{(n-1)n}{2} = \\[3pt] &=& \frac{c_4+c_5+c_6}{2}n^2+ \frac{(2c_1+2c_2+2c_3+2c_7-c_5-c_6)}{2}n - \frac{(2c_2+2c_3+2c_7-c_4)}{2} \end{array} $

Nel caso peggiore, quindi, InsertionSort impiega tempo quadratico sulla dimensione della sequenza.

Analisi InsertionSort: caso medio

Poiché le funzioni di tempo nel caso migliore e nel caso peggiore non sono asintoticamente equivalenti, è necessaria un’analisi di caso medio.

Per il caso medio è necessario calcolare la media, su tutte le possibili istanze di ingresso, del tempo di esecuzione impiegato dall’algoritmo. Il calcolo di questa media è impraticabile, essendo il numero di sequenze di linghezza n infinito.

In realtà, al fine di calcolare il tempo medio impiegato dall’algoritmo, è sufficiente conoscere il numero medio di spostamenti $t_j$ effettuati.

Analisi InsertionSort: caso medio

In base alle considerazioni precedenti, possiamo, quindi, ragionare come segue:

definiamo il rango di un valore x nella sequenza da 1 a j, rank(x,j), come il numero di elementi della sottosequenza tra 1 e j che sono maggiori di x (per ogni x vale, quindi: $0\leq rank(x,j)\leq j-1$ );

assumendo che tutte le sequenze in ingresso siano equiprobabili, possiamo assumere che anche i valori del rango di x siano tutti equiprobabili, cioè che la probabilità che il rango di x sia uguale al valore k (per ogni $0\leq k \leq j-1$ ) sia $Prob[rank(x,j)=k] = \frac{1}{j}$

poiché rank(A[j],j) rappresenta il numero di spostamenti eseguiti dall’algoritmo, il valore medio del rango corrisponde al valore medio degli spostamenti $t_j$ , otterremo:

$t_j = \sum_{k=0}^{j-1} \frac{1}{j}\cdot k = \frac{1}{j-1}\cdot \sum_{k=1}^{j} \frac{1}{j-1}\cdot k = \frac{j-1}{2} \sim \frac{j}{2}$

Analisi InsertionSort: caso medio

Consideriamo, quindi, per ogni valore di j, $t_j = j/2$ e $t_j -1 = j/2-1$

L’espressione per T(n) si riduce alla seguente:

$\begin{array}{lcl}T(n) &=& (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4\sum_{i=2}^{n} \frac{j}{2} + (c_5+c_6)\sum_{i=2}^{n} \frac{j}{2}-1 = \\[3pt] &=& (c_1+c_2+c_3+c_7)n - (c_2+c_3+c_7) + c_4\frac{(n-1)(n+1)}{4}+ (c_5+c_6)\frac{(n-1)n}{4} = \\[3pt] &=& \frac{c_4+c_5+c_6}{4}n^2+ \frac{(4c_1+4c_2+4c_3+4c_7-c_5-c_6)}{4}n - \frac{(4c_2+4c_3+4c_7-c_4)}{4} \end{array}$

Segue che, anche nel caso medio InsertionSort impiega tempo quadratico sulla dimensione della sequenza.

Conclusioni

In colclusione, dall’analisi effettuata possiamo concludere che il tempo di esecuzione di InsertionSort è asintoticamente quadratico.

Infatti, sia nel Caso Peggiore che nel Caso Medio, esso segue lo stesso andamento delle funzioni quadratiche della forma $T(n) = an^2+bn+c$

Solo nel Caso Migliore il tempo di esecuzione segue l’andamento delle funzioni lineari del tipo $T(n) = an+b$
Rappresentazione grafica delle funzioni di tempo di InsertionSort nei tre casi analizzati (migliore, peggiore, medio).

Rappresentazione grafica delle funzioni di tempo di InsertionSort nei tre casi analizzati (migliore, peggiore, medio).

Le lezioni del Corso

1. Analisi di algoritmi

2. Algoritmi di Ordinamento: InsertionSort e analisi per casi

3. Analisi di algoritmi ricorsivi

4. L'algoritmo di ordinamento HeapSort I

5. L'algoritmo di ordinamento HeapSort II