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)
2
Θ(n2)
Θ(n2)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Upper e lower bound di un
algoritmo e di un problema
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Delimitazioni superiori (upper bound)
Definizione (complessità di un algoritmo)
Un algoritmo A ha costo di esecuzione O(g(n)) su istanze di
dimensione n e rispetto ad una certa risorsa di calcolo (spazio
o tempo), se la quantità f(n) di risorsa sufficiente per eseguire
A su qualunque istanza di dimensione n (e quindi in particolare
anche nel caso peggiore) verifica la relazione
f(n)=O(g(n)).
Definizione (upper bound di un problema)
Un problema P ha una delimitazione superiore alla
complessità O(g(n)) rispetto ad una certa risorsa di calcolo
(spazio o tempo) se esiste un algoritmo che risolve P il cui
costo di esecuzione rispetto a quella risorsa è O(g(n)).
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Delimitazioni inferiori (lower bound)
Definizione
Un algoritmo A ha costo di esecuzione (g(n)) su istanze di
dimensione n e rispetto ad una certa risorsa di calcolo (spazio o tempo),
se la quantità f(n) di risorsa necessaria per eseguire A nel caso peggiore
(e quindi non è detto che debba essere necessaria per ogni istanza di
dimensione n: istanze facili potrebbero richiedere meno risorse!)
verifica la relazione
fworst(n)= (g(n)).
Definizione (lower bound o complessità intrinseca di un problema)
Un problema P ha una delimitazione inferiore alla complessità
(g(n)) rispetto ad una certa risorsa di calcolo (spazio o tempo) se
ogni algoritmo che risolve P ha costo di esecuzione (g(n)) rispetto a
quella risorsa.
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ottimalità di un algoritmo
Definizione
Dato un problema P con complessità intrinseca (g(n))
rispetto ad una certa risorsa di calcolo (spazio o tempo), un
algoritmo che risolve P è ottimo (in termini di complessità
asintotica, ovvero a meno di costanti moltiplicative e di
termini additivi/sottrattivi di “magnitudine” inferiore) se ha
costo di esecuzione O(g(n)) rispetto a quella risorsa.
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Convenzioni
• Se scriverò che un algoritmo ha complessità T(n) =
O(g(n)), intenderò che su ALCUNE istanze costerà
Θ(g(n)), ma sulle rimanenti costerà o(g(n).
• Se scriverò che un algoritmo ha complessità
T(n)=Θ(g(n)), intenderò che su TUTTE le istanze
costerà Θ(g(n))
• Da ora in poi, quando parlerò di UB di un problema,
mi riferirò alla complessità del MIGLIORE
ALGORITMO che sono stato in grado di progettare
sino a quel momento (ovvero, quello con minore
complessità nel caso peggiore).
• Da ora in poi, quando parlerò di LB di un problema, mi
riferirò alla PIÙ GRANDE delimitazione inferiore che
sono stato in grado di dimostrare sino a quel momento.
7
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?
8
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.
9
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
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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
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!
Esercizio per casa: costruire l’albero di decisione
per il SS e per il BS su una sequenza di 3 elementi.
12
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)
13
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 su 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
14
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
15
= 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
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
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
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]
18
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]
19
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)
20
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)
21
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 =)
22
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
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 2n)
24
Copyright © 2004 - The McGraw - Hill Companies, srl