Informatica I - l'andamento asintotico delle prestazioni di un algoritmo

Teniamo presente che, nell’analisi delle prestazioni di un algoritmo, ci interessano le prestazioni

asintotico).

per valori elevati di n (andamento

ESEMPIO: se n vale 1000

2

1/2*n vale 500000

circa 1% del totale

9/2*n-5 vale 4495,

() ~

quindi diciamo che l'andamento asintotico dell’algoritmo in funzione di n è:

Facciamo un’ulteriore semplificazione.

Ci interessa soltanto valutare cosa succede al tempo d’esecuzione T(n) se n, ad esempio,

raddoppia quadruplica

Nel caso in esame il tempo di esecuzione

2

T(n) = 2 2 2

(2) 4*T(n)

T(2n) = = =

4

2 2 2

T(n) = cn

Si osserva che T(2n) = 4*T(n). Questo è vero in generale nel caso in cui .

Indipendentemente dal fatto che sia presente un fattore moltiplicativo 1/2, o qualsiasi altro

c.

fattore moltiplicativo

NOTAZIONE “O-GRANDE”

Si dice quindi che per ordinare un array con l’algoritmo di selezione si effettua un numero di

2

accessi che è dell’ordine di n .

Per esprimere sinteticamente questo concetto si usa la notazione O-grande e si dice che il numero

2

O(n ).

degli accessi è la

Dopo aver ottenuto una formula che esprime l’andamento temporale dell’algoritmo, si ottiene

notazione “O-grande” considerando soltanto il termine che si incrementa più rapidamente

all’aumentare di n, ignorando coefficienti costanti.

f(n)=O(g(n)) f non cresce più velocemente di g.

La notazione significa: 2 3

Ma è possibile che f cresca molto più lentamente (Esempio: f(n) = n + 5n – 3 è O(n ), ma è anche

10

O(n )).

Esistono ulteriori notazioni per descrivere il modo in cui una funzione cresce:

• f(n)=Ω(g(n)) f non cresce più lentamente di g

significa:

g(n) = O(f(n))

Ovvero

• f(n)=Θ(g(n)) f cresce con la stessa velocità di g

significa:

f(n) = O(g(n)) e f(n) = Ω(g(n))

Ovvero

esiste una costante C>0 tale che:

f(n) = O(g(n)) f(n)/g(n) < C

↔ definitivamente

f(n) = Ω(g(n)) f(n)/g(n) > C

↔ definitivamente

f(n) = Θ(g(n)) C < f(n)/g(n) < C

↔ definitivamente

1 2