Algoritmi e Strutture Dati
Capitolo 4
Ordinamento: lower bound Ω(n log n) e
MergeSort ((*) l’intera lezione)
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Stato dell’arte
Caso Caso T(n)
Caso
migliore medio peggiore
S(n)
Selection Sort
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n)
Insertion Sort 1
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n)
Insertion Sort 2
Θ(n)
Θ(n2)
Θ(n2)
O(n2)
Θ(n)
Insertion Sort 3 Θ(n log n) Θ(n2)
Θ(n2)
O(n2)
Θ(n)
Bubble-Sort
Θ(n2)
Θ(n2)
Θ(n)
Θ(n2)
Θ(n2)
Nota: il Bubble-Sort può essere facilmente modificato in
modo tale che il caso migliore costi Θ(n). Come?
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Quindi, per il problema dell’ordinamento…
• Lower bound temporale: (n)
– “banale”: dimensione dell’input
• Upper bound temporale: O(n2)
– Insertion Sort 2 e 3
Abbiamo un gap lineare tra upper bound e lower bound!
È possibile chiudere tale gap?
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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.
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Albero di decisione
• Un albero di decisione è associato ad uno specifico
algoritmo A e ad una specifica dimensione n
dell’istanza
• 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)
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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 su una sequenza di 3
elementi!
Approfondimento: costruire l’albero di decisione per
il SS (e per il BS) su una sequenza di 3 elementi.
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Altezza in funzione delle foglie
Lemma: Un albero binario (ovvero, in cui ogni nodo interno
ha al più due figli) con k foglie ha altezza h(k)  log2 k.
Dim: Dimostrazione per induzione sul numero di foglie k:
– Caso base k=1: banale, perché ogni albero con una foglia deve
avere almeno altezza log21=0 (anche nel caso limite dell’albero
costituito da un unico nodo )
– Caso k>1: supposto vero per k-1 foglie, dimostriamolo per k;
poiché la radice ha almeno un figlio, uno dei suoi al più due
sottoalberi deve contenere almeno la metà (parte intera superiore)
delle foglie, e quindi
h(k) ≥1+h(k/2) ≥ (hp induttiva) 1+log2(k/2)
=1+log2k-log22=log2k.
QED
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Il lower bound (n logn)
• Consideriamo l’albero binario 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à:
h(n)  log2(#foglie)  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
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un algoritmo ottimo: il MergeSort
(John von Neumann, 1945)
• Problema dell’ordinamento:
– Lower bound - (n log n) albero di decisione
– Upper bound – O(n2)
IS 2 e 3
• Abbiamo ridotto il gap tra LB e UB da Θ(n) a Θ(n/log
n); proviamo a costruire un algoritmo ottimo (cioè a
ridurre il gap a Θ(1)) 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
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio di esecuzione
12
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
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Fusione di sequenze ordinate
• 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]
13
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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
Osservazione: usa
l’array ausiliario X
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]
14
fonde A[i1;f1] e A[f1+1;f2]
output in A[i1;f2]
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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)
15
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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)
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Tempo di esecuzione
• Il numero di confronti del MergeSort è descritto dalla seguente
relazione di ricorrenza:
C(n) ≤ 2 C(n/2) + Θ(n)
C(1)=0
(si noti che f(n)=Θ(n), in quanto il numero di confronti nelle fusioni è
ovviamente C(n)=O(n), ma anche C(n)=Ω(min{n1,n2})=Ω(min{n/2,
n/2})=Ω(n))
• Usando il caso 2 del Teorema Master (infatti a=b=2, e quindi
f(n)Θ(n)=Θ(nlog22)Θ(nlogba)), si ottiene
C(n) = O(nlog22 log n) = O(n log n)
(si noti che utilizzo la notazione O in quanto nella relazione di
ricorrenza compare il simbolo ≤)
• Infine, per il tempo di esecuzione totale (confronti + copie), si ha:
T(n) = 2 T(n/2) + Θ(n) T(1)=1  T(n) = Θ(n log n)
(si noti che in questo caso utilizzo la notazione Θ in quanto nella
relazione di ricorrenza compare il simbolo =)
17
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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; in tal caso, se migliorassimo la
procedura di Merge facendo un controllo
preliminare tra ultimo elemento della prima sequenza
e primo della seconda prima ancora di allocare
memoria aggiuntiva, otterremmo tempo e spazio
lineare, cioè Θ(n).
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Osservazioni finali
• Problema dell’ordinamento: abbiamo chiuso il gap!
– Lower bound - (n log n) albero di decisione
– Upper bound – Θ(n log n) Merge Sort
• Il MergeSort è dunque 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 Θ(n log n))
19
Copyright © 2004 - The McGraw - Hill Companies, srl