Algoritmi e Strutture Dati Laurea in Informatica

Algoritmi e Strutture Dati Laurea in Informatica

Calendario: 27 Febbraio – 13 Giugno Aula: LuM250

Orario: Mer 12.30-14.15

Gio, Ven 14.30-16.15 Numero crediti = 9 (~ 72 ore)

~ 52 ore di teoria, ~20 ore di esercizi Docenti: Paolo Baldan (5crediti)

Michele Scquizzato (4 crediti)

a. Prova intermedia

per l’assegnazione di un bonus fino a 3 punti (che si somma al voto dell’esame finale)

b. Prova scritta

(5 appelli - indispensabile iscriversi nella lista di esame che verrà attivata su UNIWEB)

c. Registrazione, con possibile orale (su base volontaria). Indispensabile per conseguire la lode.

Modalità d’Esame

Testo: Introduzione agli Algoritmi e Strutture Dati (3°

ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.

McGraw-Hill.

Pagina del corso:

www.math.unipd.it/~baldan/Algoritmi + Moodle con altro materiale

Trad. di: Introduction to Algorithms and Data Structures (3° ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest,

C.Stein. MIT Press.

Materiale didattico

Programma

Le prime 5 parti del testo (con qualche omissione):

I. Fondamenti: notazione per gli algoritmi e primi esempi di algoritmi e di analisi degli algoritmi II. Ordinamento e statistiche d’ordine

III. Strutture dati fondamentali

IV. Tecniche avanzate di progettazione ed analisi degli algoritmi

V. Strutture dati avanzate

I problemi computazionali, gli algoritmi che li risolvono e le tecniche per sviluppare tali

algoritmi

INTRODUZIONE

Esempio1: problema dell’ordinamento

Input: a₁,a₂,...,a_n

Output: a'₁,a'₂,...,a'_n permutazione (riarrangiamento) di a₁,a₂,...,a_n tale che a'₁ £ a'₂ £ ... £ a'_n

TECNICA

INCREMENTALE

Soluzione1: Algoritmo Insertion-Sort.

1 n

A

1 n

A

1 j n

A key

1 j n

A i

1 j n

A

j

1 n

A j

1 j n

A i

key

1 j n

Ai key

Insertion-Sort(A) n = A.length for j = 2 to n

key = A[j]

// inseriamo A[j] nella sequenza // ordinata A[1..j-1]

i = j - 1

while i > 0 and A[i] > key A[i+1] = A[i]

i = i – 1 A[i+1] = key

Insertion-Sort(A) n = A.length for j = 2 to n

key = A[j]

// inseriamo A[j] nella // sequenza ordinata // A[1..j-1]

i = j – 1

while i > 0 and A[i] > key A[i+1] = A[i]

i = i – 1 A[i+1] = key

void Insertion-Sort(vector<T> A) {

int i, j, n = A.size(); T key;

for (j = 1; j < n; j++) {

key = A[j];

// inseriamo A[j] nella // sequenza ordinata // A[0..j-1]

i = j – 1;

while (i >= 0 && A[i] > key) {

A[i+1] = A[i];

i--;

}

A[i+1] = key;

} }

Insertion-Sort(A) n = A.length

for j = 2 to n

// inserisce A[j] nella // sequenza ordinata // A[1..j-1]

key = A[j]

i = j – 1

while i > 0 and A[i] > key A[i+1] = A[i]

i = i – 1 A[i+1] = key A

5 2 8 4 7 1 3 6

key

5 # 8 4 7 1 3 6 2

# 5 8 4 7 1 3 6 2 5 8 4 7 1 3 6

2 5 # 4 7 1 3 6 8 2 5 # 4 7 1 3 6

2 5 8 4 7 1 3 6

2 5 8 # 7 1 3 6 4 2 # 5 8 7 1 3 6

2 4 5 8 7 1 3 6

2 4 5 8 # 1 3 6 7 2 4 5 # 8 1 3 6

2 4 5 7 8 1 3 6

Insertion-Sort(A) n = A.lenght

for j = 2 to n

// inserisce A[j] nella // sequenza ordinata // A[1..j-1]

key = A[j]

i = j – 1

while i > 0 and A[i] > key A[i+1] = A[i]

i = i – 1 A[i+1] = key A

2 4 5 7 8 1 3 6

key

2 4 5 7 8 # 3 6 1

# 2 4 5 7 8 3 6 1 2 4 5 7 8 3 6

1 2 4 5 7 8 # 6 3 1 2 # 4 5 7 8 6

1 2 3 4 5 7 8 6

1 2 3 4 5 7 8 # 6 1 2 3 4 5 # 7 8

1 2 3 4 5 6 7 8

Insertion-Sort(A) n = A.length

for j = 2 to n key = A[j]

i = j - 1

while i > 0 and A[i] > key

A[i+1] = A[i]

i = i – 1

A[i+1] = key

Analisi di Insertion-Sort: correttezza

Correttezza InsertionSort

1 j n

A

i

1 j n

A

1 j n

A

i

1 j n

A i

1 j n

A

Analisi di Insertion-Sort: complessità

Insertion-Sort(A) //

n = A.length //

for j = 2 to n //

key = A[j] //

i = j -1 //

while i > 0 and A[i] > key //

A[i+1] = A[i] //

i = i – 1 //

A[i+1] = key //

) 1

2(

5

å

n

j tj

c c0

n c₂

) 1

3(n - c

) 1

4(n - c

å

j t j

c_{6 2}

å

j t j

c_{7 2}

) 1

8(n - c

j t

<

£ 0

c1

å å

+

- +

+ +

+ +

=

n

j j

n

j j

IS

t c

c t

c

n c

c c

n c c

c n

T

7 2 2 6

5

8 4

3 2

1 0

) (

) 1 (

) 1 )(

( )

(

caso migliore:

å å

+ +

+

- +

+ +

+ +

=

n j n

j IS

c c

c

n c

c c

n c c

c n

T

7 2 2 6

5

8 4

3 2

1 0

min

0 )

( 1

) 1 )(

( )

(

= 0

t j ^{0 £ t}_j ^{< j}

a bn

c c

c c

c c

n c

c c

c c

n T ^IS

+

=

- -

- -

+ +

+ +

+ +

= ( ) ( )

)

( _{2 3 4 5 8 0 1 3 4 5 8}

min

caso peggiore: ^t

^{= j - 1}

' '

'

) (

2 ) 1 2

1 2

( 1

) 2 (

) 1 (

2

8 4

3 1

0

8 7

6 5

4 3

2

2 7

6 5

max

a n

b n

c

c c

c c

c

n c

c c

c c

c c

n c

c c

n T ^IS

+ +

=

- -

- +

+

+ -

- +

+ +

+

+ +

=

j t

<

£ 0

å

å

- +

+ +

+ +

=

n j n

j IS

j c

c j

c

n c

c c

n c c

c n

T

7 2 2 6

5

8 4

3 2

1 0

max

) 1 (

) (

) 1 )(

( )

(

caso medio:

å

å

-

=

+

+ +

+

- +

+ +

+ +

=

n j n j

j

j IS

c c

c

n c

c c

n c c

c n

T

2 2 7 1

2 2 6 5 1

8 4

3 2

1 0

med

) (

) 1 )(

( )

(

2 -1

=

t

"

"

"

) (

4 ) 1 4

1 4

( 3

) 4 (

) 1 (

2

8 5

4 3

1

8 7

6 5

4 3

2

2 7

6 5

med

a n

b n

c

c c

c c

c

n c

c c

c c

c c

n c

c c

n T

+ +

=

- -

- -

+

+ -

- +

+ +

+

+ +

=

j t

<

£

0

TECNICA

DIVIDE ET IMPERA

5 2 8 0 4 7 1 9 3 2 6

0 4 7 2

5

5 2 8

5 2 8 0 4 7

5 2 8 0 4 7 1 9 3 2 6

2 6 1 9 3

1 9 3 2 6

9 1

4 0

5 2 8 0 4 7 1 9 3 2 6

5 2 8 0 4 7 1 9 3 2 6

5 2 8 0 4 7 1 9 3 2 6

5 2 8 2

5

0 4 7 1 9 3

4

0 1 9

6 2

0 1 2 2 3 4 5 6 7 8 9 0 2 4 5 7 8

2 5 8 2 5

5 2

8

1 2 3 6 9

0 4 7 1 3 9 2 6

0 4 7 1 9 3

4

0 1 9

6 2

Soluzione2: Algoritmo Merge-Sort

Merge-Sort(A,p,r) if p < r

q = ë(p+r)/2û

Merge-Sort(A,p,q) Merge-Sort(A,q+1,r) Merge(A,p,q,r)

L

0 2 4 5 7 8 1 2 3 6 9

0 2 4 5 7 8 ¥ R 1 2 3 6 9 ¥ A[p..q] A[q+1..r]

0

2 4 5 7 8 ¥ 1 2 3 6 9 ¥ 0 1

2 4 5 7 8 ¥ 2 3 6 9 ¥

0 1 2

4 5 7 8 ¥ 2 3 6 9 ¥

0 1 2 2

4 5 7 8 ¥ 3 6 9 ¥

0 1 2 2 3

4 5 7 8 ¥ 6 9 ¥

0 1 2 2 3 4

5 7 8 ¥ 6 9 ¥

0 1 2 2 3 4 5

7 8 ¥ 6 9 ¥

0 1 2 2 3 4 5 6

7 8 ¥ 9 ¥

0 1 2 2 3 4 5 6 7

8 ¥ 9 ¥

0 1 2 2 3 4 5 6 7 8

¥ 9 ¥

0 1 2 2 3 4 5 6 7 8 9

¥ ¥

A[p..r]

Merge(A,p,q,r) n₁ = q – p + 1 n₂ = r – q

for i = 1 to n₁

L[i] = A[p + i – 1]

for j = 1 to n₂

R[j] = A[q + j]

L[n₁ + 1] = R[n₂ + 1] = ¥ i = j = 1

for k = p to r

if L[i] £ R[j]

A[k] = L[i]

i = i + 1 else

A[k] = R[j]

j = j + 1

Merge-Sort(A,p,r)

if p < r // altrimenti A[p..r] è ordinato q = ë(p+r)/2û

Merge-Sort(A,p,q) Merge-Sort(A,q+1,r)

Merge(A,p,q,r)

Analisi di Merge-Sort: correttezza

non ordinati

1 p r n

A

ordinati

1 p r n

A

ordinati

1 p ordinati r n

A q

Merge(A,p,q,r) n₁ = q – p + 1 n₂ = r – q

for i = 1 to n₁

L[i] = A[p + i – 1]

for j = 1 to n₂ R[j] = A[q + j]

L[n₁ + 1] = R[n₂ + 1] = ¥ i = j = 1

for k = p to r if L[i] £ R[j]

A[k] = L[i]

i = i + 1 else

A[k] = R[j]

j = j + 1

1 p q r n

A

1 p r n

A

L ∞ R ∞

1 n₁ 1 n₂

1 p r n

A

L ∞ R ∞

1 n₁ 1 n₂

k

i j

1 p r n

A

L ∞ R ∞

1 n₁ 1 n₂

k

i j

Merge(A,p,q,r) // complessità //

n₁ = q – p + 1 //

n₂ = r – q //

for i = 1 to n₁ //

L[i] = A[p + i – 1] //

for j = 1 to n₂ //

R[j] = A[q + j] //

L[n₁ + 1] = R[n₂ + 1] = ¥ //

i = j = 1 //

for k = p to r //

if L[i] £ R[j] //

A[k] = L[i] //

i = i + 1 //

else

A[k] = R[j] //

j = j + 1 //

c1

c2

c3

( ₁ ¹)

4 n + c

1 5n c₄(n₂ +¹)

c

2 5n c

c6

ë^{(p r)/2}û

q = +

2 11n c

c7

( ¹)

8 n+ c

1 11n c

n c₉

1 10n c

2 10n c

+1 -

= r p n

é ^/2ù

1 n

n =

ë ^/2û

2 n

n =

2

1 n

n n = +

' '

2

) (

) (

8 7

6 4

3 2

1

11 10

9 8

5 4

b n a

c c

c c

c c

c

n c

c c

c c

c n

T ^M

+

=

+ +

+ +

+ +

+

+ +

+ +

+

=

Merge-Sort(A,p,r) //complessità //

if p < r //

q = ë(p+r)/2û //

Merge-Sort(A,p,q) //

Merge-Sort(A,q+1,r) //

Merge(A,p,q,r) //

c1

c2

c3

( )ⁿ₁

T ^MS

( )n₂ T ^MS

( )n a'n b' T^M = +

+1 -

= r p n

îí ì

>

+ +

+ +

+

£

= +

1 se

) ( )

( )

(

1 ) se

(

2 1

3 2

1

2 1

n n

T n

T n

T c

c c

n c

n c

T ^MS _{MS MS M}

1 = q - p +1 n

q r n₂ = -

2

1 n

n n = +

îí ì

>

+ +

+

= £

1 se

) (

) (

1 ) se

(

2

1 T n n

n T

b an

n n c

T ^MS _{MS MS}

( )

_é

_ù

T ^MS @ log₂ + ( -1) +

b

an_1,1 + an_1,2 + b an_2,1 + b an_2,2 + b

é^{log2 n}ù

c c c c c c c c c c c c

b an +

b an 2+

b an 4+

cn

( ) _î^íì + + ( )+ ( ) >

= £

1 se

1 se

2

1 T n n

n T

b an

n n c

T^MS _{MS MS}

b an +

( )ⁿ₁

T ^{MS TMS}( )ⁿ₂

b an₁ +

( )

T ^MS T ^MS( )n1,2

b an₂ +

( )n2,1

T ^MS T^MS( )n2,2

( )

T ^MS @ + +

( ) ( )

lim ₂ ² =

+ +

+

= _®¥ +

¥

® a n b n c

c n

b n

n a n

T

n T

IS n med

MS n

Dunque esiste N tale che per ogni n > N.

Qualunque siano i valori delle costanti a', b', c', a", b" e c" l’algoritmo Merge-Sort è superiore a Insertion-Sort

per array di dimensione sufficientemente grande.

( )

( )

T ^MS < _med^IS

( )

T ^MS @ + +

"

"

"

)

(n a n² b n c T_med^IS = + +

Possiamo dire che “cresce come” n² mentre “cresce come” n log₂ n.

( )

T_med^IS

( )

T ^MS

n n² n log₂ n

IS n² ns

MS

n log₂ n ns

10 100 33 0.1µs 0.033µs

100 10000 664 10µs 0.664µs

1000 10⁶ 9965 1ms 10µs

10000 10⁸ 132877 0.1s 133µs 10⁶ 10¹² 2·10⁷ 17m 20ms

10⁹ 10¹⁸ 3·10¹⁰ 30s

10⁹ 10¹⁸ 3·10¹⁰ 70anni 30s

( ) ( )

¥

® " "

' '

log lim '

lim ²

b n

a

c n

b n

n a n

T

n T

IS n min

MS n

dunque esiste N tale che per ogni n > N.

Qualunque siano i valori delle costanti a', b', c', a", b" l’algoritmo Insertion-Sort è superiore a Merge-Sort per array (quasi) ordinati e

sufficientemente grandi.

( )

( )

T ^MS > _min^IS

Insertion-Sort è anche superiore a Merge-Sort per array piccoli in quanto le costanti a', b', c' in sono generalmente molto maggiori delle costanti a", b" e c" in .

( )

T ^MS

( )

T_max^IS

Questo suggerisce una modifica di Merge-Sort in cui le porzioni di array di dimensione minore di una certa costante k si ordinano con Insertion-Sort invece di usare ricorsivamente Merge-Sort.

Soluzione3: Algoritmo Merge-Ins-Sort

Merge-Ins-Sort(A,p,r) if p < r

if r-p+1 < 32

InsertSort(A,p,r) else

q = ë(p+r)/2û

Merge-Ins-Sort(A,p,q) Merge-Ins-Sort(A,q+1,r) Merge(A,p,q,r)

Complessità e Notazione Asintotica

Quando si confrontano algoritmi, determinare il tempo di esecuzione

-È complicato

-Contiene dettagli inutili che vorremmo ignorare

-Dipende da costanti non note

vogliamo darne una visione più astratta (tasso di crescita)

Paragonare tra loro algoritmi

Abbiamo una scala di complessità:

vogliamo inserire ogni algoritmo in questa scala

1 log

log ...

2 ...

2 3

n n n n

n n

n

Un algoritmo può richiedere tempi diversi per input della stessa taglia. Ad esempio il tempo per ordinare n oggetti può dipendere dal loro ordine iniziale.

complessità massima

complessità minima complessità media

1 log

log ...

2 ...

2 3

n n n n

n n

n

Nell’analizzare la complessità tempo di un algoritmo siamo interessati a come aumenta il tempo al crescere della taglia n dell’input.

Siccome per valori “piccoli” di n il tempo richiesto è comunque poco, ci interessa

soprattutto il comportamento per valori

“grandi” di n (il comportamento asintotico)

Inoltre, siccome la velocità del processore influisce sul tempo calcolo per una costante moltiplicativa noi valuteremo la complessità a meno di una tale costante.

Questo giustifica le seguenti definizioni:

Notazione asintotica O

(limite superiore asintotico)

} ogni

per )

( )

( 0

che tali

ed 0

esistono :

) ( { ))

( (

0 0

n n

n cg n

f

n c

n f

n g

³

£

£

>

= O

) (n f

) (n cg

n0

O(g(n))

Scriveremo f(n) = O(g(n)) per dire che f(n) è una delle funzioni dell’insieme O(g(n))

f(n) = O(g(n)) si legge:

f(n) è “o grande” di g(n)

Se f(n) = O(g(n)) rappresenta il tempo calcolo richiesto da un algoritmo diciamo che

O(g(n)) è un limite superiore asintotico per la

complessità tempo di tale algoritmo.

esempi

) (

5 5

2 )

(n n² n O n²

f = + + =

infatti ^{0 £ 2 n}

^{+ 5 n + 5 £ cn}

per c = 4 ed n

= 5

) 1 ( sin

2 )

( n n O

f = + =

infatti

per c = 3 ed n

= 1

) (

)

( n a

n

a

n a

O n

f = + + =

Vedremo che in generale per a

> 0

Notazione asintotica W . (limite inferiore asintotico)

} ogni

per 0

) ( )

(

che tali

ed 0

esistono :

) ( { ))

( (

0 0

n n

n cg n

f

n c

n f n

g

³

³

³

>

= W

) (n f

) (n cg

n0

Se f(n) = W(g(n)) rappresenta il tempo

calcolo richiesto da un algoritmo diciamo che W(g(n)) è un limite inferiore asintotico per la complessità tempo di tale algoritmo.

Scriveremo f(n) = W(g(n)) per dire che f(n) è una delle funzioni dell’insieme W(g(n)).

f(n) = W(g(n)) si legge:

f(n) è “omega” di g(n)

esempi

) (

5 5

2 )

(n n² n n²

f = - - = W

infatti

per c = 1 ed n

= 10

) 1 ( sin

2 )

(n = + n = W f

infatti

per c = 1 ed n

= 1

) (

)

(n a₂n² a₁n a₀ n²

f = + + = W

Vedremo che in generale se a

> 0

Notazione asintotica Q . (limite asintotico stretto)

)}

