O-grande

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).

Questa notazione è stata introdotta per la prima volta dal teorico dei numeri tedesco Paul Bachmann nel 1894^[1], 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^[2], 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.

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".

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 2ⁿ. 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

${\displaystyle T(n)\in O(n^{2})}$

e diremo che l'algoritmo ha una complessità in tempo dell'ordine di n².

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

${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2}}+O(x^{3})\qquad {\text{per }}x\to 0}$

esprime il fatto che la differenza ${\displaystyle e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)}$ è più piccola in valore assoluto di qualche costante positiva moltiplicata per ${\displaystyle |x|^{3}}$ quando ${\displaystyle x}$ è sufficientemente vicino a 0.

Si supponga che ${\displaystyle f(x)}$ e ${\displaystyle g(x)}$ siano due funzioni definite su qualche sottoinsieme dei numeri reali^[3]. Diciamo che

${\displaystyle f(x)\in O(g(x))}$ per ${\displaystyle x\to \infty }$

se e solo se

${\displaystyle \exists x_{0}\in \mathbb {R} ,c>0:|f(x)|\leq c|g(x)|,\quad \forall x>x_{0}.}$

La notazione può anche essere usata per descrivere il comportamento di ${\displaystyle f}$ nell'intorno di un numero reale ${\displaystyle a}$: diciamo che

${\displaystyle f(x)\in O(g(x))}$ per ${\displaystyle x\to a}$

se e solo se

${\displaystyle \exists \delta >0\;\exists c>0:|f(x)|\leq c|g(x)|{\text{ per }}|x-a|<\delta .}$

Se ${\displaystyle g(x)}$ è non nulla per valori di ${\displaystyle x}$ sufficientemente vicini ad ${\displaystyle a}$, entrambe queste definizioni possono essere unificate utilizzando il limite superiore:

${\displaystyle f(x)\in O(g(x)){\text{ per }}x\to a}$

se e solo se

