Didattica e Fondamenti degli
Algoritmi e della Calcolabilità
Sesta giornata
Risolvere efficientemente un problema in P:
Il problema dell’ordinamento: Insertion
Sort
Guido Proietti
Email: [email protected]
URL: www.di.univaq.it/~proietti/index_personal
1
InsertionSort
Approccio incrementale: assumendo che i primi k elementi
siano ordinati, estende l’ordinamento ai primi k+1
elementi, inserendo l’elemento in posizione k+1-esima
nella giusta posizione rispetto ai primi k elementi
2
7
2
4
5
3
1
2
4
5
7
3
1
2
7
4
5
3
1
2
3
4
5
7
1
2
4
7
5
3
1
1
2
3
4
5
7
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
5.
if (A[j] > x) then break
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
• Linea 2: elemento x=A[k+1] da inserire nella posizione che gli
compete
• Linee 3 e 4: individuano la posizione j in cui va messo x
• Linee 5 e 6: se la posizione j è diversa da k+1, si fa spazio per
inserire x, “shiftando” tutti gli elementi da j a k verso destra
3
Correttezza
• Si dimostra facendo vedere che alla fine del generico
passo k (k=1,…, n-1) i primi k+1 elementi sono ordinati
(si noti la differenza con il Selection Sort, in cui invece
dovevamo far vedere anche che erano i più piccoli)
• Induzione su k:
– k=1: banale: si riordinano A[1] e A[2];
– k>1: All’inizio del passo k i primi k elementi sono ordinati
(ipotesi induttiva). Allora la tesi segue dal fatto che
l’algoritmo inserisce A[k+1] nella giusta posizione rispetto
alla sequenza A[1],…,A[k]
4
Complessità temporale
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
1 assegnamento
if (A[j] > x) then break
5.
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
j*≤k+1
confronti
k+1–j*
assegnamenti
n-1
T(n) = (n)+ (k+1) =  (n2)
k=1
T(n) = Tbest(n) = Tavg(n) = (n2)
Possiamo fare meglio?
5
k+1
oper.
il tutto eseguito
per k=1,…, n-1
Una variante dell’IS più efficiente
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.
tk ≤ 2k
assegnam.
A[j+1] = A[j]
6.
j= j-1
7.
A[j+1]=x
n-1
il tutto eseguito
per k=1,…, n-1
n-1
T(n)=(n)+ tk ≤ (n)+ 2k = (n)+n·(n-1) = (n2)
k=1
 T(n) = O(n2)
6
k=1
Si noti che T(n) è AL PIÙ UGUALE ad un
polinomio di 2º grado in n, e quindi la
notazione O è perfettamente ESPRESSIVA del
valore di T(n)
Caso migliore, peggiore, e medio di
InsertionSort2
• Caso migliore
– array già ordinato in ordine crescente  tk = 0
 Tbest(n) = (n) (costo del ciclo for esterno)
• Caso peggiore
– array ordinato in ordine decrescente  tk = 2k
n-1
 T(n) =  2k = (n2)
k=1
• Caso medio
– L’elemento in posizione k+1 ha la medesima probabilità di essere
inserito in ciascuna delle k posizioni che lo precedono  la sua
posizione attesa è k/2  il valore atteso di tk = k
n-1
 Tavg(n) =  k = (n2)
k=1
7

Legge di Murphy?
« Se qualcosa può andar male, lo farà. »
In realtà, negli algoritmi il caso medio costa spesso
come il caso peggiore (asintoticamente), in quanto le
strutture di controllo fondamentali degli algoritmi sono i
cicli, e spesso il caso medio implica l’esecuzione della
metà delle istruzioni di un ciclo, senza quindi avere un
abbattimento asintotico della complessità.
8
Riepilogo
Caso
Caso Caso
migliore medio peggiore
9
Selection Sort
Θ(n2)
Θ(n2)
Θ(n2)
Insertion Sort 1
Θ(n2)
Θ(n2)
Θ(n2)
Insertion Sort 2
Θ(n)
Θ(n2)
Θ(n2)
Notazione asintotica W
f(n) = W(g(n)) se  due costanti c>0 e n0≥0 tali
che f(n) ≥ c g(n) per ogni n ≥ n0
f(n) = W(g(n))
f(n)
c g(n)
n0
10
n
Legame con il concetto di limite
Se g(n) è definitivamente diversa da 0 per n∞
(praticamente, tutti i casi di nostro interesse),
avremo che
fn   Wgn 

