Capitolo 9
Complessità e algoritmi di ordinamento
Ordinamento bubble sort e shake sort.
Ordinamento per inserzione diretta.
9.1 Complessità computazionale.
Abbiamo visto in precedenza (Cap. 3) cosa intendiamo per problema risolvibile e algoritmo.
Affrontiamo ora il seguente problema: dato un problema risolvibile P, e due algoritmi A e B che risolvono P, è possibile dire quale tra i due algoritmi sia "il migliore" ?
Siamo cioè interessati a determinare un modo per definire se un algoritmo è "buono", se un algoritmo è "migliore" di un altro.
Per confrontare le prestazioni degli algoritmi è necessario definire una misura della loro efficienza. Per risultare utile, questa misura deve essere indipendente dalla macchina. Intuitivamente possiamo dire che la misura più utile è il tempo richiesto per eseguire l'algoritmo . Il modo piu semplice per definire la misura del tempo di esecuzione di un algoritmo (complessità temporale) è quello di calcolare il numero di operazioni elementari che l'algoritmo deve compiere in funzione delle dimensioni del problema.
Esempio 1. Stimare la complessità temporale del seguente algoritmo:
FOR i:= 1 TO N DO
x[i]:= 3*x[i] + 1
Possiamo notare che sono svolte N moltiplicazioni, N addizioni e N operazioni di assegnamento. Stimando approssimativamente uguale il tempo per ciascuna operazione elementare possiamo dire che il programma descrive 3*N operazioni.
Ora, poiché vogliamo studiare la complessità temporale in funzione delle dimensioni del problema, possiamo ritenere trascurabile la presenza della costante 3. Questo si indica scrivendo O(n) - leggi "è di ordine n", che significa che il numero delle operazioni elementari che sono compiute è proporzionale a N.
Esempio 2. Stimare la complessità temporale del seguente algoritmo:
FOR i:= 1 TO N DO
FOR j:= 1 TO N DO
x[i,j]:= x[i,j] + 1
Per i=1, il programma descrive N addizioni e N assegnazioni, cioè 2*N operazioni elementari. Lo stesso numero per i=2, i=3,..,i=N.
Compie quindi 2*N^2 operazioni elementari e quindi possiamo indicare la complessità temporale con O(n^2).
Definizione.
La complessità computazionale temporale di un algoritmo è una misura dell'ordine di grandezza del numero di operazioni elementari che un algoritmmo deve compiere espressa in funzione della dimensione del problema.
Esempio 3. Analizziamo l'algoritmo di ordinamento di un vettore proposto alla fine del capitolo 6 (ordinamento per selezione diretta).
Trascurando la parte di dichirazione delle variabili, l'algoritmo è il seguente:
BEGIN
FOR k:=1 TO n-1 DO BEGIN
max:=v[k];
i_max:=k;
FOR i:=k+1 TO n DO
IF v[i]>max THEN BEGIN
max:=v[i];
i_max:=i;
END;
v[i_max]:=v[k];
v[k]:=max;
END
END.
Possiamo individuare tre tipi di operazioni elementari:
Per k=1 vengono effettuate n-1 confronti e uno scambio.
Per k=2 vengono effettuati n-2 confronti e uno scambio.
Generalizzando, per ogni valore di k dobbiamo eseguire uno scambio e n-k confronti. I confronti saranno quindi:
1 + 2 + 3 + .. + n-1 = n * (n - 1) /2
Gli scambi saranno quindi:
1 + 1 + 1 (N-1 volte) = n-1
Tenendo conto che ogni operazione di scambio richiede tre operazioni elementari la somma delle operazioni di confronto con quelle di scambio risulta essere:
(n^2 - n) / 2 + 3 * n - 3 = (1/2)*n^2 + (5/2)*n - 3
Abbiamo fino a questo punto analizzato solo due delle tre fasi in cui avevamo scomposto l'analisi (la prima e la terza): in effetti la seconda è quella che crea più problemi. Supponiamo ad esempio che il vettore risulti già ordinato: la condizione v[i] > max risulterà sempre falsa e quindi il numero di operazioni interne risulta uguale a 0.
Se invece il vettore è ordinato in modo inverso il numero di operazioni che si svolgeranno all'interno della IF saranno circa N^2 / 4.
Questo significa che, secondo come vengono forniti i dati in ingresso, il numero di operazioni elementari che l'algoritmo svolge può cambiare in modo anche sensibile.
Il calcolo della complessità temporale di un algoritmo ci porterà quindi ad analizzare tre casi:
Definiamo in modo preciso la complessità media:
Siano
Il numero medio di operazioni elementari sarà:
Nmed = Sommatoria(i:1,k) p(Ki) * Nop(Ki)
In generale, il calcolo del numero medio di operazioni che svolge un algoritmo risulta complesso. Nel seguito, eccetto che per i casi semplici, daremo una stima intuitiva della complessità media.
Nel caso precedente per il numero di operazioni elementari op si ha:
(1/2)*n^2 + (5/2)*n - 3 <= op <= (1/2)*n^2 + (5/2)*n - 3 + n^2 / 4
le complessità risultano:
C_min = C_med = C_max = O(n^2)
E` importante tener presente che il dire che la complessità minima, media e massima coincidono non significa dire che sono uguali il numero di operazioni elementari nei tre casi, bensì l'ordine di grandezza dei tre casi è uguale.
Determinando un metodo per analizzare il numero di operazioni di un algoritmo ci siamo dotati di uno strumento per poter confrontare algoritmi diversi che risolvono lo stesso problema.
Possiamo ora rispondere alla domanda che ci eravamo posti in partenza:
dato un problema P e due algoritmi A e B che risolvono P, diremo che A è più efficiente di B se la complessità computazionale temporale di A è minore di quella di B.
Esempio 4. Analizziamo la complessità dell'algoritmo di ricerca di un elemento in un vettore proposto nel capitolo 6.
L'algoritmo è il seguente:
v[n+1]:=x;
i:=0;
REPEAT
i:=i+1;
UNTIL v[i]=x;
IF i=n+1 THEN
WRITELN('NON TROVATO ')
ELSE
WRITELN('TROVATO ALLA POSIZIONE ',i);
Il programma svolge sempre le seguenti operazioni una sola volta:
v[n+1]:=x; i:=0; confronto tra i e n+1; una writeln;
Quello che determina la complessità del programma è quindi sostanzialmente il numero addizioni e assegnamenti che avvengono all'interno del ciclo REPEAT/UNTIL.
C_min: l'elemento viene trovato alla prima posizione del vettore; le operazioni svolte sono quindi 2 (una addizione e un assegnamento).
C_max: l'elemento viene trovato alla posizione n+1; il numero di operazioni svolte risulta 2*(n+1).
C_med: la complessità media è data dalla media delle complessità dei casi possibili. I casi possibili sono n+1 e cioè elemento alla posizione 1, alla posizione 2, ... , alla posizione n+1. Risulterà quindi:
(2 / (n+1)) * (1+2+3..+(n+1)) = n+2
nell'ipotesi che gli n+1 casi possibili siano equiprobabili.
Abbiamo quindi:
C_min = O(1) e C_med = C_max = O(n)
Abbiamo visto in precedenza un algoritmo per la ricerca di un elemento in un vettore. Vediamo ora come scrivere un algoritmo più efficiente nell'ipotesi che il vettore sia ordinato.
Supponiamo di avere un vettore V di 100 elementi ordinati in ordine crescente ed un elemento E da cercare nel vettore:
confrontiamo E con V[50]
L'idea di base è molto semplice: l'algoritmo terminerà quando si trova l'elemento oppure il vettore su cui restringiamo la ricerca è vuoto.
FUNCTION ricerca_binaria (a:vettore; n,elemento:INTEGER):INTEGER;
VAR
inizio,fine,medio:INTEGER;
trovato:BOOLEAN;
BEGIN
inizio:=1;
fine:=n;
trovato:= FALSE;
WHILE (inizio <= fine) AND (not trovato) DO BEGIN
medio:= (inizio + fine) div 2;
IF a[medio] = elemento THEN
trovato:=TRUE
ELSE
IF a[medio] < elemento THEN
inizio:=medio + 1
ELSE
fine:= medio -1
END;
IF trovato THEN ricerca_binaria:=medio
ELSE ricerca_binaria:=-1
END;
Poichè ad ogni passo si dimezza il numero di elementi su cui effettuare la ricerca si ottieme immediatamente:
C_min = O(1) C_med = C_max = O(log(n))
N.B. Non è necessario specificare la base del logaritmo poichè
Loga x = logc x / logca
e quindi la base del logaritmo non modifica l'ordine di grandezza ma solo la costante moltiplicativa.
Un confronto tra i due algoritmi ci dice che, nel caso di un vettore di 1024 elementi, sono mediamente necessari 10 confronti per determinare la posizione dell'elemento ricercato contro i 512 del metodo precedente.
Una versione ricorsiva dello stesso algoritmo è la seguente:
FUNCTION ricerca_binaria1 (VAR a:vettore;p1,p2,elemento:INTEGER):INTEGER;
VAR
medio :INTEGER;
BEGIN
IF p2 < p1 THEN ricerca_binaria1:= -1
ELSE BEGIN
medio:=(p1 + p2) div 2;
IF a[medio]=elemento THEN
ricerca_binaria1:=medio
ELSE
IF a[medio] < elemento THEN
ricerca_binaria1:=ricerca_binaria1(a,medio+1,p2,elemento)
ELSE
ricerca_binaria1:=ricerca_binaria1(a,p1,medio-1,elemento)
END
END;
9.3 Ordinamento per scambio diretto (bubblesort, shakesort)
L'ordinamento per scambio diretto è basato sul principio di confrontare ed eventualmente scambiare coppie di elementi adiacenti fino a quando il vettore è ordinato.
Supponiamo di avere il seguente vettore:
V: 12 3 7 15 2
Si confronta 12 con 3: 12 è maggiore di 3 quindi si scambiano i due valori:
V: 3 12 7 15 2 :confronto 12 7
V: 3 7 12 15 2 :confronto 12 15
V: 3 7 12 15 2 :confronto 15 2
V: 3 7 12 2 15
A questo punto è terminata la prima passata sul vettore: il valore più grande è sicuramente nella posizione corretta. Questo implica che al massimo in N passate il vettore risulterà ordinato. Ecco come risulterà il vettore ad ogni passata:
L'algoritmo qui descritto è immediatamente migliorabile se si tiene presente che tutti gli elementi successivi all'indice i, dove è avvenuto l'ultimo scambio in una passata sul vettore, sono già ordinati.
Data la seguente struttura dati:
CONST
dim=100;
TYPE
vettore=ARRAY[1..dim] OF REAL;
si ha:
PROCEDURE bubblesort (VAR a:vettore;n:INTEGER);
VAR
i2,k,j:INTEGER;
PROCEDURE swap (VAR p:REAL; VAR q:REAL);
VAR
tmp:REAL;
BEGIN
tmp:=p; p:=q; q:=tmp;
END;
BEGIN
i2:=n-1;
REPEAT
k:=1;
FOR j:= 1 TO i2 DO
IF a[j] > a[j+1] THEN BEGIN
swap(a[j], a[j+1]);
k:=j
END;
i2:= k-1;
UNTIL i2 < 1;
END;
L'analisi della complessità porta alle seguenti conclusioni:
C_min = O(n) C_med = C_max = O(n^2)
In generale il bubblesort è un algoritmo molto lento dato il notevole numero di scambi che si devono effettuare: è soddisfacente solo nel caso in cui il vettore è già ordinato o parzialmente ordinato.
Si noti però che dato il seguente vettore:
V: 1 2 3 4 5 6 7 8 10 0
l'algoritmo precedente si trova nella situazione peggiore in quanto ad ogni passata solo un elemento va al posto corretto.
Per evitare questo inconveniente conviene alternare il verso delle passate: tale algoritmo prende il nome di shakesort.
PROCEDURE shakesort (VAR a:vettore;n:INTEGER);
VAR
i1,i2,k,j:INTEGER;
PROCEDURE swap (VAR p:REAL; VAR q:REAL);
VAR
tmp:REAL;
BEGIN
tmp:=p; p:=q; q:=tmp;
END;
BEGIN
i1:=2; i2:=n; k:=n;
REPEAT
FOR j:=i2 DOWNTO i1 DO
IF a[j-1] > a[j] THEN BEGIN
swap(a[j-1], a[j]);
k:=j
END;
i1:= k+1;
FOR j:=i1 TO i2 DO
IF a[j-1] > a[j] THEN BEGIN
swap(a[j-1], a[j]);
k:=j
END;
i2:= k-1;
UNTIL i1 > i2;
END;
L'algoritmo shakesort è semplicemente una versione più raffinata del bubblesort ma la complessità non viene modificata:
C_min = O(n) C_med = C_max = O(n^2)
9.4 Ordinamento per inserimento diretto
Nel metodo per inserimento diretto assumiamo che quando ci troviamo ad elaborare l'i-esimo elemento i primi i-1 elementi sono correttamente ordinati. Allora cerchiamo tra i primi i-1 elementi la posizione in cui inserire l'elemento di posizione i.
Dato il vettore:
V: 10 4 8 12 16 2 9 13
l'algoritmo modificherà ad ogni passata il vettore nel seguente modo:
1- 4 10 8 12 16 2 9 13 : inser. 4 in v1: 10
2- 4 8 10 12 16 2 9 13 : inser. 8 in v2: 4 10
3- 4 8 10 12 16 2 9 13 : inser. 12 in v3: 4 8 10
4- 4 8 10 12 16 2 9 13 : inser. 16 in v4: 4 8 10 12
5- 2 4 8 10 12 16 9 13 : inser. 2 in v5: 4 8 10 12 16
6- 2 4 8 9 10 12 16 13 : inser. 9 in v6: 2 4 8 10 12 16
7- 2 4 8 9 10 12 13 16 : inser. 13 in v7: 2 4 8 9 10 12 16
Data la seguente struttura dati:
CONST
dim=100;
TYPE
vettore=ARRAY[1..dim] OF REAL;
si ha:
PROCEDURE ins_sort (VAR a:vettore;n:INTEGER);
VAR
i,j:INTEGER;
x:REAL;
alt:BOOLEAN;
BEGIN
FOR i:=2 TO n DO BEGIN
x:=a[i];
j:=i-1;
alt:=FALSE;
{ ricerca la posizione dove inserire l'elemento x tra i primi i-1 elementi }
WHILE (a[j] > x) AND NOT alt DO BEGIN
a[j+1]:=a[j];
IF j > 1 THEN j:= j-1 ELSE alt:=TRUE
END;
{ inserisci l'elemento }
IF alt THEN a[1]:=x ELSE a[j+1]:=x
END;
END;
La complessità, vedendo l'algoritmo come N inserimeti in un vettore ordinato, risulta:
C_min = O(n) C_med = C_max = O(n^2)
9.5 Ordinamento per partizione (quicksort).
L'idea su cui si basa questo algoritmo di ordinamento (Hoare 1962) è molto semplice:
E` sufficiente ora ripetere ricorsivamente il ragionamento sulle due parti del vettore per ottenere il vettore ordinato.
Supposta la seguente struttura dati:
CONST
dim=100
TYPE
vettore=ARRAY[1..dim] OF REAL;
si ha:
PROCEDURE quick_ordina (VAR a:vettore;i1,i2:INTEGER);
VAR
x:REAL;
k:INTEGER;
PROCEDURE swap (VAR p:REAL; VAR q:REAL);
VAR
tmp:REAL;
BEGIN
tmp:=p; p:=q; q:=tmp;
END;
FUNCTION partition (i,j:INTEGER; VAR a:vettore; pivot:REAL):INTEGER;
BEGIN
WHILE (i<=j) do BEGIN
WHILE a[i] < pivot do i:= i+1;
WHILE a[j] > pivot do j:= j-1;
IF i <= j THEN BEGIN
swap(a[i],a[j]);
i:= i+1;
j:= j-1
END;
END;
partition:=i;
END;
BEGIN
x:=a[(i1+i2) div 2];
k:=partition(i1,i2,a,x);
IF i1<k-1 THEN quick_ordina(a,i1,k-1);
IF k<i2 THEN quick_ordina(a,k,i2);
END;
Per determinare la complessita temporale del Quicksort notiamo inanzitutto che la FUNCTION partition ha complessita O(n).
IL numero di chiamate della FUNCTION partition è, salvo casi particolari, proporzionale al log(n).
Abbiamo quindi:
C_min = C_med = O(n*log(n)) C_max = O(n^2)
La complessita massima concide con il caso in cui la funzione di partizione divide il vettore in modo che uno risulti sempre vuoto.
La complessita minina coincide con il caso in cui la funzione di partizione divide il vettore in due vettori con lo stesso numero di elementi.
N.B. Il Quicksort è un algoritmo di ordinamento molto efficiente e veloce: le sue prestazioni sono però molto modeste per valori piccoli di n.
9.6 Ordinamento per fusione (mergesort)
L'idea su cui si basa il mergesort è molto semplice. Supponiamo di avere il seguente vettore:
v1: 7 9 1 13 6 4 17 15
e due vettori di supporto v2 e v3.
Trasferiamo gli elementi di v1 in v2 continuando finchè l'elemento da trasferire è maggiore o uguale al precedente: se è minore cambiamo il vettore di destinazione.
v2: 7 9 6 15
v3: 1 13 4 17
A questo punto fondiamo i vettori v2 e v3 nel vettore v1 e ripetiamo il ragionamento finchè il vettore è ordinato:
v2: 1 7 9 4 15 17
v3: 6 13
v2: 1 6 7 9
v3: 4 13 15 17
E` importante notare che dopo il primo passo il vettore risulta formato, nel caso peggiore, da N/2 coppie ordinate: in generale al passo T il vettore risulta formato da blocchi di 2^T elementi ordinati. Questo implica che, dopo al massimo P passi (P=logaritmo in base 2 di N), l'algoritmo termina.
Supposta la seguente struttura dati
CONST
dim=100;
TYPE
vettore=ARRAY[1..dim] OF REAL;
si ha:
PROCEDURE mergesort( var v1:vettore; n1:INTEGER );
VAR
v2,v3:vettore;
n2,n3:INTEGER;
PROCEDURE dividi (VAR v1,v2,v3:vettore; n1:INTEGER; VAR n2,n3:INTEGER);
VAR
sw:BOOLEAN;
i:INTEGER;
BEGIN
sw:=TRUE; v2[1]:=v1[1]; n2:=1;
FOR i:=2 TO n1 DO
IF v[i] >= v[i-1] THEN
IF sw THEN BEGIN n2:=n2+1 ; v2[n2]:=v1[i] END
ELSE BEGIN n3:=n3+1 ; v3[n3]:=v1[i] END
ELSE BEGIN
sw:= not sw;
IF sw THEN BEGIN n2:=n2+1 ; v2[n2]:=v1[i] END
ELSE BEGIN n3:=n3+1 ; v3[n3]:=v1[i] END
END;
END;
PROCEDURE merge (VAR v1,v2,v3:vettore; n1,n2:INTEGER; VAR n3:INTEGER);
VAR
i,j,k:integer;
BEGIN
i:=1; j:=1; k:=1;
WHILE (i<=n1) AND (j<=n2) DO BEGIN
IF v1[i] <= v2[j] THEN BEGIN
v3[k]:=v1[i];
i:=i+1
END
ELSE BEGIN
v3[k]:=v2[j];
j:=j+1
END;
k:= k+1
END;
WHILE (i<=n1) DO BEGIN
v3[k]:=v1[i];
i:=i+1;
k:=k+1
END;
WHILE (j<=n2) DO BEGIN
v3[k]:=v2[j];
j:=j+1;
k:=k+1
END;
n3:=k-1;
END;
BEGIN
REPEAT
n2:=0; n3:=0;
dividi(v1,v2,v3,n1,n2,n3);
IF n3 <> 0 THEN
merge(v2,v3,v1,n2,n3,n1)
UNTIL n3 = 0;
END;
Per determinare la complessita temporale del Mergesort notiamo che le procedure dividi e merge hanno complessita O(n).
Il numero di chiamate delle procedure è, salvo casi particolari, proporzionale a log(n). Abbiamo quindi:
C_min = O(n) C_med = C_max = O(n*log(n))
La complessità minima coincide con il fatto che il vettore è già ordinato.
9.7 Confronto tra i metodi di ordinamento
La complessità temporale di un algoritmo permette solo una misura approssimata delle prestazioni: per scopi pratici è utile avere dati sperimentali sui tempi di esecuzione dei vari algoritmi.
Benchè queste misure siano influenzate da diversi fattori, esse comunque forniscono dei valori che ci permettono di trarre interessanti conclusioni.
Le seguenti stime sono fatte analizzando i tempi di ordinamento di vettori disordinati di 256 e 512 interi: i tempi sono stati rapportati al tempo del quicksort.
|
Algoritmo |
256elem. |
512elem. |
C_med |
|
Quicksort |
t1 |
t2 |
O(n*log(n)) |
|
Mergesort |
1.6*t1 |
1.6*t2 |
O(n*log(n)) |
|
Inserimento |
6.1*t1 |
9.9*t2 |
O(n^2) |
|
Selezione |
8.5*t1 |
13.4*t2 |
O(n^2) |
|
Shakesort |
16*t1 |
24*t2 |
O(n^2) |
|
Bubblesort |
18*t1 |
29*t2 |
O(n^2) |
Nonostante le stime siano molto approssimative emerge in modo evidente la diversità tra i metodi con complessità media O(n*log(n)) e quelli con complessità media O(n^2).
Tra quelli con complessità media O(n^2), il Bubblesort e il Shakesort sono decisamente i peggiori (a parte il caso in cui gli elementi del vettore sono già ordinati).
N.B. Il confronto è stato effettuato su vettori di interi: se associata alla chiave intera ci fossero altri campi si noterebbe un miglioramento sensibile degli algoritmi che effettuano pochi scambi.
Ad esempio, tra il metodo per inserimento diretto (numero medio di scambi = n(n-1)/2 e il metodo per selezione diretta (numero medio di scambi = n-1) noteremo che il secondo diventa più veloce del primo.
x:=a[(i1+i2) div 2];
con una funzione che determini x in modo più efficiente.