Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

  1. La sequenza in ingresso viene scorsa a partire dal secondo elemento; l’indice j, inizialmente assegnato al secondo elemento, indica l’elemento corrente;
  2. Si considera la sottosequenza a sinistra dell’indice j come già ordinata;
  3. Si seleziona l’elemento precedente a j (ultimo della sottosequenza ordinata) assegnando i = j-1;
  4. Si cerca il posto giusto per l’elemento in posizione j nella sottosequenza ordinata da 1 a i.
  5. 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.

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 \xrightarrow{\hspace{3cm}} c_1n

2 Key = A[j] \xrightarrow{\hspace{3cm}} c_2(n-1)
3 i = j-1 \xrightarrow{\hspace{3cm}} c_3(n-1)
4 while (i>0 && A[i]>Key) do \xrightarrow{\hspace{2cm}} c_4 ?

5 A[i+1] = A[i] \xrightarrow{\hspace{3cm}} c_5 ?
6 i=i-1 \xrightarrow{\hspace{3cm}} c_6 ?

7 A[i-1] = Key \xrightarrow{\hspace{3cm}} c_7(n-1)

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 \xrightarrow{\hspace{3cm}} c_1n

2 Key = A[j] \xrightarrow{\hspace{3cm}} c_2(n-1)
3 i = j-1 \xrightarrow{\hspace{3cm}} c_3(n-1)
4 while (i>0 && A[i]>Key) do \xrightarrow{\hspace{2cm}}c_4\sum_{i=2}^{n} t_j

5 A[i+1] = A[i] \xrightarrow{\hspace{2cm}}c_5\sum_{i=2}^{n} (t_j-1)
6 i=i-1 \xrightarrow{\hspace{2cm}}c_6\sum_{i=2}^{n} (t_j-1)

7 A[i-1] = Key \xrightarrow{\hspace{3cm}} c_7(n-1)

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]<br />
    &=& (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]<br />
    &=& \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}<br />

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]<br />
      &=& (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]<br />
      &=& \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).

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


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion