La notazione asintotica

In matematica la notazione asintotica consente di confrontare il tasso di crescita ( comportamento asintotico ) di una funzione nei confronti di un'altra.

In informatica il calcolo asintotico è utilizzato per analizzare la complessità di un algoritmo. In particolar modo, per stimare quanto aumenta il tempo al crescere della dimensione n dell'input.

Tipi di notazioni asintotiche

Esistono tre notazioni asintotiche:

  • Notazione asintotica O. La notazione O grande è il limite superiore asintotico
  • Notazione asintotica Ω. La notazione omega è il limite inferiore asintotico
  • Notazione asintotica θ. La notazione Theta è il limite asintotico stretto

La notazione asintotica O

La notazione asintotica O è il limite superiore asintotico.

Date due funzioni f(n) e g(n), si dice che f(n)=O(g(n)) se esiste un valore c>0 tale che 0≤f(n)≤c·g(n) per ogni n≥ n0.
la formula del limite asintotico superiore

Un esempio pratico

Se analizziamo il comportamento delle funzioni nel seguente grafico, a partire da n0 la f(x) è sempre più grande di c·g(n).

un esempio pratico di limito asintotico superiore O

Per questa ragione la notazione asintotica O è detta limite asintotico superiore.

In tali circostanze la f(n) è una delle funzioni dell'insieme O(g(n)).

La notazione f(n)=O(g(n)) si legge f(n) è "O grande" di g(n).

Nota. Va comuque specificato che la notazione precedente f(n)=O(g(n)) è un abuso di notazione, anche se è molto diffusa nei libri di testo. Sarebbe più corretto scrivere f(n)∈O(g(n)).
la notazione O corretta

In generale una funzione a1n2+a2n+a3 è sempre O(n2) se a1>0.

La notazione asintotica omega Ω

La notazione asintotica Ω è il limite asintotico inferiore.

Date due funzioni f(n) e g(n), si dice che f(n)=Ω(g(n)) se esiste un valore c>0 tale che 0≤c·g(n)≤f(n) per ogni n≥ n0.
la formula del limite asintotico inferiore

Un esempio pratico

Analizzando il comportamento delle funzioni nel seguente grafico, la f(n) è sempre più piccola di c·g(n) a partire da n0.

un esempio pratico di limite asintotico inferiore

Per questo motivo la notazione asintotica omega (Ω) è detta limite asintotico inferiore.

Quindi la f(n) è una delle funzioni dell'insieme Ω(g(n)).

La notazione f(n)=Ω(g(n)) si legge f(n) è "omega" di g(n).

La notazione asintotica theta θ

La notazione asintotica θ è il limite asintotico stretto.

Date due funzioni f(n) e g(n), si dice che f(n)=θ(g(n)) se esistono due valori c1>0 e c2>0 tali che 0≤c1·g(n)≤f(n)≤c2·g(n) per ogni n≥ n0.
la formula del limite asintotico inferiore

Un esempio pratico

Guardando il comportamento delle due funzioni nel seguente grafico, a partire da n0 la f(n) è sempre compresa tra c1·g(n) e c2·g(n).

un esempio pratico di limite asintotico stretto

Per questo motivo la notazione asintotica theta (θ) è detta limite asintotico stretto.

Quindi la f(n) è una delle funzioni dell'insieme θ(g(n)).

La notazione f(n)=θ(g(n)) si legge f(n) è "theta" di g(n).

Nota. Se una funzione è θ(g(n)) allora è anche O(g(n)) e Ω(g(n)) perché esiste sia un limite asintotico superiore che inferiore. E viceversa, se una funzione è sia O(g(n)) che Ω(g(n) allora è anche θ(g(n).
se una funzione appartiene a O e omega, allora appartiene anche a theta

In generale qualsiasi funzione polinomiale di grado k con coefficiente ak>0 appartiene all'insieme θ(nk).

la funzione polinomiale di grado k

Le proprietà del limite asintotico stretto

Nel caso del limite asintotico stretto valgono le seguenti proprietà

le proprietà del limite asintotico stretto

Come calcolare il limite asintotico

Per determinare i limiti asintotici di due funzioni f(n) e g(n) si utilizza il metodo del limite del rapporto f(n)/g(n).

  • Se il limite del rapporto f(n)/g(n) per n→∞ è zero, allora la funzione f(n) è O(g(n)).
    il limite asintotico superiore (O)
  • Se il limite del rapporto f(n)/g(n) per n→∞ è infinito, allora la funzione f(n) è omega Ω(g(n)).
    il limite asintotico omega
  • Se il limite del rapporto f(n)/g(n) per n→∞ tende a un numero finito k, allora la funzione f(n) è theta θ(g(n)).
    il limite asintotico stretto

Nota. Ovviamente, il metodo del limite è utilizzabile soltanto se esiste il limite del rapporto f(n)/g(n). Se non esiste, il limite asintotico non può essere definito con questo metodo.

Le proprietà dei limiti asintotici

La proprietà della transitività

Date tre funzioni f(n), g(n), h(n).

la proprietà della transitività dei limiti asintotici

La proprietà della riflessività

Data una funzione f(n)

la proprietà riflessiva dei limiti asintotici

La proprietà della simmetria

Date due funzioni f(n) e g(n)

la proprietà della simmetria dei limiti asintotici

La proprietà della simmetria trasposta

Date due funzioni f(n) e g(n)

la proprietà della simmetria trasposta

La differenza tra O grande e o piccola

Nella O grande è sufficiente che sia almeno un c>0 tale che 0≤f(n)≤cg(n) per ogni n>n0.

la differenza tra o grande e piccola

Nella o piccola, invece, per ogni c>0 esiste un n0>0 tale che 0≤f(n)≤cg(n).

Quindi, la o(g(n)) piccola implica la O(g(n)) grande.

La differenza tra omega grande (Ω) e omega piccola (ω)

Nella omega grande Ω è sufficiente che sia almeno un c>0 tale che 0≤cg(n)≤f(n) per ogni n>n0.

la differenza tra omega grande e piccola

Nella omega piccola ω, invece, per ogni c>0 esiste un n0>0 tale che 0≤cg(n)≤f(n).

Quindi, la ω(g(n)) piccola implica la Ω(g(n)) grande.


 
Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base