limn
fn 
gn 
0
ovvero f(n)=Ω(g(n) se e solo se f(n) è un infinito di
ordine non inferiore a g(n)
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Relazioni tra O, Ω e Θ
fn   g(n) 

fn   Ogn 
fn   Og(n) 

fn   Θgn 
fn   g(n) 

fn   Wgn 
fn   Wg(n) 

fn   Θgn 
fn   g(n)   fn   Wgn  e fn   Ogn 
12
Complessità spaziale
Ricordiamo che oltre alla complessità temporale
dobbiamo valutare anche la complessità spaziale di un
algoritmo, ovvero lo spazio di memoria necessario per
ospitare le strutture di dati utilizzate dall’algoritmo.
La complessità spaziale del Selection Sort
e dell’Insertion Sort è Θ(n)
Nota: Se la complessità spaziale di un certo algoritmo è Θ(g(n)), e se tale
algoritmo “ispeziona” l’intera memoria occupata, allora la complessità
temporale dell’algoritmo è W(g(n)), ovviamente.
13
Conseguenze per il problema dell’ordinamento
La complessità spaziale di qualsiasi algoritmo che risolve il
problema dell’ordinamento è W(n) (dimensione input)
…ma qualsiasi algoritmo che risolve il problema
dell’ordinamento deve ispezionare tutti i dati in ingresso, e
quindi ha complessità temporale T(n)=W(n)

Tutti gli algoritmi che risolveranno il problema
dell’ordinamento avranno una complessità temporale W(n)
14
Delimitazione superiore e inferiore alla
complessità di un problema
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 quindi abbiamo già progettato) che risolve P
e il cui costo di esecuzione rispetto a quella risorsa è O(g(n)) (ad
esempio, nel caso della risorsa tempo, deve essere T(n)=O(g(n))).
Definizione (lower bound o complessità intrinseca di un
problema):
Un problema P ha una delimitazione inferiore alla complessità
W(g(n)) rispetto ad una certa risorsa di calcolo (spazio o tempo) se
ogni algoritmo (anche quelli non ancora progettati!!!) che risolve P
ha costo di esecuzione W(g(n)) rispetto a quella risorsa (ad esempio,
nel caso della risorsa spazio, deve essere S(n)= W(g(n))).
15
Copyright © 2004 - The McGraw - Hill Companies, srl
Ottimalità di un algoritmo
Definizione:
Dato un problema P con complessità intrinseca W(g(n))
rispetto ad una certa risorsa di calcolo (spazio o tempo), un
algoritmo che risolve P è ottimo (in termini di complessità
asintotica) se ha costo di esecuzione O(g(n)) rispetto a
quella risorsa, e quindi la sua complessità asintotica risulta
la migliore possibile.
Obiettivo principale di un algoritmista:
Dato un problema P, trovare un algoritmo ottimo (in
genere rispetto alla risorsa tempo) che risolva P. Ciò può
essere ottenuto dimostrando da un lato che il problema è
intrinsecamente difficile (alzando il lower bound), e
dall’altro progettando algoritmi sempre più efficienti
(abbassando l’upper bound).
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Quindi, per il problema dell’ordinamento…
• Upper bound temporale: O(n2)
– Insertion Sort, Selection Sort
• Lower bound temporale: W(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 ?
17
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.
18
Lower bound W(n log n) per l’ordinamento
• Consideriamo un generico algoritmo A, che ordina
eseguendo solo confronti: dimostreremo che A esegue (nel
caso peggiore) W(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
19
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
20
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.
21
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)
22
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
23
Il lower bound W(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à:
h(n)  log2(#foglie)  log2(n!) > log2 (n/e)n =
Formula di Stirling:
n!  (2pn)1/2 ·(n/e)n
> (n/e)n
24
= n log2 (n/e) =
= n log2 n – n log2 e =
= W(n log n)
QED