Algoritmi e Strutture Dati
Capitolo 4
Ordinamento
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 (nel caso peggiore) 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)
– Insertion Sort, Selection Sort, Quick Sort
• Un upper bound migliore: O(n log n)
– Merge Sort
• Lower bound: W(n)
– banale: dimensione dell’input
Abbiamo un gap di log n 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
• Nodo interno (non foglia): i:j
– modella il confronto tra ai e aj
• Nodo foglia:
– modella una risposta (output) dell’algoritmo: permutazione degli elementi
Input: a1,a2,a3
Š
1,2,3
Š
2:3
Š
1,3,2
7
1:2
Š

1:3


3,1,2
2,1,3
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
Osservazioni
• L’albero di decisione non è associato ad un
problema
• L’albero di decisione non è associato solo ad un
algoritmo
• L’albero di decisione è associato ad un algoritmo e
a una dimensione dell’istanza
• L’albero di decisione descrive le diverse sequenze
di confronti che un certo algoritmo può eseguire
su istanze di una certa dimensione
8
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
NonsenseSort (A)
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio
if n  3 then
1.
2.
if A[1]>A[n] then
3.
scambia A[1] con A[n]
4.
scambia A[2] con A[n]
5.
Albero di decisione
di NonsenseSort con n > 2
else
1: n
6.
scambia A[1] con A[2]
7.
if A[1] > A[n] then
8.

scambia A[1] con A[2]
n,1,3,…,n-1,2
2: n
>

2,1,3,…,n
9
>
1,2,3,…,n
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
…alcune definizioni…
Sotto-albero
sinistro
Š
1,2,3
2:3
Š
1,3,2
radice
1:2
Š
1:3


Š


3,1,2
Sotto-albero
destro
2,1,3
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.
10
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 di un algoritmo che risolve
il problema dell’ordinamento di n elementi
contiene almeno n! foglie
11
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
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Il lower bound W(n logn)
• Consideriamo l’albero di decisione di un qualsiasi
algoritmo che risolve il problema dell’ordinamento di
n elementi
• 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)
13
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
14
Copyright © 2004 - The McGraw - Hill Companies, srl