( )

( )

( 0

ogni per

che tali

ed 0 ,

esistono :

) ( { ))

( ( ))

( ( ))

( (

2 1

0 0

2 1

n g c n

f n

g c

n n

n c

c

n f n

g n

g O n

g

£

£

£

³

>

= W

Ç

= Q

) (n f

)

1g(n c

n0

)

2g(n c

Se f(n) = Q(g(n)) rappresenta il tempo calcolo richiesto da un algoritmo diciamo che Q(g(n)) è un limite asintotico stretto per la

complessità tempo di tale algoritmo.

Scriveremo f(n) = Q(g(n)) per dire che f(n) è una delle funzioni dell’insieme Q(g(n)).

f(n) = Q(g(n)) si legge:

f(n) è “theta” di g(n)

esempi

) (

5 5

2n² - n + = O n² 2n² - 5n + 5 = W(n²)

2 2 2

2

1 2 5 5

0 £ c n £ n - n + £ c n per c₁ = 1, c₂ = 4 ed n₀ = 10

) (

5 5

2n² - n + = Q n² Dunque

) 1 ( sin

2 + n = O

2 + sin n = W ( 1 )

) 1 ( sin

2 + n = Q

Dunque

) (

5 5

2 )

(n n² n n³

f = + + ¹ Q

per ogni n ³ n₀ allora

5 5

2

0 £ c₁n³ £ n² + n +

altrimenti

3 1 2

5 5

2

n n

c £ n + + per ogni n ³ n₀. Assurdo!

) ( 5

5 2

)

(n n² n n

f = + + ¹ Q

per ogni n ³ n₀ allora n

c n

n² 5 5 ₂ 2

0 £ + + £

altrimenti

n c n

n

2 2

5

2 + 5 + £ per ogni n ³ n₀. Assurdo!

Metodo del limite

Spesso è possibile determinare dei limiti

asintotici calcolando il limite di un rapporto.

Ad esempio se

lim

f ( n ) / g ( n ) = k > 0

allora per ogni e > 0 esiste n₀ tale che per n ≥ n₀

e

e £ £ +

- f n g n k

k ( ) / ( )

Preso 0 < e < k e posto c₁ = k - e e c₂ = k +e

) ( )

( )

(

1

g n f n c g n

c £ £

)) (

( )

( n g n f = Q

e quindi

Se diciamo che

Attenzione: quando il limite del rapporto non esiste questo metodo non si può usare.

¥

¥ =

® ( )

) lim (

n g

n f

n f (n) =

w

)) (

( )

(

ma

)) (

( )

( n g n f n g n

f = W ¹ Q

ed in questo caso

Se diciamo che0 )

( ) lim _®¥ ( =

n g

n f

n

f ( n ) = o ( g ( n ))

)) (

( )

(

ma

)) (

( )

(n O g n f n g n

f = ¹ Q

ed in questo caso

In generale f (n) = a_kn^k +...+ a₁n + a₀ = Q(n^k ) per ogni funzione polinomiale di grado k con coefficiente a_k > 0.

Inoltre

b a

b

a

¹ Q

¹ Q ( ) ( ) per

b a

n

n _b

a ) (log ) per ogni e

(log = Q Q

) (

) log

( n

n ¹ Q n

Q

h k

n

n

¹ Q

¹ Q ( ) ( ) per

n b

n _{a b}

a log log

log

perché =

) (

) (

) log

(

) (

) (

) (log

n n

k

k h

b O

a O

n n

O

n O

n O

n O

Í Í

Í

Í Í

Í

) (

) (

) log

(

) (

) (

) (log

n n

k

k h

b a

n n

n n

n

Q

¹ Q

¹ Q

¹

¹ Q

¹ Q

¹ Q

Per 0 < h < k e 1 < a < b :

Useremo le notazioni asintotiche anche all’interno delle formule.

In questo caso le notazioni O(f(n)), Ω(f(n)) e

ϴ(f(n)) stanno ad indicare una qualche funzione appartenente a tali insiemi e di cui non ci

interessa conoscere la forma esatta ma solo il comportamento asintotico.

Ad esempio T(n)=n²+O(n) significa che T(n) è la somma di n² e di una funzione che cresce al più linearmente.

esiste un algoritmo che risolve il problema con questa complessità

limite superiore: O(n²)

1 log

log ...

2 ...

2 3

n n n n

n n

n

Valutare la difficoltà dei problemi

Valutare la difficoltà dei problemi

ogni algoritmo che risolve il problema ha complessità

maggiore o uguale di questa limite inferiore: W(n)

1 log

log ...

2 ...

2 3

n n n n

n n

n

Un limite superiore per il problema dell’ordinamento

Abbiamo visto che Insert-Sort per ordinare n oggetti richiede O(n

) operazioni

Quindi O(n

) è un limite superiore

Vedremo in seguito che Q(n log n) è un limite stretto per il problema dell’ordinamento.

Per ora ci limitiamo a dimostrare che:

La complessità nel caso pessimo di ogni

algoritmo di ordinamento sul posto che confronta e scambia tra loro soltanto elementi consecutivi dell’array è W(n²).

Quindi il problema di ordinare sul posto un array scambiando tra loro soltanto elementi consecutivi ha complessità Q(n²).

Se l’array è ordinato non ci sono inversioni.

Se l’array è ordinato in senso opposto e gli

elementi sono tutti distinti allora ogni coppia (i, j) di indici con i < j è una inversione e quindi ci

sono esattamente n(n-1)/2 inversioni.

Sia A[1..n] un array

Se i < j e A[i] > A[j] diciamo che la coppia di indici (i, j) è una inversione

8 3

i j

3

k

Come cambia il numero di inversioni quando facciamo uno scambio tra due elementi

consecutivi A[i] ed A[i+1] dell’array?

Consideriamo tutte le coppie di indici ( j, k) con j < k e vediamo quante e quali di esse

possono cambiare di stato da inversioni a non inversioni o viceversa quando scambiamo

A[i] con A[i+1].

x

i i+1

y

Se j e k sono entrambi diversi da i e i+1 la coppia ( j, k) non cambia di stato e quindi il numero di inversioni di questo tipo non cambia.

y x

i i+1

u v

k j

(i, k) è inversione dopo lo scambio se e solo se (i+1, k) lo era prima e (i+1, k) è inversione se e solo se (i, k) lo era prima.

y x

i i+1

v

k

x y

i i+1

v

k

Quindi le due coppie si scambiano gli stati ma il numero totale di inversioni non cambia.

Consideriamo le due coppie (i, k) e (i+1, k) con k > i+1 ossia

y x

i i+1

u

j

x y

i i+1

u

j

La situazione è simmetrica di quella precedente e quindi anche in questo caso il numero totale di

inversioni non cambia.

Consideriamo le coppie (j, i) e (j,i+1) con j < i ossia

In conclusione con lo scambio di due elementi consecutivi dell’array il numero totale di

inversioni aumenta o diminuisce di 1 (o rimane invariato se i due elementi scambiati erano

uguali).

Rimane soltanto da considerare la coppia (i, i+1) che con lo scambio cambia di stato se i due

elementi sono diversi.

Nel caso pessimo in cui l’array è ordinato in senso inverso e gli elementi sono tutti distinti le

inversioni iniziali sono n(n-1)/2.

Siccome n(n-1)/2 = W(n²) rimane dimostrato il limite inferiore.

Occorrono quindi almeno n(n-1)/2 scambi tra elementi consecutivi per ridurre tale numero a 0.

Esercizio: Abbiamo dimostrato che scambiando due elementi diversi consecutivi il numero totale di inversioni aumenta o diminuisce di 1.

Quindi se prima dello scambio il numero di

inversioni totale era pari, dopo lo scambio esso risulta dispari e viceversa.

Mostrare che questo cambiamento della parità del numero totale di inversioni avviene anche se si

scambiano due elementi diversi non consecutivi.

Soluzione delle ricorrenze

Metodo di sostituzione:

Si assume che la soluzione sia di un certo tipo, ad esempio

3 2

2

1

log

)

( n k n n k n k

T = + +

dove k₁, k₂ e k₃ sono delle costanti

Si sostituisce la soluzione nella ricorrenza e si cercano dei valori delle costanti per i quali la ricorrenza è soddisfatta.

Se le cose non funzionano si riprova con un altro tipo di soluzione.