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.

Comparación asintótica de funcións utilizadas en informática, máis precisamente en algoritmos. Vemos por exemplo que a función exponencial (${\displaystyle 2^{n}}$) medra máis rápido que a función linear (${\displaystyle 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

${\displaystyle 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):

${\displaystyle f(x)=o(g(x))\ (x\rightarrow \infty )}$

ou (notación de Hardy, obsoleta)

${\displaystyle 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 ${\displaystyle {\frac {f}{g}}}$.

Sexa ${\displaystyle 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 ${\displaystyle f(x)={\underset {\overset {x\rightarrow a}{}}{o}}(g(x))}$, cando

${\displaystyle {\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: ${\displaystyle f(x)=o(g(x))}$, ou mesmo ${\displaystyle 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 ${\displaystyle f(x)=o(g(x))}$ (ás veces tamén ${\displaystyle f(x)\in o(g(x))}$ ), o símbolo ${\displaystyle o}$ lese como o pequeno. A notación de Hardy equivalente é ${\displaystyle 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:

• ${\displaystyle o(f)+o(f)=o(f)}$ ;
• ${\displaystyle o(f)-o(f)=o(f)}$ .

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

Exemplos

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

Equivalencia

Definición formal

Sexa ${\displaystyle 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

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

Exemplo

${\displaystyle \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 +∞, ou que g domina f en +∞, e denotámolo como (notación de Bachmann, 1894, ou de Landau, 1909)

${\displaystyle f(x)=O(g(x))\ (x\rightarrow \infty ),}$

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

${\displaystyle \ f\preccurlyeq g,}$

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

${\displaystyle f(x)\ll g(x)\ (x\rightarrow \infty ),}$

cando hai constantes N e C tal que

${\displaystyle \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

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

se existen constantes d > 0 e C tal que

${\displaystyle \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 ${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

Exemplos

• ${\displaystyle 4x^{3}+10000x^{2}={\underset {x\to \infty }{O}}(x^{3}).}$
• ${\displaystyle 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 ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle f(x)=\Omega (g(x))}$ é a negación de ${\displaystyle f(x)=o(g(x))}$.

En 1916, os mesmos autores presentaron os dous novos símbolos Ω_R e Ω_L ^[4], definidos como segue:

${\displaystyle f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0}$ ;

${\displaystyle 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, ${\displaystyle f(x)=\Omega _{R}(g(x))}$ é a negación de ${\displaystyle f(x)<o(g(x))}$, e ${\displaystyle f(x)=\Omega _{L}(g(x))}$ é a negación de ${\displaystyle f(x)>o(g(x))}$.

Estes tres símbolos, a saber ${\displaystyle \Omega }$, ${\displaystyle \Omega _{+}}$ E ${\displaystyle \Omega _{-}}$, utilízanse agora habitualmente na teoría analítica de números, como o son ${\displaystyle f(x)=\Omega _{\pm }(g(x))}$ para significar que se satisfán as dúas condicións ${\displaystyle f(x)=\Omega _{+}(g(x))}$ e ${\displaystyle 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

${\displaystyle \sin x=\Omega (1)\ (x\rightarrow \infty )}$

e máis precisamente,

${\displaystyle \sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).}$

Temos

${\displaystyle \sin x+1=\Omega (1)\ (x\rightarrow \infty )}$

e máis precisamente,

${\displaystyle \sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty )~;}$

porén,

${\displaystyle \sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).}$

Dúas definicións incompatíbeis

É importante subliñar o feito de escribir

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)}$, é insignificante para ${\displaystyle x^{2}}$ Cando ${\displaystyle 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 ${\displaystyle 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.

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

O(${\displaystyle n^{c}}$) e O(${\displaystyle 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 ${\displaystyle f(n)=10\log(n)+5(log(n))^{3}+7n+3n^{2}+6n^{3}}$

entón ${\displaystyle 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:	${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\;}$ cando ${\displaystyle m,n\to +\infty }$
corresponde coa proposición :	${\displaystyle \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

${\displaystyle 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 ${\displaystyle n\to \infty }$, a partir dun certo rango...	Definición rigurosa
${\displaystyle f(n)=O(g(n))}$ ou ${\displaystyle 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	${\displaystyle |f(n)|\leq |g(n)|\cdot k}$ para un k > 0	${\displaystyle \exists k>0,\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq |g(n)|\cdot k}$
${\displaystyle f(n)=\Omega (g(n))}$ ou ${\displaystyle 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: ${\displaystyle |f(n_{i})|\geq |g(n_{i})|\cdot k}$ para un k > 0 e para un conxunto de números ${\displaystyle n_{i}\rightarrow \infty }$	En teoría de números : ${\displaystyle \exists k>0,\forall n_{0}\;\exists n>n_{0}\;|g(n)|\cdot k\leq |f(n)|}$
		En teoría de algoritmos : f esta minorizada por g (ata un factor) (ou f domina g)	En teoría de algoritmos : ${\displaystyle |f(n)|\geq |g(n)|\cdot k}$ para un k > 0	En teoría de algoritmos : ${\displaystyle \exists k>0,\exists n_{0}\;\forall n>n_{0}\;|g(n)|\cdot k\leq |f(n)|}$
${\displaystyle f(n)\asymp g(n)}$ ou ${\displaystyle 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	${\displaystyle |g(n)|\cdot k_{1}\leq |f(n)|\leq |g(n)|\cdot k_{2}}$ para un k1 > 0, e un k2 > 0	${\displaystyle \exists k_{1},k_{2}>0,\exists n_{0}\;\forall n>n_{0}}$ ${\displaystyle |g(n)|\cdot k_{1}<|f(n)|<|g(n)|\cdot k_{2}}$
${\displaystyle f(n)=o(g(n))}$ ou ${\displaystyle f(n)\in o(g(n))}$	o pequeno	f é desprezábel ante g asintóticamente	${\displaystyle |f(n)|\leq |g(n)|\cdot \varepsilon }$, independentemente de ${\displaystyle \varepsilon }$ > 0 (fixado).	${\displaystyle \forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq |g(n)|\cdot \varepsilon }$
${\displaystyle f(n)\in \omega (g(n))}$	Omega pequeno	f domina g asintóticamente	${\displaystyle |f(n)|\geq |g(n)|\cdot k}$ para todo k > 0	${\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\;|g(n)|\cdot k\leq |f(n)|}$
${\displaystyle f(n)\sim g(n)\!}$	equivalent a	f é aproximativamente igual a g asintóticamente	${\displaystyle |f(n)-g(n)|<\varepsilon |g(n)|}$, independentemente de ${\displaystyle \varepsilon }$ > 0 (fixé).	${\displaystyle \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.