Divide et Impera
Parte 11 - Risoluzione di problemi per
divisione in sottoproblemi “bilanciati”
Corso A: Prof. Stefano Berardi http://www.di.unito.it/~stefano
Corso B: Prof. Ugo de’ Liguoro http://www.di.unito.it/~deligu
Divide et Impera
Indice Parte 11
1. La ricorsione è efficiente? Due
algoritmi per il minimo e il massimo.
2. Divide et Impera: l’ordinamento per
fusione MergeSort.
3. Un altro esempio di Divide et impera:
il Quicksort
Divide et Impera
1. La ricorsione è efficiente?
• Nel caso della ricorsione lineare l’efficienza di
una funzione ricorsiva è paragonabile a quella di
un’iterazione
• Negli esempi visti di ricorsione ad albero
(fibonacci, coefficiente binomiale) la ricorsione
è molto meno efficiente dell’iterazione.
• Questo è vero in generale? Molto dipende da
come progettiamo gli algoritmi ricorsivi. Un
metodo di progettazione per ottenere algoritmi
ricorsivi ad albero efficienti, come vedremo, è
il metodo del “Divide et Impera”.
Divide et Im pera
Minimo e Massimo iterativo
Come esempio di ricorsione efficiente vediamo una versione
iterativa e una ricorsiva dell’algoritmo MinMax, che calcola
il minimo ed il massimo tra i valori di un vettore A[].
void MinMax (int A[], int n, int& min, int& max)
// pre: n > 0, ossia A[0..n-1] non e' vuoto
// post: min e max sono il minimo ed il massimo
// in A[0..n-1] rispettivamente
{
min = max = A[0];
for (int i = 1; i < n; i++)
if (A[i] < min) min = A[i];
else if (max < A[i]) max = A[i];}
Sia n=lun(A). L’algoritmo iterativo richiede (n-1)
confronti per il minimo, (n-1) per il massimo, dunque 2n 
2 confronti. Sembra difficile fare di meglio!
Divide et Impera
Minimo e Massimo ricorsivo
L’algoritmo DI_MinMax calcola il min e max in A[i..j] con
un metodo di dimezzamenti analogo alla Ricerca Binaria.
1. Se [i..j] ha al più due punti, calcola il minimo e il
massimo direttamente.
2. Altrimenti, divide l’intervallo A[i..j] in due parti il più
possibile uguali, A[i..m] e A[m+1..j], dove m è il punto
medio di [i..j]
3. Calcola il massimo e il minimo (max1 e min1) di A[i..m],
e il massimo e il minimo (max2 e min2) di A[m+1..j].
4. Il massimo di A[i..j] è il massimo di max1, max2,
mentre il minimo di A[i..j] è il minimo di min1, min2.
Divide et Impera
Minimo e Massimo ricorsivo
void DI_MinMax(int A[], int i, int j, int& min, int& max)
// pre: i <= j, ossia A[i..j] non e' vuoto
// post: min e max sono il min/max in A[i..j] risp.
{
if (i == j) min = max = A[i];
else if (i == j-1)
if (A[i] < A[j]) { min = A[i]; max = A[j];}
else { min = A[j]; max = A[i];}
else // i..j ha piu' di 2 elementi
{
int min1, max1, min2, max2;
int m = (i + j)/2; // punto medio in i..j
DI_MinMax(A, i,
m, min1, max1);
DI_MinMax(A, m+1, j, min2, max2);
min = Min(min1, min2);
max = Max(max1, max2);
}
}
Quanti sono i confronti richiesti nel caso ricorsivo?
Divide et Impera
Minimo e Massimo:
la ricorsione è più efficiente
Se n = lun(A[i..j]) = j – i + 1 allora i confronti C (n) richiesti
dall’algoritmo ricorsivo sono:
0
se n = 1
C (n) =
1
se n = 2
2C (n/2) + 2
se n > 2
Infatti: quando dividiamo il vettore in due vettori di
lunghezza n/2, ognuno di essi ci richiede C(n/2) confronti,
poi con un altro confronto calcoliamo il massimo tra i due
massimi, con un altro ancora il minimo tra i due minimi. A
questo punto, ragionando per induzione su n, è possibile
dimostrare che i confronti sono C(n) = (3/2)n – 2.
L’algoritmo iterativo è più semplice, ma richiede un
numero maggiore di confronti: 2n-2.
Divide et Impera
2. Divide et Impera
“Per meglio dominare occorre dividere gli avversari”
Ossia: suddividi il problema in sottoproblemi di
dimensione circa eguale (“bilanciati”); risolvi i
sottoproblemi con la ricorsione, infine combina i risultati
MinMax e la Ricerca binaria sono esempi di algoritmi
progettati con “Divide et Impera”.
• Il vantaggio del Divide et Impera è che la dimensione
massima del sottoproblema che dobbiamo risolvere
decresce esponenzialmente, e quindi scende rapidamente a
zero.
• Per esempio, quando dividiamo in due sottoproblemi di
dimensione uguale, la dimensione massima si dimezza ogni
volta.
2. Divide et Impera
“Per meglio dominare occorre dividere gli avversari”
Ossia: suddividi il problema in sottoproblemi di
dimensione circa eguale (“bilanciati”); risolvi i
sottoproblemi con la ricorsione, infine combina i risultati
Ecco come appare un programma “Divide et Impera”
DivideEtImpera (P, n) // Pre: n è la dimensione del problema P
if n  k then risolvi direttamente P
else
dividi P nei sottoproblemi P1,…, Ph
di dimensioni n1,…, nh all’incirca uguali
for i = 1 to h do
Risi = DivideEtImpera (Pi, ni)
return combinazione di Ris1, …, Rish uguale al risultato
Divide et Impera
“Per meglio dominare occorre dividere gli avversari”
Ossia: suddividi il problema in sottoproblemi di dimensione
circa eguale (“bilanciati”); risolvi i sottoproblemi con la
ricorsione, infine combina i risultati
In genere, una stima del tempo necessario si calcola cosí:
c
se n  k


h
T (n)   D(n)  C (n)  T (n ) se n  k

i

i 1
Tempo per
dividere
Tempo per
combinare
Somma dei
tempi dei
sottoproblemi
Divide et Impera
Esempio di “Divide et impera”:
Ordinamento per fusione
88 52 14
31 25 98
30
23
62
79
Affida una metà da
ordinare
ad un amico …
25,31,52,88,98
dividi l’insieme da
ordinare il più
possibile a metà,
in modo qualsiasi
… e l’altra metà da
ordinare ad un
altro
14,23,30,62,79
Divide et Impera
Ordinamento per fusione
25,31,52,88,98
14,23,30,62,79
25,31,52,88,98
“Fondi” tra loro i due
vettori ordinati ottenuti
14,23,25,30,31,52,62,79,88,98
14,23,30,62,79
Fa solo attenzione che la
“fusione” sia ordinata!
Divide et Impera
Ordinamento per fusione o
“MergeSort”
void MergeSort(int A[], int i, int j)
{
if (i < j)
{
int m = (i+j)/2;
MergeSort(A, i, m);
MergeSort(A, m+1, j);
/* per completare l’opera, devo solo
“fondere” i segmenti ordinati A[i,m] e
A[m+1,j] */
Merge(A, i, m, j);
}}
Divide et Impera
Fusione ordinata (merge) di due
segmenti ordinati adiacenti
Definiamo un metodo per “fondere” due segmenti ordinati
consecutivi A[i..m] e A[m+1..j] in un segmento ordinato
A[i...j] che comprende tutti i loro punti.
1. Creiamo un vettore di appoggio B in cui costruire l’unione
ordinata di A[i..m] e A[m+1..j].
2. Prendiamo il primo elemento di A[i..m] e il primo
elemento di A[m+1..j] e li confrontiamo. Il più piccolo dei
due diventa il minimo di B.
3. Continuiamo così a togliere il più piccolo elemento
rimasto da A[i…m] o da A[m+1..j] e a inserirlo in B, finché
A[i..m] oppure A[m+1..j] diventano vuoti.
4. A questo punto gli elementi rimasti in A[i..m] oppure
A[m+1..j] sono i più grandi, e li ricopiamo in B.
5. Finito di costruire B, lo ricopiamo all’indietro su A.
Divide et Impera
I primi due passi del Merge
25,31,52,88,98
14
14,23,30,62,79
25,31,52,88,98
14,
14 23
23,30,62,79
Divide et Impera
Fusione ordinata (merge) di due
segmenti ordinati adiacenti
void Merge(int A[], int i, int m, int j)
// pre: i <= m <= j
A[i..m] e A[m+1..j] ordinati
// post: A{i..j] e' ordinato
Invariante while:
A[p..m], A[q..j] ordinati,
{int* B = new int[j-i+1];
B[0..k – 1] ordinato ed i
int p = i, q = m+1, k = 0;
suoi elem. sono quelli di
while (p <= m && q <= j)
A[i..p – 1] e A[m+1..q – 1]
if (A[p]< A[q]) {B[k]=A[p];k++;p++}
else {B[k]=A[q];k++;q++}
/* se A[i..m] o A[m+1..j] sono vuoti copio tutti
gli elementi rimasti in A[i..m] A[m+1..j] su B. */
Copy(A, p, m, B, k); Copy(A, q, j, B, k+(m-p+1));
/* Riporto il risultato da B in A */
Copy(B, 0, k-1, A, i); delete B;}
Divide et Impera
La funzione di “copia” tra
vettori
Nel lucido precedente abbiamo utilizzato
funzione di “copia” definita come segue:
una
void Copy(int A[], int i, int j, int B[],
int k)
// post: copia A[i..j] su B[] a partire da k
{
for (int h = i; h <= j; h++, k++)
B[k] = A[h];
}
Divide et Impera
Merge Sort: prima parte
esecuzione (divisione)
7
7
7
7
4
4
1
1
2
3
8
4
1
4
8
1
8
2
8
2
6
5
2
3
3
6
5
6
3
6
5
5
Scomponiamo il vettore in segmenti di un punto soltanto
(necessariamente ordinati!)
Divide et Impera
Merge Sort: seconda parte
esecuzione (merge)
1
1
4
7
4
2
7
3
5
6
8
7
1
4
4
1
8
2
8
2
7
8
2
3
3
5
6
5
3
6
6
5
Fondiamo tra loro i segmenti ordinati in segmenti più
grandi, preservando l’ordine, fino a ricostruire il vettore
Divide et Impera
Come si stima il tempo di calcolo di una
funzione ricorsiva?
Ricordiamo quanto abbiamo visto studiando i tempi di calcolo:
a ogni algoritmo associamo un ordine di infinito per il tempo
di calcolo nel caso peggiore. Per le funzioni ricorsive il tempo
di calcolo è a sua volta definito ricorsivamente
1

