Comparación asintótica

miniatura| Comparación asintótica de funcións utilizadas en informática, máis precisamente en algoritmos. Vemos por exemplo que a función exponencial (2^n) medra máis rápido que a función linear (n).

En matemáticas, máis precisamente na análise, **a comparación asintótica** é un método para estudar a velocidade de crecemento dunha función.

Por exemplo, a función exponencial medra máis rápido que unha función linear.

A comparación asintótica tamén nos permite estudar a velocidade de calquera función en relación a unha función considerada máis "sinxela". Esta é a miúdo escollida nunha escala de referencia, xeralmente contén polo menos algunhas das chamadas funcións elementais, en particular as sumas e produtos de polinomios, exponenciais e logaritmos. A comparación faise no infinito ou nas proximidades dun punto.

O concepto de comparación asintótica úsase en física e tamén  en informática, por exemplo para describir a complexidade de certos algoritmos. De feito, a comparación asintótica é interesante no infinito, porque nos interesa o comportamento dun algoritmo en datos arbitrariamente grandes. Este método de comparación tamén se usa na teoría analítica de números para avaliar finamente o erro cometido ao substituír unha función irregular, como a de contar números primos, por unha función da escala escollida.

O método foi introducido polo traballo de Paul du Bois-Reymond a partir de 1872; para facilitar os cálculos e a presentación dos resultados, desenvolvéronse varias notacións, en particular por Bachmann (1894), Landau (1909), Hardy (1910), Hardy e Littlewood (1914 e 1916) e Vinogradov (  1930).

## Exemplos de comparación 
### Preponderancia. Notación o pequeno. 
#### Exemplo 
Sexan  e  as funcións reais definidas polas fórmulas 
:f(x)=\cos(x)+2\text{ e }g(x)=x.

Ao estudar as dúas funcións, sabemos que  toma valores tan grandes como queremos preto do infinito, mentres que  só pode tomar valores entre 1 e 3. O cociente  dividido por  preto do infinito segue a aumentar e non está limitado. Neste contexto, podemos dicir que  é **desprezábel** en comparación con , ou que  é **preponderante** en comparación con , nas proximidades do infinito, escribimos (en notación de Landau, notación o pequeno):
:f(x) = o(g(x)) \ (x\rightarrow\infty) 
ou (notación de Hardy, obsoleta)
:f (x) \prec g(x)\ (x\rightarrow\infty).

#### Definición formal cando a función *g* non desaparece 
Para definir formalmente esta propiedade consideramos o comportamento do cociente \frac f g.

Sexa a \in\R\cup \left\{ +\infty ; -\infty \right\}.

Sexan  e  dúas funcións da variábel real . Supoñemos que  non desaparece nunha veciñanza de *a*. Dicimos que  é desprezábel en comparación con , ou que  é **preponderante** en comparación con  en , e denotamos como f(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x)), cando 
:\frac {f(x)} {g(x)} \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0.
Se o contexto está claro, non especificamos o ámbito de estudo e denotamos como:  f(x) = o (g(x)), ou mesmo f = o(g). Porén, a notación sempre está asociada a un lugar *a* e á veciñanza deste lugar: ser desprezábel é un **concepto local**.

Nesta notación de Landau f(x) = o(g(x)) (ás veces tamén f(x) \in o(g(x)) ), o símbolo o lese como  *o* *pequeno*. A notación de Hardy equivalente é f(x) \prec g(x). Hoxe, usamos exclusivamente a notación de Landau.

#### Propiedades 
Polo que pode parecer un abuso da linguaxe, realizamos operacións sobre o «o  pequeno» . De feito, podemos escribir:

* o(f) + o(f) = o(f) ;
* o(f) - o(f) = o(f) .

No lado esquerdo de cada fórmula os dous símbolos o(f) representan a priori diferentes funcións. A primeira fórmula lese como: "a suma de dúas funcións de orde o(f) tamén é unha función de orde o(f)".

#### Exemplos 
*  x^2 + 10000 = \underset{ \overset { x \rightarrow \infty } {} } {o} (x^3) 
*  x^n = \underset{ \overset { x \rightarrow +\infty } {} } {o} (e^x) 
* Para calquera función \varepsilon, tal que  \varepsilon (x) \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0 , temos que: \varepsilon (x) = \underset{ \overset { x \rightarrow a } {} } {o} (1)

### Equivalencia 
#### Definición formal 
Sexa a \in\R\cup \left\{ +\infty ; -\infty \right\}.

Sexan  e  dúas funcións da variábel real . Supomos que  non desaparece nunha proximidade de . Dicimos que  é equivalente a  en , ou que  é equivalente a  en , e denotámolo como

: f(x) \underset{ \overset { x \rightarrow a } {} } {\sim} g(x), cando  f(x) - g(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x))  .

#### Exemplo 
\cos x + x^{20} + \exp(x) \underset{ \overset { x \rightarrow \infty } {} } {\sim} \exp(x)

### Dominación. Notación O grande. 
A notación O grande de Landau denota o carácter **dominado** dunha función en relación a outra. Xeralmente, como Paul Bachmann que introduciu este símbolo en 1894, úsase a letra maiúscula O (do alemán ''*, "orde").

#### Definición formal 
Sexan  e  dúas funcións da variábel real . Dicimos que  está dominado por  en , ou que  domina  en , e denotámolo como (notación de Bachmann, 1894, ou de Landau, 1909)

: f(x)=O(g(x)) \ (x\rightarrow\infty),

ou (a notación de Hardy , 1910, obsoleta)

: \ f\preccurlyeq g, 

ou (notación de Vinogradov, década de 1930)

: f(x)\ll g(x) \ (x\rightarrow\infty),

cando hai constantes  e  tal que

: \forall x>N\qquad \left|f(x)\right| \le C \left|g(x)\right|.

Intuitivamente, isto significa que  non medra máis rápido que .

Do mesmo xeito, se  é un número real, escribimos

: f(x)=\underset{x\to a}O(g(x))

se existen constantes  e  tal que

:  \forall x \qquad \left|x - a\right| 

Isto é equivalente, cando  non desaparece, a \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| 

#### Exemplos 
* 4x^3 + 10000 x^2=\underset{x\to\infty}O(x^3).
* x^3 =\underset{x\to\infty}O(4x^3+ 10000 x^2).
* Nun punto , se  é desprezábel en comparación con  ou equivalente a , entón está dominado por .
* Unha función  está limitada nunha veciñanza de  se e só se f(x)=\underset{x\to a}O(1).

## Ausencia de preponderancia e oscilacións 
### Notación Ω de Hardy e Littlewood (teoría dos números) 
En 1914, Hardy e Littlewood presentaron o novo símbolo Ω  definido como:

: f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0 .

Suponse que as funcións  e  están definidas, e  é  positiva, nun contorno do infinito. Entón f(x)=\Omega(g(x)) é a negación de f(x)=o(g(x)).

En 1916, os mesmos autores presentaron os dous novos símbolos Ω e Ω , definidos como segue:

: f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0 ;

