Comparación asintótica

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^[1]. 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 ( c. 1930).

Exemplos de comparación

Preponderancia. Notación o pequeno.

Exemplo

Sexan $f$ e $g$ 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 $g$ toma valores tan grandes como queremos preto do infinito, mentres que $f$ só pode tomar valores entre 1 e 3. O cociente $g$ dividido por $f$ preto do infinito segue a aumentar e non está limitado. Neste contexto, podemos dicir que $f$ é desprezábel en comparación con $g$ , ou que $g$ é preponderante en comparación con $f$ , nas proximidades do infinito, escribimos (en notación de Landau^[2], 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 \mathbb {R} \cup \left\{+\infty ;-\infty \right\}.$

Sexan $f$ e $g$ dúas funcións da variábel real $x$ . Supoñemos que $g$ non desaparece nunha veciñanza de a. Dicimos que $f$ é desprezábel en comparación con $g$ , ou que $g$ é preponderante en comparación con $f$ en $a$ , 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 \mathbb {R} \cup \left\{+\infty ;-\infty \right\}$ .

Sexan $f$ e $g$ dúas funcións da variábel real $x$ . Supomos que $g$ non desaparece nunha proximidade de $a$ . Dicimos que $f$ é equivalente a $g$ en $a$ , ou que $g$ é equivalente a $f$ en $a$ , 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 Ordnung, "orde").

Definición formal

Sexan $f$ e $g$ dúas funcións da variábel real $x$ . Dicimos que $f$ está dominado por $g$ en $+\infty$ , ou que $g$ domina $f$ en $+\infty$ , 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 $N$ e $C$ tal que

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

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

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

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

se existen constantes $d > 0$ e $C$ tal que

\forall x\qquad \left|x-a\right|<d\Rightarrow \left|f(x)\right|\leq C\left|g(x)\right|.

Isto é equivalente, cando $g$ non desaparece, a $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$

Exemplos

$4x^{3}+10000x^{2}={\underset {x\to \infty }{O}}(x^{3}).$
$x^{3}={\underset {x\to \infty }{O}}(4x^{3}+10000x^{2}).$
Nun punto $a$ , se $f$ é desprezábel en comparación con $g$ ou equivalente a $g$ , entón está dominado por $g$ .
Unha función $f$ está limitada nunha veciñanza de $a$ 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 Ω ^[3] 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 $f$ e $g$ están definidas, e $g$ é 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 Ω_R e Ω_L ^[4], 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)}}<0

.

Como antes, as funcións $f$ e $g$ suponse que están definidas, e $g$ é positiva, nun contorno do infinito. Entón, $f(x)=\Omega _{R}(g(x))$ é a negación de $f(x)<o(g(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 $\infty$ por $-\infty$ 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 $+\infty$ e c é unha constante real arbitraria. Cando c é unha constante maior que 1, as funcións aparecen nesta lista en orde de magnitude ascendente.

notación		grande como moito
O(1)		módulo aumentado en unha constante
O(log(n))		logarítmica
O( $(\log n)^{c}$ )		(polilogarítmica se c é enteira positiva)
O(n)		linear
O(n log(n))		ás veces chamada «linearítmica»
O( $n\log ^{c}{(n)}$ )		ás veces chamada «cuasi linear»
O( $n^{2}$ )		cadrática
O( $n^{c}$ )		(polinomial se c é enteira positiva)
O( $c^{n}$ )		(exponencial se c é positiva, ás veces chamada «xeométrica»)
O(n!)		factorial

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^c)), 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:

A escrita:	$f(n,m)=n^{2}+m^{3}+O(n+m)\;$ cando $m,n\to +\infty$
corresponde coa proposición :	$\exists C\quad \exists N\quad \forall n,m>N\qquad \|f(n,m)-n^{2}-m^{3}\|\leq C(n+m)$

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, Ω, ω, Θ, ~

