Analisi asintotica 1

Analisi asintotica

Se si considerano tutte le costanti l’analisi può divenire eccessivamente complessa

In realtà interessa conoscere come varia il costo al variare della dimensione dell’input, a meno di costantio Motivo: il costo è comunque calcolato a meno di

costanti, per le ipotesi fatte circa il modello Un’analisi di questo tipo è detta asintotica L’analisi asintotica trascura i fattori costanti L’analisi asintotica è influenzata

dall’operazione dominante di un algoritmoo L'operazione eseguita "più frequentemente"

(concetto da chiarire)

Analisi asintotica 2

Analisi asintotica /2

f(n), g(n) funzioni non negative e non decrescenti, dagli interi ai reali

f(n) = O(g(n)) se esistono c > 0 reale e una costante intera n0 >= 1 tali che f(n) <= c·g(n), per n >= n0 (f cresce al più come g)

f(n) = Ω(g(n)) se esistono c > 0 reale e una costante intera n0 >= 1 tali che f(n) >= c·g(n), per n >= n0 (f cresce almeno come g)

f(n) = Θ(g(n)) se f(n) = O(g(n)) e f(n) = Ω(g(n)) (f cresce come g)

f(n) = o(g(n)) se limn f(n)/g(n) = 0 f(n) = ω(g(n)) se g(n) = o(f(n))

Analisi asintotica 3

Esempi

1. L’algoritmo arrayMax ha costo Θ(n)

2. f(n) = 3n2 + 10n = O(n2)per c = 4 e n0 >= 10, 3n2 + 10n

<= 4n2

3. f(n) = n2/2 – 3n = Θ(n2)per c1 = 1/14, c2 = 1/2, n0 >= 7:

c1n2 <= n2/2 – 3n <= c2n2

D.: Cosa significa O(1)?D.: Cosa significa O(1)?

0

200

400

600

800

1000

1200

1400

1600

1800

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

-50

0

50

100

150

200

250

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Analisi asintotica 4

Operazione dominante

Un’operazione di un algoritmo di costo f(n) si dice dominante se, per ogni n, essa viene eseguita, nel caso peggiore di input di dimensione n, un numero di volte d(n) che soddisfa:

f(n) < a·d(n) + bper opportune costanti reali a e b

Ex.: istruzione if (A[i] > currentMax) nell’algoritmo arrayMax(A, n)

Analisi asintotica 5

Analisi asintotica /3

Limiti dell’approccio "analisi asintotica di caso peggiore"o Le costanti nascoste possono essere

molto grandi: un algoritmo con costo 1050n è lineare ma potrebbe essere poco pratico

o Comportamento nel caso di istanze “piccole” (es. 3n contro n2)?

o Il caso peggiore potrebbe verificarsi raramente

Analisi asintotica 6

Analisi di Insertion SortAlgorithm insertionSort(A, n)

for (i=0; i<n; i++) {tmp=A[i];for (j=i; j>0 && tmp<A[j-1];

j--)A[j]=A[j-1];

A[j] = tmp;}return A;

Ordina in modo non-decrescenteInserisce l’elemento A[i] nella posizione corretta nel vettore ordinato A[0,…,i-1]Operazione dominante: una qualunque fra quelle eseguite nel for più internoD.: se la ricerca della posizione di A[i] in A[0,…,i-1] avvenisse con la ricerca binaria?

Ex: 5 4 3 2 1

i=0 5 4 3 2 1 0 confronti

i=1 4 5 3 2 1 1 confronto

i=2 3 4 5 2 1 2 confronti

i=3 2 3 4 5 1 3 confronti

i=4 1 2 3 4 5 4 confronti

Ex: 1 2 3 4 5 f(n) = n

)(2

)1()( 2

1

0

nOnn

infn

i

Analisi asintotica 7

Esempiclass esercizio {

public void Ex1(int n) {int a, i;for (i = 0; i < n; i++)

a = i;}public void Ex2(int n) {int a, i;for (i = 0; i < n * n; i++)

a = i;}public void Ex3(int n) {int a, i, j;for (i = 0; i < n; i++)

for (j = 0; j <= i; j++)a=i;

}}

Valutare la complessitàdei tre metodi

Complessità di Ex3: 1+ 2 + … + n = O(n2)

qual è la dimensione dell'input??

Analisi asintotica 8

Calcolo delle somme dei prefissi Dato un vettore di interi X[0....n-1], determinare le

componenti del vettore A[0...n-1] in modo tale che A[i]=X[0]+....+X[i-1] + X[i]. Due algoritmi:

Algorithm prefix1(X, n)for (i=0; i<n; i++) {

A[i]=0;for (j=0; j<=i; j+

+)A[i]=A[i]

+X[j];}return A;

Algorithm prefix2(X, n)A[0]=X[0];for (i=1; i<n; i++)

A[i]=A[i-1]+X[i];return A;O(n2)

O(n)