: f(x)=\Omega_L(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\liminf_{x \to \infty} \frac{f(x)}{g(x)} .

Como antes, as funcións  e  suponse que están definidas, e  é positiva, nun contorno do infinito. Entón, f(x)=\Omega_R(g(x)) é a negación de f(x), e f(x)=\Omega_L(g(x)) é a negación de f(x)>o(g(x)).

Estes tres símbolos, a saber \Omega, \Omega_+ E \Omega_-, utilízanse agora habitualmente na teoría analítica de números, como o son f(x)=\Omega_\pm(g(x)) para significar que se satisfán as dúas condicións f(x)=\Omega_+(g(x)) e f(x)=\Omega_-(g(x)).

Está claro que en cada unha destas definicións podemos substituír  por  ou por un número real.

### Exemplos 
Temos

: \sin x=\Omega(1)\ (x\rightarrow\infty)

e máis precisamente,

: \sin x=\Omega_\pm(1)\ (x\rightarrow\infty).

Temos

: \sin x+1=\Omega(1)\ (x\rightarrow\infty)

e máis precisamente,

: \sin x+1=\Omega_+(1)\ (x\rightarrow\infty)~;

porén,

: \sin x+1\not=\Omega_-(1)\ (x\rightarrow\infty).

### Dúas definicións incompatíbeis 
É importante subliñar o feito de escribir

: f(x)=\Omega(g(x))\ (x\rightarrow\infty)

ten dúas definicións incompatíbeis en matemáticas, ambas as dúas moi estendidas, unha na teoría analítica de números, que acabamos de presentar, a outra na teoría da complexidade dos algoritmos. Cando estas dúas disciplinas se atopan, é probábel que esta situación cree unha grande confusión.

## Usando comparacións 
### Expansións limitadas 
En matemáticas, moitas veces é importante botar un ollo no termo de erro dunha aproximación. Esta notación úsase especialmente cando se trata de expansións limitadas e cálculos equivalentes. Por exemplo, a expansión da función exponencial de orde 2 tamén se pode escribir como:

:  e^x = 1+x+\frac{1}{2} x^2+o(x^2) \text{ cando } x \rightarrow 0

para expresar o feito de que o erro, a diferenza e^x - \left(1 + x +\frac{x^2}{2}\right), é insignificante para x^2 Cando x tende cara a 0.

Hai que ter en conta que o número de operandos neste tipo de escritura debe estar limitado por unha constante que non dependa da variábele: por exemplo a afirmación o(x)+o(x)+\dots+o(x)=o(x) é obviamente falso se as elipses ocultan un número de termos que non está limitado cando *x* varía.

### Escala de comparación 
Aquí temo unha lista de categorías de funcións que se usan habitualmente na análise. A variábel (denotada aquí como *n*) tende cara  e *c* é unha constante real arbitraria. Cando *c* é unha constante maior que 1, as funcións aparecen nesta lista en orde de magnitude ascendente.

O(n^c) e O(c^n) son moi diferentes. Este último permite un crecemento moito máis rápido, para calquera constante *c* > 1. Dise que unha función que medra máis rápido que calquera polinomio é *superpolinomial*. Unha función que medra máis lentamente que calquera exponencial dise que é *subexponencial*. Hai funcións que son superpolinomiais e subexponenciais, como a función *n*log(*n*).

Teña en conta tamén que O(log *n*) é exactamente o mesmo que O(log(*n*)), xa que estes dous logaritmos son múltiplos entre si por un factor constante e a notación O grande "ignora» constantes multiplicativas. Do mesmo xeito, os logaritmos en diferentes bases constantes son equivalentes.

A lista anterior é útil debido á seguinte propiedade: se unha función *f* é unha suma de funcións, e se unha das funcións da suma medra máis rápido que as outras, entón determina a orde de crecemento de *f*(*n*).

Exemplo:
: se f(n) = 10 \log(n) + 5 (log(n))^3 + 7n + 3n^2 + 6n^3 
:entón f(n) = O (n^3).
Que podemos ler como "efe de n é da orde de n ao cubo".

### Función de varias variábeis 
Esta notación tamén se pode usar con funcións de varias variábeis:

Para algúns, esta notación abusa do símbolo da igualdade, xa que parece violar o axioma da igualdade: "cousas iguais á mesma cousa son iguais entre si» (noutras palabras, con esta notación, a igualdade xa non é unha relación de equivalencia). Mais tamén podemos considerar que na escrita
:f(n,m) - n^2 - m^3 = O(n+m),
a notación "=O" designa un único operador, en cuxa escritura o signo "=" non ten existencia propia independente (e en particular non designa unha relación de equivalencia). Neste caso xa non hai ningún abuso de notación, pero obviamente aínda existe o risco de confusión.

## A familia de notacións Landau *O*, *o*, Ω, ω, Θ, *~'' 
Despois da notación O grande, as notacións Θ e Ω son as máis usadas en computación; a notación o pequeno é común en matemáticas pero máis rara en informática. O ω é pouco usado.

## Notas 
## Véxase tamén 
### Outros artigos 
* Desenvolvemento asintótico
* Función asintótica
*Analítica combinatoria
### Ligazóns externas 
* Big-O Cheat Sheet, un sitio que enumera unha clasificación de complexidades algorítmicas por dominio.