TFact (n)  
TFact (n  1)  1
Per esempio, questa è la
definizione ricorsiva del
tempo di calcolo per la
funzione ricorsiva
“fattoriale”
se n  2
altrimenti
Divide et Impera
Il tempo di Merge Sort
Questa è la definizione ricorsiva del tempo di calcolo per
il MergeSort. Richiede di conoscere il tempo richiesto dal
Merge:
TMergeSort (n)  2T ( n / 2)  TMerge (n)
E’ facile vedere che TMerge (n)  O (n) dunque:
c
se n  1

T ( n)  
2T ( n / 2)  n se n  1
Occorrono log2(n) dimezzamenti successivi per trasformare
n in 1. Dunque la formula per calcolare T(n) ci chiede di
sommare n per log2(n) volte (vedi prossimo lucido)
Divide et Impera
Il tempo di Merge Sort
T (n)  2T (n / 2)  n
T (n )
Divide et Impera
Il tempo di Merge Sort
T (n)  2T (n / 2)  n
n
T (n / 2)
T (n / 2)
Divide et Impera
Il tempo di Merge Sort
T (n)  2T (n / 2)  n
n
n
2
T (n / 4) T (n / 4)
n
2
T (n / 4) T (n / 4)
Divide et Impera
Il tempo del Merge Sort
è O(n log(n))
T (n)  2T (n / 2)  n
È possibile ordinare
in tempo meno di
O(n log n) ?
n
4
Albero delle chiamate ricorsive, ciascuna
con il suo costo
n
n
2
+
n
n
2
+
n
4
+
n
4
+
n
n
4
n
Ogni
“livello”
dell’albero
ha costo
totale n, e i
livelli sono
log 2 (n)
Dunque la somma di tutti i costi è: O(n log n)
Il MergeSort è ulteriormente migliorabile? Bisogna prima
stabilire quale è il tempo minimo richiesto dall’ordinamento
Divide et Impera
Alberi di decisione e limitazioni
inferiori al tempo di calcolo
Un albero rappresenta le decisioni prese da un
algoritmo quando valgono le condizioni seguenti:
 i ”nodi interni” dell’albero rappresentano le
decisioni prese dall’algoritmo
 le ”foglie” dell’albero rappresentano i possibili
risultati dell’algoritmo
 i ”rami” dell’albero rappresentano particolari
esecuzioni dell’algortimo.
La minima lunghezza del ramo più lungo di un
albero di decisione di un algoritmo fornisce una
limitazione inferiore al numero di decisioni
necessarie all’algoritmo nel caso peggiore.
Divide et Impera
Alberi quasi
perfettamente bilanciati
Def. Un albero binario è completo se ha 2k vertici per ogni
livello k non vuoto. Un albero binario è quasi perfettamente
bilanciato (qpb) se, avendo altezza h, è completo sino al
livello h 1 (come nella figura qui sopra).
Le foglie di un albero quasi perfettamente bilanciato di
altezza h sono in numero di:
2h1  s  2h , ovvero h  log2 (s)
Quindi un problema la cui soluzione può rappresentarsi con
un albero q.p.b. con s(n) possibili soluzioni richiede tempo
almeno O(log2 s(n)) (la lunghezza del suo ramo più lungo).
Un esempio di albero q.p.b. di decisione
per l’ordinamento di 3 elementi
a:b
a<b
b<c
b:c
b<a
c<b
b<c
a:c
a:c
a, b, c
a<c
a, c, b
c<a
c, a, b
a<c
b, a, c
b:c
c<b
b, c, a
c<a
b, c, a
Ogni nodo corrisponde al confronto tra due elementi del
vettore {a,b,c} da ordinare, ogni foglia è uno dei 3! = 6
possibili ordinamenti finali, la massima lunghezza di un
“ramo” è 3, mentre la minima è 2 (dato che l’albero è q.p.b.).
Divide et Impera
Il tempo di calcolo minimo
richiesto dall’ordinamento
Nel caso dell’ordinamento le foglie dell’albero di decisione
sono s(n) = n! (il risultato di un algoritmo di ordinamento è
una permutazione, dunque i risultati possibili sono n!). I nodi
interni rappresentano i confronti tra due elementi.
Nel caso dell’ordinamento il numero dei confronti nel caso
peggiore deve essere dunque almeno log2(n!). Usando la
formula di Stirling per n! concludiamo che:
log 2 (n!)  log 2


