Didattica e Fondamenti degli
Algoritmi e della Calcolabilità
Settima giornata
Risolvere ottimamente un problema in P:
Il problema dell’ordinamento: Merge Sort
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
Riepilogo per il problema dell’ordinamento
• Upper bound temporale: O(n2)
– Insertion Sort, Selection Sort
• Lower bound temporale: (n)
– “banale”: dimensione dell’input
Abbiamo un gap lineare tra upper bound e lower bound!
Possiamo fare meglio, ovvero abbassare
l’upper bound e/o innalzare il lower bound ?
2
Ordinamento per confronti
Dati due elementi ai ed aj, per determinarne l’ordinamento relativo
effettuiamo una delle seguenti operazioni di confronto:
a i  aj ; ai  aj ; a i  aj ; ai  aj ; ai  aj
Non si possono esaminare i valori degli elementi o ottenere
informazioni sul loro ordine in altro modo.
Notare: Tutti gli algoritmi di ordinamento considerati fino ad
ora sono algoritmi di ordinamento per confronto.
3
Lower bound (n log n) per l’ordinamento
• Consideriamo un generico algoritmo A, che ordina
eseguendo solo confronti: dimostreremo che A esegue (nel
caso peggiore) (n log n) confronti
• Un generico algoritmo di ordinamento per confronti lavora
nel modo seguente:
- Confronta due elementi ai ed aj (ad esempio effettua il test ai  aj);
- A seconda del risultato, riordina e/o decide il confronto
successivo da eseguire.
 Un algoritmo di ordinamento per confronti può essere
descritto in modo astratto usando un albero di decisione,
nel quale i nodi interni rappresentano i confronti, mentre le
foglie rappresentano gli output prodotti
4
Albero di decisione
• Descrive le diverse sequenze di confronti che A esegue
su un’istanza <a1,a2,…,an> di lunghezza n; i movimenti
dei dati e tutti gli altri aspetti dell’algoritmo vengono
ignorati
• Nodo interno (non foglia): i:j (modella il confronto
tra ai e aj)
• Nodo foglia: i1,i2,…,in (modella una risposta (output)
dell’algoritmo, ovvero una permutazione <ai1,ai2,…,ain>
degli elementi)
• L’albero di decisione è associato ad un algoritmo e alla
dimensione n dell’istanza
5
Esempio
Input <a1,a2,a3>
Š
1,2,3
1:2
Š
2:3
Š
1,3,2
Š

1:3


3,1,2
2,1,3
1:3
Riconoscete
l’algoritmo
associato?

2:3
Š

2,3,1
3,2,1
È proprio l’Insertion Sort 2!
Esercizio per casa: costruire l’albero di decisione
per il SS su una sequenza di 3 elementi.
6
Albero di decisione del SS
Input <a1,a2,a3>
3:2
<
<
1:2
impossibile

3,2,1
•
<
2:1

3:1

<
3:1
2,3,1
,
<

<
2,1,3
3,1,2
1:2


3:2

<
3,2,1 1,3, 2
1,2,3
Osservazione 1: l’albero non è strettamente binario: compare un
confronto inutile!
Osservazione 2: tutte le foglie sono alla stessa altezza (e infatti il SS
esegue sempre lo stesso numero di confronti!)
•
•
Osservazione 3: la permutazione <3,2,1> è raggiungibile solo nel caso in cui a1=a2
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Proprietà
• Per una particolare istanza, i confronti eseguiti da
A su quella istanza rappresentano un cammino
radice – foglia
• L’algoritmo segue un cammino diverso a seconda
delle caratteristiche dell’input
– Caso peggiore: cammino più lungo
– Caso migliore: cammino più breve
• Il numero di confronti nel caso peggiore è pari
all’altezza dell’albero di decisione (ovvero alla
lunghezza, in termini di numero di archi, del più
lungo cammino radice-foglia)
8
Altezza in funzione delle foglie
Lemma: Un albero strettamente binario (ovvero, in cui ogni
nodo interno ha esattamente due figli) con k foglie ha altezza
h(k)  log2 k.
Dim: Dimostrazione per induzione su k:
– Caso base k=1 (albero-nodo ): banale h(k)=0≥ log21=0
– Caso k>1: supposto vero per k-1 foglie, dimostriamolo per k;
poiché la radice ha 2 figli, uno dei due suoi sottoalberi deve
contenere almeno la metà (parte intera sup.) delle foglie, e quindi
h(k) ≥1+h(k/2) ≥ (hp induttiva) 1+log2(k/2)
=1+log2k-log22=log2k.
QED
9
Il lower bound (n logn)
• Consideriamo l’albero di decisione di un qualsiasi algoritmo
che risolve il problema dell’ordinamento di n elementi
• Tale albero deve avere almeno n! foglie: infatti, se l’algoritmo
è corretto, deve contemplare tutti i possibili output, ovvero le
n! permutazioni della sequenza di n elementi in input
• Dal lemma precedente, avremo che l’altezza h(n!) dell’albero
di decisione sarà quindi:
h(n!)  log2(n!) > log2 (n/e)n =
Formula di Stirling:
n!  (2pn)1/2 ·(n/e)n
> (n/e)n
10
= n log2 (n/e) =
= n log2 n – n log2 e =
= (n log n)
QED
Correzione esercizio:
Il problema della ricerca
Un primo algoritmo è quello di ricerca sequenziale (o
esaustiva), che gestisce l’insieme di numeri come una
lista L non ordinata
Contiamo il numero di confronti (operazione dominante):
Tbest(n) = 1
x è in prima posizione
Tworst(n) = n
xL oppure è in ultima posizione
11
Algoritmo di ricerca binaria
Se ipotizzassimo che la sequenza di numeri fosse un array L
ordinato, potremmo progettare un algoritmo più efficiente:
Confronta x con l’elemento centrale di L e prosegue nella
metà sinistra o destra in base all’esito del confronto
12
Esempi su un array di 9 elementi
Cerca 2
Cerca 1
Cerca 9
Cerca 3
3<4 quindi a e b
si invertono
13
Analisi dell’algoritmo di ricerca binaria
Contiamo i confronti eseguiti nell’istruzione 3 (operazione dominante):
Tbest(n) = 1
l’elemento centrale è uguale a x
Tworst(n) = Θ(log n) xL
Infatti, poiché la dimensione del sotto-array su cui si procede
si dimezza dopo ogni confronto, dopo l’i-esimo confronto il
sottoarray di interesse ha dimensione n/2i. Quindi, dopo
i=log n +1 confronti, si arriva ad avere a>b.
14
Lower bound (log n) per la ricerca
•
•
•
•


Ricordiamo che per il problema della ricerca di un elemento in un insieme
non ordinato si applica il lower bound banale di (n). Tuttavia, ad
esempio, nel caso di insiemi ordinati la ricerca binaria costa O(log n).
Possiamo migliorarla?
Consideriamo l’albero di decisione di un qualsiasi algoritmo che risolve il
problema della ricerca in un insieme di n elementi tramite confronti
L’albero deve contenere almeno n+1 foglie (ogni foglia specifica una tra le n
posizioni dove si può trovare l’elemento, più la foglia “non trovato”)
Un albero binario con k foglie in cui ogni nodo interno ha al più due figli, ha
altezza
h(k)  log k (vedi lezione n. 6)
L’altezza h dell’albero di decisione è (log n)
La ricerca binaria quindi è ottimale e non può essere ulteriormente
migliorata
15
Copyright © 2004 - The McGraw - Hill Companies, srl
Un algoritmo di ordinamento ottimo: il
MergeSort (John von Neumann, 1945)
• Problema dell’ordinamento:
– Lower bound - (n log n) albero di decisione
– Upper bound – O(n2)
IS,SS
• Proviamo a costruire un algoritmo ottimo, usando
la tecnica del divide et impera:
1 Divide: dividi l’array a metà
2 Risolvi il sottoproblema ricorsivamente
3 Impera: fondi le due sottosequenze ordinate
16
Esempio di esecuzione
17
7 2 4 5 3 1 5 6
input
1 2 3 4 5 5 6 7
output
7 2 4 5
3 1 5 6
2 4 5 7
1 3 5 6
7 2
4 5
3 1
5 6
2 7
4 5
1 3
5 6
Input ed
output delle
chiamate
ricorsive
7
2
4
5
3
1
5
6
7
2
4
5
3
1
5
6
Fusione di sequenze ordinate (passo di impera)
• Due array ordinati A e B possono essere fusi
rapidamente:
– estrai ripetutamente il minimo di A e B e copialo
nell’array di output, finché A oppure B non
diventa vuoto
– copia gli elementi dell’array non ancora
completamente svuotato alla fine dell’array di
output
Notazione: dato un array A e due indici x  y, denotiamo con
A[x;y] la porzione di A costituita da A[x], A[x+1],…,A[y]
18
Algoritmo di fusione di sequenze ordinate
Merge (A, i1, f1, f2)
1.
Sia X un array ausiliario di lunghezza f2-i1+1
2.
i=1
3.
i2=f1+1
4.
while (i1 f1 e i2  f2) do
5.
if (A[i1]  A[i2])
6.
then X[i]=A[i1]
7.
8.
9.
incrementa i e i1
else X[i]=A[i2]
incrementa i e i2
10.
if (i1<f1) then copia A[i1;f1] alla fine di X
11.
else copia A[i2;f2] alla fine di X
12.
copia X in A[i1;f2]
19
fonde A[i1;f1] e A[f1+1;f2]
output in A[i1;f2]
Osservazione: usa
l’array ausiliario X
Costo dell’algoritmo di merge
Lemma
La procedure Merge fonde due sequenze ordinate di
lunghezza n1 e n2 eseguendo al più n1+ n2 -1 confronti
Dim: Ogni confronto “consuma” un elemento di A.
Nel caso peggiore tutti gli elementi tranne l’ultimo sono
aggiunti alla sequenza X tramite un confronto.
Il numero totale di elementi è n1+ n2. Quindi il numero totale
di confronti è n1+ n2 -1.
QED
Numero di confronti: C(n=n1+ n2)=O(n1+ n2)=O(n)
(si noti che vale anche C(n)=Ω(min{n1,n2}))
Numero di operazioni (confronti + copie)? T(n)=(n1+ n2)
20
MergeSort
MergeSort (A, i, f)
1.
if (i  f) then return
2.
m = (i+f)/2
3.
MergeSort(A,i,m)
4.
MergeSort(A,m+1,f)
5.
Merge(A,i,m,f)
Ovviamente la chiamata principale è Mergesort(A,1,n)
21
Complessità del MergeSort
Si vede facilmente che il tempo di esecuzione
di MergeSort è:
T(n) = 2 T(n/2) + Θ(n) con T(1)=1, da cui:
T(n)=2(2T(n/22)+Θ(n/2))+Θ(n)=
=2(2(2T(n/23)+Θ(n/22))+Θ(n/2))+Θ(n)=…
e per k = log2n si ha n/2k = 1 e quindi
T(n)=2(2(…(2T(n/2k)+Θ(1))+…+Θ(n/22))+Θ(n/2))+Θ(n)
= 2log n·Θ(1)+2log n-1·Θ(2)+2log n-2·Θ(22)+…+ 20·Θ(n)
= n∙Θ(1)+n/2∙Θ(2)+n/4∙Θ(4)+…+1∙Θ(n) = Θ(n log n)
22
Più precisamente…
1. Nel caso peggiore, il MS esegue (n ⌈log n⌉ - 2⌈log n⌉ +
1) confronti, che corrisponde ad un numero compreso
tra (n log n - n + 1) e (n log n + n + O(log n))
2. Nel caso medio, il MS esegue (n ⌈log n⌉ - 2⌈log n⌉ + 1)
– 0.2645·n confronti
3. Nel caso migliore (array già ordinato), il MS esegue
n-1 confronti; può essere ottenuto facendo un
controllo preliminare nella procedura di Merge tra
ultimo elemento della prima sequenza e primo della
seconda
23
Osservazioni finali
• Il MergeSort è un algoritmo (asintoticamente)
ottimo rispetto al numero di confronti eseguiti
nel caso peggiore
• Il MergeSort non ordina in loco, e utilizza
memoria ausiliaria (l’occupazione di memoria
finale è pari a 2n)
24