Notación	Nome	Descrición informal	Cando $n\to \infty$ , a partir dun certo rango...	Definición rigurosa
$f(n)=O(g(n))$ ou $f(n)\in O(g(n))$	O grande O (Omicron grande)	A función \| $f$ \| está limitada pola función \| $g$ \| asintóticamente, dentro dun facrtor	$\|f(n)\|\leq \|g(n)\|\cdot k$ para un k > 0	$\exists k>0,\exists n_{0}\;\forall n>n_{0}\;\|f(n)\|\leq \|g(n)\|\cdot k$
$f(n)=\Omega (g(n))$ ou $f(n)\in \Omega (g(n))$	Omega grande	Dúas definicións : En teoría de números : $f$ non é desprezábel ante $g$	En teoría de números: $\|f(n_{i})\|\geq \|g(n_{i})\|\cdot k$ para un k > 0 e para un conxunto de números $n_{i}\rightarrow \infty$	En teoría de números : $\exists k>0,\forall n_{0}\;\exists n>n_{0}\;\|g(n)\|\cdot k\leq \|f(n)\|$
$f(n)=\Omega (g(n))$ ou $f(n)\in \Omega (g(n))$	Omega grande	En teoría de algoritmos : $f$ esta minorizada por $g$ (ata un factor) (ou f domina g)	En teoría de algoritmos : $\|f(n)\|\geq \|g(n)\|\cdot k$ para un k > 0	En teoría de algoritmos : $\exists k>0,\exists n_{0}\;\forall n>n_{0}\;\|g(n)\|\cdot k\leq \|f(n)\|$
$f(n)\asymp g(n)$ ou $f(n)\in \Theta (g(n))$	da orde de Theta grande	As funcións $f$ e $g$ son da mesma orde de tamaño asintótico	$\|g(n)\|\cdot k_{1}\leq \|f(n)\|\leq \|g(n)\|\cdot k_{2}$ para un k₁ > 0, e un k₂ > 0	$\exists k_{1},k_{2}>0,\exists n_{0}\;\forall n>n_{0}$ $\|g(n)\|\cdot k_{1}<\|f(n)\|<\|g(n)\|\cdot k_{2}$
$f(n)=o(g(n))$ ou $f(n)\in o(g(n))$	o pequeno	$f$ é desprezábel ante $g$ asintóticamente	$\|f(n)\|\leq \|g(n)\|\cdot \varepsilon$ , independentemente de $\varepsilon$ > 0 (fixado).	$\forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\|f(n)\|\leq \|g(n)\|\cdot \varepsilon$
$f(n)\in \omega (g(n))$	Omega pequeno	$f$ domina $g$ asintóticamente	$\|f(n)\|\geq \|g(n)\|\cdot k$ para todo k > 0	$\forall k>0\;\exists n_{0}\;\forall n>n_{0}\;\|g(n)\|\cdot k\leq \|f(n)\|$
$f(n)\sim g(n)\!$	equivalent a	$f$ é aproximativamente igual a $g$ asintóticamente	$\|f(n)-g(n)\|<\varepsilon \|g(n)\|$ , independentemente de $\varepsilon$ > 0 (fixé).	$\forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\|f(n)-g(n)\|<\varepsilon \|g(n)\|$

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

↑ algorithmique cours avec 957 exercices et 158 problemes.
↑ (en alemán) Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Berlin 1909, p. 883.
↑ (en inglés) G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », Acta Mathematica, vol. 37, 1914, p. 225
↑ (en inglés) G. H. Hardy et J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, vol. 41, 1916.

Véxase tamén

Outros artigos

Ligazóns externas

Big-O Cheat Sheet, un sitio que enumera unha clasificación de complexidades algorítmicas por dominio.

[1] algorithmique cours avec 957 exercices et 158 problemes.

[Landau-2] (en alemán) Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Berlin 1909, p. 883.

[HL-3] (en inglés) G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », Acta Mathematica, vol. 37, 1914, p. 225

[HL2-4] (en inglés) G. H. Hardy et J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, vol. 41, 1916.

[1]

[2]

[3]

[4]