${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

Nella matematica, i comportamenti asintotici tendenti a ${\displaystyle \infty }$ e ad ${\displaystyle a}$ sono entrambi considerati. Nella teoria della complessità computazionale, sono usati solamente quelli tendenti ad infinito; inoltre, sono considerate solo funzioni sempre positive, per cui il valore assoluto può essere omesso.

Si considerino i due polinomi

${\displaystyle f(x)=6x^{4}-2x^{3}+5,}$

${\displaystyle g(x)=x^{4}.}$

Allora

${\displaystyle f(x)\in O(g(x)){\text{ per }}x\rightarrow +\infty .}$

Dimostrazione:

Mostriamo che ${\displaystyle |f(x)|\leq C|g(x)|}$ per ogni ${\displaystyle x>1,}$ dove ${\displaystyle C}$ è una costante che determineremo più avanti.

Supponiamo ${\displaystyle x>1}$. Dalla disuguaglianza triangolare si ottiene che

${\displaystyle |f(x)|=|6x^{4}-2x^{3}+5|\leq |6x^{4}|+|-2x^{3}|+|5|=6x^{4}+2x^{3}+5.}$

Nell'ultimo passaggio, la sostituzione ${\displaystyle |-2x^{3}|=2x^{3}}$ è giustificata dal fatto che ${\displaystyle x>1>0.}$

Osserviamo che per ${\displaystyle x>1}$ valgono le disuguaglianze ${\displaystyle 1<x^{3}<x^{4}}$ e ${\displaystyle 5<5x^{4}}$. Da queste otteniamo che

${\displaystyle |f(x)|\leq 6x^{4}+2x^{4}+5x^{4}=13x^{4},}$

e quindi

${\displaystyle |f(x)|\leq 13|g(x)|.}$

Prendendo ${\displaystyle C=13}$ si ottiene la tesi.

L'affermazione "${\displaystyle f(x)}$ è dell'ordine di ${\displaystyle g(x)}$" è spesso scritta come "${\displaystyle f(x)=O(g(x))}$". Questo è un abuso di notazione: non stiamo realmente affermando l'uguaglianza fra due funzioni, in quanto ${\displaystyle O(g(x))}$ non rappresenta una singola funzione ma una classe di funzioni. Sarebbe più corretto scrivere "${\displaystyle f(x)\in O(g(x))}$", come visto in precedenza.

A volte si scrive anche "${\displaystyle O(f(x))=O(g(x))}$" per indicare che ${\displaystyle O(f(x))\subseteq O(g(x))}$. Anche questo è un abuso di notazione: quella indicata nella prima espressione non è una vera uguaglianza, in quanto non è simmetrica. Per esempio, con questa notazione abbiamo

${\displaystyle O(x)=O(x^{2})\quad {\text{ per }}x\rightarrow +\infty ,}$

ma

${\displaystyle O(x^{2})\neq O(x)\quad {\text{ per }}x\rightarrow +\infty ,}$

in quanto la funzione ${\displaystyle f(x)=x^{2}}$ è ${\displaystyle O(x^{2})}$ ma non ${\displaystyle O(x)}$ per ${\displaystyle x}$ che tende a infinito.

In un uso più complesso, ${\displaystyle O(\cdot )}$ può apparire in posti diversi di una equazione, anche più volte in ciascun membro. Per esempio, le seguenti affermazioni sono vere per ${\displaystyle n\to \infty }$

${\displaystyle (n+1)^{2}=n^{2}+O(n)}$

${\displaystyle (n+O(n^{1/2}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2})}$

${\displaystyle n^{O(1)}=O(e^{n}).}$

Il significato di queste affermazioni è il seguente: per una qualsiasi funzione che soddisfa ciascuno degli O-grande del membro sinistro, esiste qualche funzione che soddisfa ciascuno degli O-grande presenti nel membro destro, in maniera che sostituendo queste funzioni nell'equazione rende i membri uguali. Per esempio, la terza equazione significa: "Per ogni funzione f(n)∈O(1)" c'è una qualche funzione g(n)∈O(eⁿ) tale che n^f(n)=g(n)." In termini di insiemi, il significato è che la classe di funzioni rappresentata dal membro sinistro è un sottoinsieme della classe di funzioni rappresentata dal membro destro.

Segue una lista di classi di funzioni comunemente incontrate nell'analisi di algoritmi. Tutte queste vanno considerate per ${\displaystyle n}$ che tende all'infinito. Le funzioni sono elencate per magnitudine crescente (in termini insiemistici, ogni classe di funzioni elencata è un sovrainsieme delle precedenti). Nel seguito, ${\displaystyle c}$ indica una costante arbitraria.

Notazione	Nome	Esempio
${\displaystyle O(1)}$	costante	Determinare se un numero è pari o dispari
${\displaystyle O(\log ^{*}(n))}$	logaritmica iterata	L'algoritmo di ricerca di Hopcroft e Ullman su un insieme disgiunto (un tipo di struttura dati)
${\displaystyle O(\log(n))}$	logaritmica	Cercare un elemento in una lista ordinata tramite l'algoritmo della ricerca binaria
${\displaystyle O((\log(n))^{c})}$	polilogaritmica	Decidere se ${\displaystyle n}$ è primo tramite il test AKS di primalità
${\displaystyle O(n)}$	lineare	Cercare un elemento in una lista non ordinata
${\displaystyle O(n\log(n))}$	loglineare	Ordinare una lista tramite heap sort
${\displaystyle O(n^{2})}$	quadratica	Ordinare una lista tramite insertion sort
${\displaystyle O(n^{c})}$	polinomiale	Cercare il cammino più breve su di un grafo orientato e pesato tramite l'algoritmo di Floyd-Warshall
${\displaystyle O(c^{n})}$	esponenziale, alcune volte chiamata geometrica	Trovare la soluzione esatta al problema del commesso viaggiatore (sotto l'ipotesi che P ≠ NP)
${\displaystyle O(n!)}$	fattoriale	Un qualsiasi problema NP-completo tramite un algoritmo che cerca la soluzione con un metodo forza bruta

O-grande è la notazione asintotica più comunemente usata per confrontare le funzioni. Insieme ad altre notazioni correlate forma la famiglia delle notazioni di Bachmann – Landau.

Intuitivamente, l'affermazione "${\displaystyle f(x)}$ è ${\displaystyle o(g(x))}$" (letto "${\displaystyle f(x)}$ è o-piccolo di ${\displaystyle g(x)}$") significa che ${\displaystyle g(x)}$ cresce molto più velocemente di ${\displaystyle f(x).}$ Sia ${\displaystyle f}$ una funzione a valori reali o complessi e ${\displaystyle g}$ una funzione a valori reali, entrambe definite su un sottoinsieme illimitato dei numeri reali positivi, in modo che ${\displaystyle g(x)}$ sia strettamente positiva per tutti i valori abbastanza grandi di ${\displaystyle x.}$ Scriviamo

${\displaystyle f(x)=o(g(x)){\text{ per }}x\to \infty }$

se per ogni ${\displaystyle \varepsilon }$ reale positivo esiste ${\displaystyle N}$ tale che

${\displaystyle |f(x)|\leq \varepsilon g(x),\quad {\text{ per ogni }}x\geq N.}$^[4]

Ad esempio, otteniamo

${\displaystyle 2x=o(x^{2})}$

e

${\displaystyle 1/x=o(1).}$

La differenza tra la precedente definizione per la notazione O-grande e questa definizione di o-piccolo, è che mentre la prima deve essere vera per almeno una costante ${\displaystyle M,}$ la seconda deve valere per ogni costante positiva ${\displaystyle \varepsilon ,}$ per quanto piccola^[5]. In questo modo, la notazione o-piccolo è "più forte" della corrispondente notazione O-grande: ogni funzione che è o-piccolo di ${\displaystyle g}$ è anche O-grande di ${\displaystyle g,}$ ma non tutte le funzioni che sono O-grande di ${\displaystyle g}$ sono o-piccolo di ${\displaystyle g.}$ Ad esempio, ${\displaystyle 2x^{2}=O(x^{2})}$ ma ${\displaystyle 2x^{2}\neq o(x^{2}).}$

Se ${\displaystyle g(x)}$ è diverso da zero, o almeno diventa diverso da zero da un certo punto in poi, la relazione ${\displaystyle f(x)=o(g(x))}$ è equivalente a

${\displaystyle \lim _{x\to +\infty }{\frac {f(x)}{g(x)}}=0,}$

che è il modo in cui Landau^[4] ha originariamente definito la notazione o-piccolo.

La notazione o-piccolo soddisfa le seguenti proprietà:

• se ${\displaystyle c}$ è una costante diversa da zero e ${\displaystyle f=o(g),}$ allora ${\displaystyle c\cdot f=o(g);}$

• se ${\displaystyle f=o(F)}$ e ${\displaystyle g=o(G),}$ allora ${\displaystyle f\cdot g=o(F\cdot G);}$

• se ${\displaystyle f=o(g)}$ e ${\displaystyle g=o(h),}$ allora ${\displaystyle f=o(h),}$ cioè ${\displaystyle o(o(h))=o(h).}$

• Stima asintotica

• O grande, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Big-O Notation, su MathWorld, Wolfram Research.

V · D · M Analisi matematica
Calcolo infinitesimale	Numero reale · Infinitesimo · O-grande · Successione (di funzioni) · Successione di Cauchy · Teorema di Bolzano-Weierstrass · Stima asintotica · Limite (di una funzione · di una successione · Forma indeterminata) · Teorema dei due carabinieri · Limite notevole · Punto di accumulazione · Punto isolato · Intorno · Serie (di funzioni) · Criteri di convergenza · Limite di funzioni a più variabili
Studio della continuità	Funzione continua · Punto di discontinuità · Continuità uniforme · Funzione lipschitziana · Teorema di Bolzano · Teorema di Weierstrass · Teorema dei valori intermedi · Teorema di Heine-Cantor · Modulo di continuità · Funzione semicontinua · Continuità separata · Teorema di approssimazione di Weierstrass
Calcolo differenziale	Derivata · Differenziale · Regole di derivazione · Teorema di Fermat · Teorema di Rolle · Teorema di Lagrange · Teorema di Cauchy · Teorema di Darboux · Teorema di Taylor · Serie di Taylor · Funzione differenziabile · Gradiente · Jacobiana · Hessiana · Forma differenziale · Generalizzazioni della derivata · Derivata parziale · Derivata mista
Integrale	Primitiva · Integrale di Riemann · Integrale improprio · Integrale di Lebesgue · Teorema fondamentale · Metodi di integrazione · Tavole · Integrale multiplo, di linea (1ª specie · 2ª specie) e di superficie (di volume)
Studio di funzione	Funzione · Variabile · Dominio e codominio · Funzioni pari e dispari · Funzione periodica · Funzione monotona · Funzione convessa · Massimo e minimo di una funzione · Punto angoloso · Cuspide · Punto di flesso · Asintoto · Grafico di una funzione · Funzione iniettiva
Disuguaglianze	Disuguaglianza triangolare · Disuguaglianza di Cauchy-Schwarz · Bernoulli · Jensen · Hölder · Young · Minkowski
Altro	Approssimazione di Stirling · Prodotto di Wallis · Funzione Gamma · Teorema delle funzioni implicite · Teorema della funzione inversa · Funzione hölderiana · Spazio metrico · Spazio normato · Intervallo · Insieme trascurabile · Insieme chiuso · Insieme aperto · Palla · Omeomorfismo · Omeomorfismo locale · Diffeomorfismo · Diffeomorfismo locale · Classe C di una funzione · Equazione differenziale · Problema di Cauchy

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort