Michele Tomaiuolo Fondamentidi informatica Complessità

(1)

maiuolo – Fondamenti di informaticamaiuolo – Fondamenti di informatica gegneria dell'informazione – UniPRgegneria dell'informazione – UniPR /www.ce.unipr.it/people/tomamic//www.ce.unipr.it/people/tomamic/

Complessità

Fondamenti di informatica

Michele Tomaiuolo

tomamic@ce.unipr.it

http://www.ce.unipr.it/people/tomamic

(2)

ondamenti di informaticaondamenti di informatica ell'informazione – UniPRell'informazione – UniPR ipr.it/people/tomamic/ipr.it/people/tomamic/

Ricerca lineare

// Schede: ordinate e numerate da 0 a N-1 Leggi ValoreCercato

Trovato ← Falso Indice ← 0

Finché Indice < N E Non Trovato { ValoreScheda ← Schede[Indice]

Se ValoreScheda = ValoreCercato Trovato ← Vero

Altrimenti

Indice ← Indice + 1 }

Se Trovato Scrivi "La posizione è " + Indice

(3)

Ricerca binaria

// Schede: ordinate e numerate da 0 a N-1 Leggi ValoreCercato

Primo ← 0 ; Ultimo ← N – 1 ; Trovato ← Falso Finché Primo ≤ Ultimo E Non Trovato {

Medio ← (Primo+Ultimo)/2 ; X ← Schede[Medio]

Se X > ValoreCercato { Ultimo ← Medio - 1

} Altrimenti Se X < ValoreCercato { Primo ← Medio + 1

} Altrimenti { Trovato ← Vero }

} Se Trovato Scrivi "La posizione è " + Medio

Altrimenti Scrivi "Valore non trovato"

(4)

Costo di un algoritmo

Spazio, memoria richiesta

Tempo, necessario all'esecuzione

Di solito si contano i cicli, in funzione di n O i confronti/scambi tra elementi dell'array

– Array in memoria centrale, accesso lento

– Altre variabili nei registri del processore

Test e misure empiriche

(5)

Confronto tra algoritmi

Caso peggiore negli algoritmi di ricerca: elemento non presente

Ricerca lineare: n confronti

Ricerca binaria:  ^log

₂

⁽ⁿ⁾  ^confronti

– A ogni iterazione l'insieme è dimezzato

– Il numero di iterazioni è pari a quante volte un numero n può essere diviso per 2

fino a ridurlo a 1

– 2

^k

≥ n → k ≥ log

₂

n

(6)

Def. di complessità

Una funzione f(n) ha ordine O(g(n)) sse:

– Esistono due costanti positive c e m tali che |f(n)| ≤ c|g(n)| per ogni n > m

Un algoritmo ha una complessità O(g(n)) sse:

– Il tempo di calcolo t(n), sufficiente per eseguire l'algoritmo con ogni istanza di dimensione n, ha ordine O(g(n))*

– (*) Insieme di dati su cui è definito il problema

– (*) Quindi conta il caso peggiore

(7)

Analisi asintotica

Per n abbastanza grande, a meno di una costante moltiplicativa, f(n) non supera in modulo g(n)

Comportamento dell'algoritmo al limite, per dimensione delle istanze tendente all'infinito Es. n = 1 000 000

– Ricerca lineare:

1 000 000 cicli

– Ricerca binaria:

20 cicli

e

^x

x

²

x·log(x) x

√x

log(x)

(8)

Complessità intrinseca

Limite inferiore di complessità di un problema Una funzione f(n) è Ω(g(n)) sse

– Esistono due costanti positive c e m tali che

|f(n)| ≥ c|g(n)| per ogni n > m

Un problema ha una delimitazione inferiore alla complessità Ω(g(n)) sse

– Per ogni algoritmo risolutivo…

∃ una istanza (caso peggiore)…

per cui il tempo di calcolo t(n) è Ω(g(n))

(9)

Algoritmo ottimale

Algoritmo che risolve un problema P, con le due seguenti condizioni:

– Costo di esecuzione O(g(n))

– P ha una delimitazione inferiore Ω(g(n))

Es. L'algoritmo della ricerca binaria è ottimale

– Si può dimostrare che log

₂

(n) è la minima complessità possibile per la ricerca

– Ma ricerca lineare funziona anche per liste non ordinate!

(10)

Algoritmi di ordinamento

La ricerca binaria dimostra l'importanza di avere dati ordinati

– Ordinateur, ordenador

Algoritmi più semplici hanno complessità n

²

– Confronto tra ciascun elemento e gli altri

Algoritmi divide et impera

