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

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 Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Berlin 1909, p. 883., notación o pequeno):

ou (notación de Hardy, obsoleta)

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

Sexa 

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 , cando 

Se o contexto está claro, non especificamos o ámbito de estudo e denotamos como: , ou mesmo . 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  (ás veces tamén  ), o símbolo  lese como  o pequeno. A notación de Hardy equivalente é . 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:

  ;
  .

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

 Exemplos 



 Para calquera función , tal que , temos que: 

 Equivalencia 

 Definición formal 
Sexa .

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

 , cando  .

 Exemplo 

 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)



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



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



cando hai constantes  e  tal que



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

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



se existen constantes  e  tal que



Isto é equivalente, cando  non desaparece, a 

 Exemplos 



 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 .

 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 Ω  G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », Acta Mathematica, vol. 37, 1914, p. 225 definido como:

  .

Suponse que as funcións  e  están definidas, e  é  positiva, nun contorno do infinito. Entón  é a negación de .

En 1916, os mesmos autores presentaron os dous novos símbolos Ω e Ω  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., definidos como segue:

  ;

  .

Como antes, as funcións  e  suponse que están definidas, e  é positiva, nun contorno do infinito. Entón,  é a negación de , e  é a negación de .

Estes tres símbolos, a saber ,  E , utilízanse agora habitualmente na teoría analítica de números, como o son  para significar que se satisfán as dúas condicións  e .

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

 Exemplos 
Temos



e máis precisamente,



Temos



e máis precisamente,



porén,



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



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:



para expresar o feito de que o erro, a diferenza , é insignificante para  Cando  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  é 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()   (polilogarítmica se c é enteira positiva) O(n)   linear O(n log(n))  ás veces chamada «linearítmica» O()  ás veces chamada «cuasi linear»  O()   cadrática O()  (polinomial se c é enteira positiva) O()   (exponencial se c é positiva, ás veces chamada «xeométrica») O(n!)   factorial

O() e O() 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 nlog(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  
entón .
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: cando corresponde coa proposición :
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

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ónNomeDescrición informalCando , a partir dun certo rango...Definición rigurosaouO grande O  (Omicron grande)A función | | está limitada pola función || asintóticamente, dentro dun facrtor para un k > 0ouOmega grandeDúas definicións : 

En teoría  de números : non é desprezábel En teoría  de números:

 para un k > 0 e
para un conxunto de números En teoría  de números :En teoría de algoritmos : 

 esta minorizada por   (ata un factor) (ou f domina g)En teoría de algoritmos :

 para un k > 0 En teoría de algoritmos :ouda orde de Theta grandeAs funcións  e  son da mesma orde de tamaño asintótico para un k1 > 0, e un k2  > 0ouo pequeno  é desprezábel ante  asintóticamente, independentemente de  > 0 (fixado).Omega pequeno domina  asintóticamente para todo k > 0equivalent a é aproximativamente igual a  asintóticamente, independentemente de  > 0 (fixé).
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.

Categoría:Teoría de números
Categoría:Análise matemática
Categoría:Wikipedia:Páxinas con traducións non revisadas