2n (n / e) n  log 2 2n  n log 2 (n / e)
Ossia il tempo per ordinare è almeno O(nlog(n)).
Algoritmi O(nlog(n)), come il MergeSort, impiegano dunque
tempo minimo (a meno di costanti moltiplicative, che la
Teoria del Tempo di Calcolo non considera).
Divide et Impera
3. Divide et impera:
il Quick Sort
Dividi l’insieme in due scegliendo un elemento
(detto “perno”) a caso, e disponendo gli
elementi ≤ del perno da una parte e quelli ≥
dall’altra
88 52
14
31
25 98
30
23
62
79
14
31 30 23
25
88
≤ 52 ≤
62
98
79
Divide et Impera
Quick Sort
14
31 30 23
25
Fà ordinare una metà
ad un amico …
14,23,25,30,31
88
≤ 52 ≤
62
98
79
…e la seconda metà
ad un altro amico
62,79,98,88
Divide et Impera
Quick Sort
14,23,25,30,31
52
62,79,98,88
Metti insieme i due risultati con il perno in
mezzo: formano un insieme ordinato senza
bisogno di fare altro
14,23,25,30,31,52,62,79,88,98
Divide et Impera
Quick Sort (supponendo già
definita la funzione Perno)
void QuickSort(int A[], int i, int j)
//pre: A[] e' un vettore, i <= j < dim. di A[]
// post: ordina A in senso non decrescente
{
if (i < j)
{
int k = Perno(A, i, j);
QuickSort(A, i, k);
QuickSort(A, k+1, j);
}
}
Divide et Impera
Divisione di A[p,u] in due
parti con il perno in mezzo
int Perno (int A[], int p, int u)
// pre: p <= u < dimensione di A[], x = A[p] “perno”
// post: se y in A[p..j-1] allora y <= x, A[j-1] == x
// se y in A[j..u] allora y >= x
{ int x = A[p], i = p+1, j = p+1;
while (i <= u)
// INVARIANTE. Se y in v[p+1..j-1] allora y < x
// se z in v[j..i-1] allora z >= x
if (A[i] < x) {swap(A[i], A[j]);i++;j++;}
else i++;
swap(A[p], A[j-1]); // inserisco il perno in mezzo
return j-1;} // restituisco la posizione del perno
Divide et Impera
Quick Sort: il caso pessimo
14,23,25,30,31,52,62,79,88,98
(vuoto)
≤ 14 ≤ 23,25,30,31,52,62,79,88,98
Se Perno sceglie sempre il primo elemento, allora il
caso peggiore si verifica se la lista è già ordinata,
perché la dimensione del secondo sottoproblema
descresce molto lentamente, di un solo elemento
alla volta.
Divide et Impera
Il tempo peggiore per il
Quick Sort è O(n2)
Sia n la lunghezza del vettore da ordinare e p la posizione del
primo perno da inserire
T ( n)  P ( n)  T ( p )  T ( n  p )
Tempo
della
funzione
Perno
poniamo
Tempo = num.
dei confronti
Caso peggiore: avviene quando p = 1. In
tal caso, infatti, abbiamo P(n) = n – 1 e
T(1) = 0, quindi deduciamo che:
T (n)  (n  1)  T (n  1)  (( n  1)  (n  2)  ..  1)  n(n  1) / 2 
 O( n 2 )
Divide et Impera
Il tempo medio per il Quick
Sort è O(nlog(n))
Il tempo impiegato nel caso medio è la media dei tempi
impiegati nelle n possibili posizioni del perno: p=0,…,n-1.
1 n 1
Tmedio (n)  P ( n)   (Tmedio ( p )  Tmedio ( n  p ))
n p 1
p è la
2 n 1
posizione
 n  1   Tmedio ( p )
(per n  1)
del perno
n p 1
Partendo dalla formula per il tempo nel caso medio si
n 1
1
dimostra che:
Tmedio ( n)  2(n  1)  O( n log 2 n)
k 3 k
Almeno, il QuickSort è ottimo nel
caso medio: richiede tempo medio
O(nlog(n))
Divide et Impera
Fine
Fine del Corso
di Informatica
2009/2010
Divide et Impera