– Complessità n·log

₂

(n)

– Complessità instrinseca

(11)

Bubble sort

// Schede: N schede, numerate da 0 a N-1 Ultimo ← N – 1

Finché Ultimo > 0 { I ← 0

Finché I < Ultimo {

Se Schede[I] > Schede[I + 1] { Scambia(I, I + 1)

} I ← I + 1 }

Ultimo ← Ultimo – 1 }

B B C C A A

^F^F ^D^D

E E G G H H

Confronti e scambi Confronti e scambi

Nel primo ciclo, il valore maggiore

sale fino in cima Nel primo ciclo, il valore maggiore

sale fino in cima

(12)

Analisi Bubble Sort

Gli elementi maggiori salgono rapidamente

“come bollicine di champagne”

Caso peggiore: lista rovesciata

– Numero di confronti e scambi: n

²

/2

– (n-1)+(n-2)+...+2+1 = n(n-1)/2 = n

²

/2 - n/2 ≈ n

²

/2

– Complessità n

²

Anche in media, circa stessi valori

(13)

Selection sort

// Schede: N schede, numerate da 0 a N-1 I ← 0

Finché I < N - 1 { PosMin ← I

J ← I + 1

Finché J < N {

Se Schede[J] < Schede[PosMin] { PosMin ← J

}

J ← J + 1

} Scambia(PosMin, I) I ← I + 1

}

A A B B C C E E G G F F H H

Sx: parte ordinata

Sx: parte ordinata Dx: parte da ordinareDx: parte da ordinare DD

Si cerca a dx il valore

minimo Si cerca a dx

il valore minimo

(14)

Analisi Selection Sort

Ad ogni ciclo principale, si seleziona il valore minore Caso peggiore: lista rovesciata

– Numero di confronti n·(n-1)/2; complessità n

²

– Numero di scambi: n-1 scambi

Anche in media, circa stessi valori

(15)

Insertion sort

// Schede: N schede, numerate da 0 a N - 1 I ← 1

Finché I < N {

Valore ← Schede[I]

J ← I – 1

Finché J ≥ 0 E Schede[J] > Valore { Schede[J + 1] ← Schede[J]

J ← J – 1 }

Schede[J + 1] ← Valore I ← I + 1

}

A A D D G G C C B B F F H H

Sx: parte ordinata

Sx: parte ordinata Dx: parte da ordinareDx: parte da ordinare EE

Si cerca a sx il posto per il primo val a dx Si cerca a sx il posto per il primo val a dx

(16)

Analisi Insertion Sort

La prima parte è ordinata, vi si inserisce un elemento alla volta, più facile trovare il posto

– In media si scorre solo 1/2 della prima parte

Caso peggiore: lista rovesciata

– Cicli: 1+2+...+(n-1) = n·(n-1)/2; compl: O(n

²

)

In media n

²

/4 confronti e n

²

/4 scambi Ottimizzazioni

– Ricerca binaria in parte ordinata, ma scambi

(17)

Quick Sort

// N schede, ordinare quelle tra Prima e Ultima Se Prima < Ultima {

Pivot ← Schede[Ultima]

J ← Prima; I ← Prima Finché I < Ultima {

Se Schede[I] ≤ Pivot { Scambia(I, J)

J ← J + 1 }

I ← I + 1

} Scambia(Ultima, J)

QuickSort(Prima, J - 1) QuickSort(J + 1, Ultima) }

Prima di J:

valori minori di pivot Prima di J: valori minori

di pivot

I scorre tutte le schede

tranne l'ultima (pivot) I scorre tutte le schede

tranne l'ultima (pivot)

C C A A B B G G E E F F H H

Val ≤ Pivot

Val ≤ Pivot Val > PivotVal > Pivot DD

H H C C G G A A B B E E F F D D

Pivot Pivot

(18)

Analisi Quick Sort

Dato un insieme, sceglie un valore pivot Crea due sottoinsiemi: x ≤ pivot, x > pivot Stesso algoritmo sui 2 insiemi (ricorsione)

Caso peggiore: lista rovesciata, n

²

– Dipende da scelta pivot, ma esiste sempre

Caso medio: n·log

₂

(n)

– t(n) = α·n + 2·t(n/2)

(19)

Merge Sort

// N schede, ordinare quelle tra Prima e Ultima Se Prima < Ultima {

Media ← (Prima + Ultima) / 2 MergeSort(Prima, Media)

MergeSort(Media + 1, Ultima) Merge(Prima, Media, Ultima) }

D D G G H H C C E E F F

AA BB

Merge: O(n) Confronti sempre tra

primi valori Merge: O(n) Confronti sempre tra

primi valori Ad ogni passo

la lista viene divisa nel mezzo Ad ogni passo la lista viene divisa

nel mezzo

G G D D A A H H E E F F C C B B G G D D A A H H E E F F C C B B G G D D A A H H E E F F C C B B G G D D A A H H E E F F C C B B

Costo ∝ n

Costo ∝ 2·n/2

Costo ∝ 4·n/4

(20)

Michele Tomaiuolo Fondamentidi informatica Complessità

Complessità

Fondamenti di informatica

Michele Tomaiuolo

tomamic@ce.unipr.it

http://www.ce.unipr.it/people/tomamic

Ricerca lineare

// Schede: ordinate e numerate da 0 a N-1 Leggi ValoreCercato

Trovato ← Falso Indice ← 0

Finché Indice < N E Non Trovato { ValoreScheda ← Schede[Indice]

Se ValoreScheda = ValoreCercato Trovato ← Vero

Altrimenti

Indice ← Indice + 1 }

Se Trovato Scrivi "La posizione è " + Indice

Ricerca binaria

// Schede: ordinate e numerate da 0 a N-1 Leggi ValoreCercato

Primo ← 0 ; Ultimo ← N – 1 ; Trovato ← Falso Finché Primo ≤ Ultimo E Non Trovato {

Medio ← (Primo+Ultimo)/2 ; X ← Schede[Medio]

Se X > ValoreCercato { Ultimo ← Medio - 1

} Altrimenti Se X < ValoreCercato { Primo ← Medio + 1

} Altrimenti { Trovato ← Vero }

} Se Trovato Scrivi "La posizione è " + Medio

Altrimenti Scrivi "Valore non trovato"

Costo di un algoritmo

Spazio, memoria richiesta

Tempo, necessario all'esecuzione

Di solito si contano i cicli, in funzione di n O i confronti/scambi tra elementi dell'array

– Array in memoria centrale, accesso lento

– Altre variabili nei registri del processore

Test e misure empiriche

Confronto tra algoritmi

Caso peggiore negli algoritmi di ricerca: elemento non presente

Ricerca lineare: n confronti

Ricerca binaria:  log

(n)  confronti

– A ogni iterazione l'insieme è dimezzato

– Il numero di iterazioni è pari a quante volte un numero n può essere diviso per 2

fino a ridurlo a 1

– 2

≥ n → k ≥ log

n

Def. di complessità

Una funzione f(n) ha ordine O(g(n)) sse:

– Esistono due costanti positive c e m tali che |f(n)| ≤ c|g(n)| per ogni n > m

Un algoritmo ha una complessità O(g(n)) sse:

– Il tempo di calcolo t(n), sufficiente per eseguire l'algoritmo con ogni istanza* di dimensione n, ha ordine O(g(n))

– (*) Insieme di dati su cui è definito il problema

– (*) Quindi conta il caso peggiore

Analisi asintotica

Per n abbastanza grande, a meno di una costante moltiplicativa, f(n) non supera in modulo g(n)

Comportamento dell'algoritmo al limite, per dimensione delle istanze tendente all'infinito Es. n = 1 000 000

– Ricerca lineare:

1 000 000 cicli

– Ricerca binaria:

20 cicli

e

x

x·log(x) x

√x

log(x)

Complessità intrinseca

Limite inferiore di complessità di un problema Una funzione f(n) è Ω(g(n)) sse

– Esistono due costanti positive c e m tali che

|f(n)| ≥ c|g(n)| per ogni n > m

Un problema ha una delimitazione inferiore alla complessità Ω(g(n)) sse

– Per ogni algoritmo risolutivo…

∃ una istanza (caso peggiore)…

per cui il tempo di calcolo t(n) è Ω(g(n))

Algoritmo ottimale

Algoritmo che risolve un problema P, con le due seguenti condizioni:

– Costo di esecuzione O(g(n))

– P ha una delimitazione inferiore Ω(g(n))

Es. L'algoritmo della ricerca binaria è ottimale

– Si può dimostrare che log

(n) è la minima complessità possibile per la ricerca

– Ma ricerca lineare funziona anche per liste non ordinate!

Algoritmi di ordinamento

La ricerca binaria dimostra l'importanza di avere dati ordinati

– Ordinateur, ordenador

Algoritmi più semplici hanno complessità n

Ricerca binaria:  ^log

⁽ⁿ⁾  ^confronti

– Il tempo di calcolo t(n), sufficiente per eseguire l'algoritmo con ogni istanza di dimensione n, ha ordine O(g(n))*