Didattica e Fondamenti degli Algoritmi e della Calcolabilità

(1)

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: guido.proietti@univaq.it

URL: www.di.univaq.it/~proietti/index_personal

1

(2)

InsertionSort

2 7 4 5 3 1 7 2 4 5 3 1

2 4 7 5 3 1

2 4 5 7 3 1 2 3 4 5 7 1 1 2 3 4 5 7

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

(3)

InsertionSort (A)

1. for k=1 to n-1 do

2. x = A[k+1]

3. for j=1 to k+1 do

4. 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

• 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

(4)

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]

(5)

InsertionSort (A)

1. for k=1 to n-1 do

2. x = A[k+1]

3. for j=1 to k+1 do

4. 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

T(n) = (n)+



(k+1) =  (n²)

j*≤k+1 confronti k+1–j*

assegnamenti

il tutto eseguito per k=1,…, n-1

k=1 n-1

T(n) = T

_best

(n) = T

_avg

(n) = (n

²

)

Possiamo fare meglio?

k+1 oper.

Complessità temporale

5

1 assegnamento

(6)

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

il tutto eseguito per k=1,…, n-1

t_k ≤ 2k assegnam.

^T(n)=(n)+



^t_k ^≤^(n)+



^{2k =} (n)+n·(n-1) = (n²)

 T(n) = O(n

²

)

k=1 n-1

Una variante dell’IS più efficiente

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)

6

(7)

Caso migliore, peggiore, e medio di InsertionSort2

• Caso migliore

– array già ordinato in ordine crescente  t_k = 0

 T_best(n) = (n) (costo del ciclo for esterno)

• Caso peggiore

– array ordinato in ordine decrescente  t_k = 2k

 T(n) =



^{2k = (n}²⁾

• 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 t_k = k

 T_avg(n) =



^{k = (n}²⁾



k=1

k=1 n-1 n-1

7

(8)

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à.

(9)

Riepilogo

Insertion Sort 2 Insertion Sort 1

Θ(n) Caso migliore Selection Sort Θ(n²)

Θ(n²)

Caso medio Θ(n²) Θ(n²) Θ(n²)

Θ(n²) Θ(n²) Θ(n²) Caso peggiore

9

(10)

f(n) = W(g(n)) se  due costanti c>0 e n

₀

≥0 tali che f(n) ≥ c g(n) per ogni n ≥ n

₀

Notazione asintotica W

n₀ n

f(n) = W(g(n)) f(n)

c g(n)

(11)

Se g(n) è definitivamente diversa da 0 per n ∞

(praticamente, tutti i casi di nostro interesse), avremo che

ovvero f(n)=Ω(g(n) se e solo se f(n) è un infinito di ordine non inferiore a g(n)

Legame con il concetto di limite

  ^ ^W   ^ __ ^{ }_{ } ^ ⁰ n

g n lim f

n g n

f _n

(12)

Relazioni tra O, Ω e Θ

 n g(n) f n Og n 

f    

 n Og(n) f n Θg n 

f   

 n g(n) f n g n 

f     W

 n g(n) f n Θg n 

f  W  

 n g(n) f n g n  e f n Og n 

f     W 

(13)

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

(14)

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)

(15)

15

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))).

(16)

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).

(17)

Quindi, per il problema dell’ordinamento…

• Upper bound temporale: O(n

²

)

– 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

(18)

Ordinamento per confronti

Dati due elementi a_i ed a_j, per determinarne l’ordinamento relativo effettuiamo una delle seguenti operazioni di confronto:

a_i  a_j ; a_i  a_j ; a_i  a_j ; a_i a_j; a_i  a_j

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.

(19)

• 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 a_i ed a_j (ad esempio effettua il test a_i a_j);

- 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

Lower bound W(n log n) per l’ordinamento

19

(20)

• Descrive le diverse sequenze di confronti che A esegue su un’istanza <a₁,a₂,…,a_n> 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 a_i e a_j)

• Nodo foglia: i₁,i₂,…,i_n (modella una risposta (output) dell’algoritmo, ovvero una permutazione <a_i1,a_i2,…,a_in>

degli elementi)

• L’albero di decisione è associato ad un algoritmo e alla dimensione n dell’istanza

Albero di decisione

(21)

Esempio

2:3

1,2,3 1:3 2,1,3 2:3

1:3 1:2

1,3,2 3,1,2 2,3,1 3,2,1

Š 

Š  Š 

Š 



Input <a₁,a₂,a₃> Riconoscete

l’algoritmo associato?

È proprio l’Insertion Sort 2!

Esercizio per casa: costruire l’albero di decisione per il SS su una sequenza di 3 elementi.

21

(22)

• 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)

Proprietà

(23)

Lemma: Un albero strettamente binario (ovvero, in cui ogni nodo interno ha esattamente due figli) con k foglie ha altezza h(k)  log₂ k.

Dim: Dimostrazione per induzione su k:

– Caso base k=1 (albero-nodo ): banale h(k)=0≥ log₂1=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+log

₂

(k/2)

=1+log

₂

k-log

₂

2=log

₂

k.

QED

Altezza in funzione delle foglie

23

(24)

• 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à:

Il lower bound W(n log n)

h(n)  log₂(#foglie)  log₂(n!)

Formula di Stirling:

n!  (2pn)^1/2 ·(n/e)ⁿ

> (n/e)ⁿ

> log₂(n/e)ⁿ=

= n log₂ (n/e)

= n log₂ n – n log₂ e

=

= W(n log n) QED

=