Algoritmi e Strutture Dati
Capitolo 4
Ordinamento
Camil Demetrescu, Irene Finocchi,
Giuseppe F. Italiano
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Lower bound
• Delimitazione inferiore alla quantità di una
certa risorsa di calcolo necessaria per risolvere
un problema
• W(n log n) è un lower bound al numero di
confronti richiesti per ordinare n oggetti
• Consideriamo un generico algoritmo A, che
ordina eseguendo solo confronti: dimostreremo
che A esegue W(n log n) confronti
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
…alcuni richiami…
Definizione (upper bound)
Un problema P ha una complessità O(f(n)) rispetto ad una
risorsa di calcolo se esiste un algoritmo che risolve P il cui
costo di esecuzione rispetto quella risorsa (nel caso peggiore)
è O(f(n))
Definizione (lower boud)
Un problema P ha una complessità W(f(n)) rispetto ad una
risorsa di calcolo se ogni algoritmo che risolve P ha costo
di esecuzione (nel caso peggiore) W(f(n)) rispetto quella
risorsa
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
…per il problema dell’ordinamento…
• Upper bound: O(n2)
– Insertio Sort, Selection Sort, Boubble Sort
• Lower bound: W(n)
– banale: dimensione dell’input
Abbiamo un gap lineare tra upper bound e lower bound!
Possiamo fare meglio?
4
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.
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Gli algoritmi di ordinamento per confronto possono essere descritti
in modo astratto in termini di alberi di decisione.
Un generico algoritmo di ordinamento per confronto 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.
Albero di decisione - Descrive i confronti che l’algoritmo esegue
quando opera su un input di una determinata dimensione. I
movimenti dei dati e tutti gli altri aspetti dell’algoritmo vengono
ignorati
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Alberi di decisione
• Descrive le diverse sequenze di confronti che
A potrebbe fare su istanze di lunghezza n
1:2
Š
2:3
Š
1,2,3
7
1:3

1:3

Š
Š

1,3,2
3,1,2
2,1,3

2:3
Š

2,3,1
3,2,1
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
…alcune definizioni…
Sotto-albero
sinistro
2:3
Š
1,2,3
radice
1:2
Š

1:3

1:3
Sotto-albero
destro
Š
Š

1,3,2
3,1,2
2,1,3

2:3
Š

2,3,1
3,2,1
Profondità di un nodo: lunghezza del cammino che lo congiunge alla
radice.
Altezza di un albero: valore massimo della profondità dei nodi.
8
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
• Un albero di decisione per l’ordinamento di n
elementi contiene almeno n! foglie
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Altezza in funzione delle foglie
• Un albero binario con k foglie tale che ogni
nodo interno ha esattamente due figli ha
altezza almeno log2 k
• Dimostrazione per induzione su k
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Il lower bound W(n logn)
• L’altezza h dell’albero di decisione è almeno log2 (n!)
• Formula di Stirling: n!  (2pn)1/2 ·(n/e)n
h  log2(n!) > log2 (n/e)n =
= n log2 (n/e) =
n! > (n/e)n
= n log2 n – n log2 e =
= W(n log n)
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esercizio
Fornire l’albero di decisione del seguente algoritmo per istanze di
dimensione 3.
InsertionSort2 (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
j=k
4.
while j > 0 e A[j] > x do
5.
A[j+1] = A[j]
6.
j= j-1
7.
A[j+1]=x
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Soluzione
a1:a2


a2:a3



<a1,a3,a2>


a1:a3
<a1,a2,a3>
13
a1:a3
<a2,a1,a3>

<a3,a1,a2>
a2:a3

<a2,a3,a1>

<a3,a2,a1>
Copyright © 2004 - The McGraw - Hill Companies, srl