O-grande

0
25

Jump to navigation
Jump to search

Esempio di notazione O-grande: f(x) ∈ O(g(x)), esistono c>0 e un valore x0 tale che a destra di x0 si abbia f(x) < c g(x)

La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro. Più precisamente, è usata per descrivere un limite asintotico superiore per la magnitudine di una funzione rispetto ad un’altra, che solitamente ha una forma più semplice.
Ha due aree principali di applicazione: in matematica, è solitamente usata per caratterizzare il resto del troncamento di una serie infinita, in particolare di una serie asintotica, mentre in informatica risulta utile nell’analisi della complessità degli algoritmi.

Nell’uso informale, la notazione O è comunemente impiegata per descrivere un limite asintotico stretto, ma i limiti asintotici stretti sono più formalmente e propriamente denotati dalla lettera Θ (Theta grande), come descritto in seguito.

Storia

Questa notazione è stata introdotta per la prima volta dal teorico dei numeri tedesco Paul Bachmann nel 1894, nel secondo volume del libro Analytische Zahlentheorie (“Teoria analitica dei numeri”), il cui primo volume (che ancora non conteneva la notazione O-grande) uscì nel 1892. La notazione divenne popolare grazie al lavoro di un altro teorico dei numeri tedesco, Edmund Landau, ragione per cui oggi è alcune volte chiamata simbolo di Landau. La O-grande, che sta per “dell’ordine di”, era in origine una omicron maiuscola; oggi è anche usata la lettera maiuscola O, ma mai la cifra zero.

Uso

Ci sono due utilizzi per questa notazione, che sono formalmente vicini ma chiaramente differenti: asintoti infiniti e asintoti infinitesimali. Questa distinzione è solo applicativa e non di principio. Tuttavia, la definizione formale di “O-grande” è la stessa in entrambi i casi, con la sola differenza del valore a cui tende il limite della funzione a cui si intende applicare la “O-grande”.

Comportamento asintotico all’infinito

La notazione O-grande risulta utile nell’analisi dell’efficienza degli algoritmi. Per esempio, supponiamo di aver ricavato che il tempo (o il numero di passi) che sono necessari a completare un problema di dimensione n sia T(n) = 4n² – 2n + 2.

Per grandi valori di n, il termine n² diventerà preponderante rispetto agli altri, che potranno non essere considerati; per esempio, per n pari a 500, il termine 4n² sarà pari a 1000 volte il termine 2n, e l’ignorare quest’ultimo sarà, nella maggior parte dei casi, un’approssimazione tollerabile.

Inoltre, anche i coefficienti diventano irrilevanti se compariamo l’espressione precedente ad una di ordine superiore, come una contenente un termine n³ oppure 2n. Se anche T(n) = 1.000.000n², se U(n) = n³, U(n) sarà comunque maggiore di T(n) per n maggiore di 1.000.000 (T(1.000.000) = 1.000.000³ = U(1.000.000)).

La notazione O-grande riesce ad esprimere proprio questo concetto: scriveremo

e diremo che l’algoritmo ha una complessità in tempo dell’ordine di n2.

O-grande e infinitesimi

La notazione O-grande può anche essere usata per descrivere il termine di errore in una approssimazione di una funzione. Per esempio,

esprime il fatto che la differenza





e

x




(

1
+
x
+



x

2


2



)



{\displaystyle e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)}

è più piccola in valore assoluto di qualche costante positiva moltiplicata per





|

x


|


3




{\displaystyle |x|^{3}}

quando x è sufficientemente vicino a 0.

Definizione formale

Si supponga che




f
(
x
)


{\displaystyle f(x)}

e




g
(
x
)


{\displaystyle g(x)}

siano due funzioni definite su qualche sottoinsieme dei numeri reali. Diciamo che

se e solo se

Let’s block ads! (Why?)

from My Reading List: Read and Unread https://ift.tt/2QHejJa
via IFTTT

LEAVE A REPLY

Please enter your comment!
Please enter your name here