Vedremo in seguito che (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 è (n2).

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

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 3i j

3k

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

xi 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 xi i+1

u vkj

(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 xi i+1

vk

x yi i+1

vk

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 xi i+1

uj

x yi i+1

uj

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 = (n2) 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.

Abbiamo visto che la complessità nel caso pessimo di ogni algoritmo di ordinamento sul posto che confronta e scambia tra loro elementi consecutivi dell’array è (n2).

Per ottenere algoritmi più efficienti dobbiamo quindi operare confronti e scambi tra elementi “distanti” dell’array.

L’algoritmo Heap-Sort confronta elementi non consecutivi e possiamo quindi sperare che la sua complessità sia minore.

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)=n2+O(n) significa che T(n) è la somma di n2 e di una funzione che cresce al più linearmente.

niniT

niniT H

H

2 se),2()1(

2 se)1(),(

maxmax

Max-Heapfy(A,i) // Analisi: Complessità l = 2i, r = 2i+1 m = i if l A.heapsize and A[l] > A[m] m = l if r A.heapsize and A[r] > A[m] m = r if m i t = A[i], A[i] = A[m], A[m] = t Max-Heapfy(A,m)

)1(log)1( 2

i

nb

i

na

2log

)1(

)1(

2/

1 maxmax ),()()(n

i

HBMH niTnnT

Build-Max-Heap (A) A.heapsize = A.length for i = A.lenght/2 downto 1 Max-Heapfy(A,i)

2/

1

2/

1 2log)(n

i

n

ib

i

nan

2/

1 2log)(n

ib

i

nan

2/

1 2log)(n

i i

nan

n

i

n

ib

ia

i

nan

2 2

2/

1 2 1

1loglog)(

Heap-Sort (A) Build-Max-Heap(A) for i = A.length downto 2 t = A[i], A[i] = A[1], A[1] = t A.heapsize = A.heapsize - 1 Max-Heapfy(A,1)

n

i

Hn

i

HS iTni

nannT

2 max

2/

1 2max )1,1()(log)()(

1

1 2

2/

1 2 )(loglog)(n

i

n

iia

i

nan

n

i

n

i

n

ibia

i

nan

22 2

2/

1 2 )1(loglog)(

n

mjjf )(

1)()(

n

m

n

mjdxxfjf

f(x) funzione crescente

m m+1 m+2 n n+1n-1n-2x

f(x)

f(m)f(m+1)

f(m+2)

m+3

f(n)

f(n-1)f(n-2)

f(m+3)

n-3m+4

…

m-1

Valutazione di sommatorie (App. A del testo)

f(m

)

f(m

+1)

f(m

+2)

f(n)

f(n-

1)

f(n-

2)

f(n-

3)

f(m

+3)

f(m

+3)

f(m

+4)

f(m

)

f(m

+1)

f(m

+2)

f(n)

f(n-

1)

f(n-

2)

n

mjjf )(

1

1)()()(

n

m

n

mj

n

mdxxfjfdxxf

f(x) funzione crescente

m m+1 m+2 n n+1n-1n-2x

f(x)

f(m)f(m+1)

f(m+2)

m+3

f(n)

f(n-1)f(n-2)

f(m+3)

n-3m+4

…

m-1

n

mjjf )(

n

m

n

mjdxxfjf

1)()(

f(x) funzione decrescente

m m+1 m+2 n n+1n-1n-2x

f(x)

m+3 n-3

f(n)

f(n-

1)

f(n-

2)

f(m

)

f(m

+1)

f(m

+2)

f(n)f(n-1)

f(n-2)

f(m)

f(m+1)f(m+2)

f(n-3)

…

m-1

f(m

+3)

f(n-

3)

f(n-

2)

f(n-

2)

f(n)

f(n-

1)

f(n-

2)

f(m

)

f(m

+1)

f(m

+2)

n

mjjf )(

n

m

n

mj

n

mdxxfjfdxxf

1

1)()()(

f(x) funzione decrescente

m m+1 m+2 n n+1n-1n-2x

f(x)

m+3 n-3n-4

f(n)f(n-1)

f(n-2)

f(m)

f(m+1)f(m+2)

f(n-3)

…

m-1

2/

2

2/

1lnlnln

n

j

n

j j

nn

j

n

dx

x

nndx

x

nn

nn

2/

1

2/

1lnlnlnln

2/

1

2/

1lnlnln

nnxdxdxnn

2/1lnln)1

2(ln nxxxnn

n

122

ln2

ln2

nnn

nn

12

2ln2

ln2

ln2

nn

nn

nn

)(12

2ln2

nnn

)(ln2/

1nO

j

nn

j

)log()log()()()(max nnOnnOnOnnT HS

Dunque Heap-Sort richiede tempo O(n log n) per ordinare un array di n elementi.

)ln(1ln

lnlnln 11

1

1

nnOnnn

xxxdxxi nnn

i

Implementazione di code con priorità

Gli heap binari si possono usare, oltre che per ordinare un array, anche per implementare delle code con priorità.

Le code con priorità sono delle strutture dati in cui è possibile immagazzinare degli oggetti x a cui è attribuita una priorità x.key ed estrarli uno alla volta in ordine di priorità.

Possono inoltre essere definite anche:Increase-Key(S,x,p): aumenta la priorità di xChange-Key(S,x,p): cambia la priorità di x

Le operazioni fondamentali sulle code con priorità sono:Insert(S, x): aggiunge x alla coda SMaximum(S): ritorna x S con x.key massimaExtract-Max(S): toglie e ritorna x S con x.key massima.