Notación O grande

Describe el comportamiento limitante de una función.

Ejemplo de notación O grande: como existe (por ejemplo, ) y (por ejemplo, ) tal que cuando sea . ${\displaystyle {\color {red}f(x)}=O{\color {blue}(g(x))}}$ ${\displaystyle x\to \infty }$ ${\displaystyle M>0}$ ${\displaystyle M=1}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}=5}$ ${\displaystyle 0\leq {\color {red}f(x)}\leq M{\color {blue}g(x)}}$ ${\displaystyle x\geq x_{0}}$

La notación O grande es una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor o infinito particular. Big O es miembro de una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann , ^[1] Edmund Landau , ^[2] y otros, denominadas colectivamente notación de Bachmann-Landau o notación asintótica . Bachmann eligió la letra O para representar Ordnung , es decir, el orden de aproximación .

En informática , la notación O grande se utiliza para clasificar algoritmos según cómo crecen sus requisitos de tiempo de ejecución o espacio a medida que crece el tamaño de entrada. ^[3] En teoría analítica de números , la notación O grande se utiliza a menudo para expresar un límite en la diferencia entre una función aritmética y una aproximación mejor entendida; un ejemplo famoso de tal diferencia es el término restante del teorema de los números primos . La notación O grande también se utiliza en muchos otros campos para proporcionar estimaciones similares.

La notación O grande caracteriza funciones según sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento asintótica se pueden representar usando la misma notación O. La letra O se utiliza porque la tasa de crecimiento de una función también se conoce como orden de la función . Una descripción de una función en términos de notación O grande generalmente solo proporciona un límite superior a la tasa de crecimiento de la función.

Asociadas con la notación O grande hay varias notaciones relacionadas, que utilizan los símbolos o , Ω, ω y Θ , para describir otros tipos de límites en las tasas de crecimiento asintótico.

Definicion formal

Sea , la función a estimar, una función con valor real o complejo y sea , la función de comparación, una función con valor real. Dejemos que ambas funciones se definan en algún subconjunto ilimitado de los números reales positivos y sean estrictamente positivas para todos los valores suficientemente grandes de . ^[4] Se escribe ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g(x)}$ ${\displaystyle x}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }$$

valor absoluto ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle x}$ ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle M}$ ${\displaystyle x_{0}}$

$${\displaystyle |f(x)|\leq Mg(x)\quad {\text{ for all }}x\geq x_{0}.}$$

${\displaystyle x}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}$$

${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle a=0}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a}$$

, ${\displaystyle \delta }$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle 0<|x-a|<\delta }$

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

límite superior ${\displaystyle g(x)}$ ${\displaystyle x}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a}$$

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

punto límitepunto de agrupaciónlímite inferior y el límite superiorrecta numérica real extendida ${\displaystyle a}$ ${\displaystyle \infty }$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle a}$ ${\displaystyle \textstyle \limsup _{x\to a}}$

En informática, es común una definición un poco más restrictiva: y ambos deben ser funciones de algún subconjunto ilimitado de números enteros positivos a números reales no negativos; entonces si existen números enteros positivos y tales que para todos . ^[5] ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle M}$ ${\displaystyle n_{0}}$ ${\displaystyle f(n)\leq Mg(n)}$ ${\displaystyle n\geq n_{0}}$

Ejemplo

En el uso típico, la notación O es asintótica, es decir, se refiere a x muy grande . En este contexto, la contribución de los términos que crecen "más rápidamente" eventualmente hará que los demás sean irrelevantes. Como resultado, se pueden aplicar las siguientes reglas de simplificación:

• Si f ( x ) es una suma de varios términos, si hay uno con la mayor tasa de crecimiento, se puede mantener y omitir todos los demás.
• Si f ( x ) es un producto de varios factores, se puede omitir cualquier constante (factores del producto que no dependen de x ).

Por ejemplo, sea f ( x ) = 6 x ⁴ − 2 x ³ + 5 , y supongamos que deseamos simplificar esta función, usando la notación O , para describir su tasa de crecimiento cuando x se acerca al infinito. Esta función es la suma de tres términos: 6 x ⁴ , −2 x ³ y 5 . De estos tres términos, el que tiene mayor tasa de crecimiento es el que tiene mayor exponente en función de x , es decir, 6 x ⁴ . Ahora se puede aplicar la segunda regla: 6 x ⁴ es un producto de 6 y x ⁴ en el que el primer factor no depende de x . Omitir este factor da como resultado la forma simplificada x ⁴ . Por tanto, decimos que f ( x ) es una "gran O" de x ⁴ . Matemáticamente, podemos escribir f ( x ) = O ( x ⁴ ) . Se puede confirmar este cálculo utilizando la definición formal: sea f ( x ) = 6 x ⁴ − 2 x ³ + 5 y g ( x ) = x ⁴ . Aplicando la definición formal anterior, la afirmación de que f ( x ) = O ( x ⁴ ) es equivalente a su expansión,

$${\displaystyle |f(x)|\leq Mx^{4}}$$

x ₀Mx > x ₀x ₀ = 1M = 13x > x ₀

$${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$

$${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$

Uso

La notación O grande tiene dos áreas principales de aplicación:

• En matemáticas , se usa comúnmente para describir qué tan cerca se aproxima una serie finita a una función dada, especialmente en el caso de una serie de Taylor truncada o una expansión asintótica .
• En informática , es útil en el análisis de algoritmos.

En ambas aplicaciones, la función g ( x ) que aparece dentro de O (·) normalmente se elige para que sea lo más simple posible, omitiendo factores constantes y términos de orden inferior.

Hay dos usos formalmente cercanos, pero notablemente diferentes, de esta notación: ^{[ cita necesaria ]}

• asintóticas infinitas
• asintóticas infinitesimales .

Sin embargo, esta distinción es sólo en la aplicación y no en principio: la definición formal de la "O grande" es la misma para ambos casos, solo que con límites diferentes para el argumento de la función. ^{[ ¿ investigacion original? ]}

Asintóticas infinitas

Gráficos de funciones comúnmente utilizadas en el análisis de algoritmos, que muestran el número de operaciones N frente al tamaño de entrada n para cada función.

La notación O grande es útil al analizar la eficiencia de algoritmos. Por ejemplo, el tiempo (o el número de pasos) que se necesita para completar un problema de tamaño n podría ser T ( n ) = 4 n ² − 2 n + 2 . A medida que n crece, el término n ² llegará a dominar, de modo que todos los demás términos pueden despreciarse; por ejemplo, cuando n = 500 , el término 4 n ² es 1000 veces más grande que el término 2 n . Ignorar esto último tendría un efecto insignificante en el valor de la expresión para la mayoría de los propósitos. Además, los coeficientes se vuelven irrelevantes si los comparamos con cualquier otro orden de expresión, como una expresión que contenga un término n ³ o n ⁴ . Incluso si T ( n ) = 1.000.000 n ² , si U ( n ) = n ³ , este último siempre excederá al primero una vez que n crezca más que 1.000.000 , es decir. T (1.000.000) = 1.000.000 ³ = U (1.000.000) . Además, la cantidad de pasos depende de los detalles del modelo de máquina en el que se ejecuta el algoritmo, pero los diferentes tipos de máquinas generalmente varían solo en un factor constante en la cantidad de pasos necesarios para ejecutar un algoritmo. Entonces, la notación O grande captura lo que queda: escribimos

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

o

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

y digamos que el algoritmo tiene un orden de complejidad temporal n ² . El signo " = " no pretende expresar "es igual a" en su sentido matemático normal, sino más bien un "es" más coloquial, por lo que la segunda expresión a veces se considera más precisa (consulte la discusión sobre el "signo igual" a continuación), mientras que el primero es considerado por algunos como un abuso de notación . ^[6]

Asintóticas infinitesimales

Big O también se puede utilizar para describir el término de error en una aproximación a una función matemática. Los términos más significativos se escriben explícitamente y luego los términos menos significativos se resumen en un único término O grande. Considere, por ejemplo, la serie exponencial y dos expresiones de ella que son válidas cuando x es pequeño:

${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}$

La expresión del medio (la que tiene O ( x ³ )) significa que el valor absoluto del error e ^x − (1 + x + x ² /2) es como máximo algunos tiempos constantes | x3 | ^_ cuando x está lo suficientemente cerca de 0.

Propiedades

Si la función f se puede escribir como una suma finita de otras funciones, entonces la que crece más rápido determina el orden de f ( n ) . Por ejemplo,

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .}$

En particular, si una función puede estar acotada por un polinomio en n , entonces como n tiende al infinito , se pueden ignorar los términos de orden inferior del polinomio. Los conjuntos O ( n ^c ) y O ( c ⁿ ) son muy diferentes. Si c es mayor que uno, entonces este último crece mucho más rápido. Una función que crece más rápido que n ^c para cualquier c se llama superpolinomio . Aquella que crece más lentamente que cualquier función exponencial de la forma c ⁿ se llama subexponencial . Un algoritmo puede requerir un tiempo que sea a la vez superpolinomial y subexponencial; ejemplos de esto incluyen los algoritmos más rápidos conocidos para la factorización de enteros y la función n ^{log n} .

Podemos ignorar cualquier potencia de n dentro de los logaritmos. El conjunto O (log n ) es exactamente igual que O (log( n ^c )) . Los logaritmos difieren sólo por un factor constante (ya que log( n ^c ) = c log n ) y por lo tanto la notación O grande ignora eso. De manera similar, los registros con diferentes bases constantes son equivalentes. Por otro lado, las exponenciales con diferentes bases no son del mismo orden. Por ejemplo, 2 ⁿ y 3 ⁿ no son del mismo orden.

El cambio de unidades puede afectar o no el orden del algoritmo resultante. Cambiar de unidad equivale a multiplicar la variable apropiada por una constante dondequiera que aparezca. Por ejemplo, si un algoritmo se ejecuta en el orden de n ² , reemplazar n por cn significa que el algoritmo se ejecuta en el orden de c ² n ² , y la notación O grande ignora la constante c ² . Esto se puede escribir como c ² n ² = O( n ² ) . Sin embargo, si un algoritmo se ejecuta en el orden de 2 ⁿ , reemplazar n con cn da 2 ^cn = (2 ^c ) ⁿ . Esto no es equivalente a 2 ⁿ en general. El cambio de variables también puede afectar el orden del algoritmo resultante. Por ejemplo, si el tiempo de ejecución de un algoritmo es O ( n ) cuando se mide en términos del número n de dígitos de un número de entrada x , entonces su tiempo de ejecución es O (log x ) cuando se mide como una función del número de entrada x mismo. , porque n = O (log x ) .

Producto

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}$

${\displaystyle f\cdot O(g)=O(fg)}$

Suma

Si y entonces . De ello se deduce que si y entonces . En otras palabras, esta segunda afirmación dice que es un cono convexo . ${\displaystyle f_{1}=O(g_{1})}$ ${\displaystyle f_{2}=O(g_{2})}$ ${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$ ${\displaystyle f_{1}=O(g)}$ ${\displaystyle f_{2}=O(g)}$ ${\displaystyle f_{1}+f_{2}\in O(g)}$ ${\displaystyle O(g)}$

Multiplicación por una constante

Sea k una constante distinta de cero. Entonces . En otras palabras, si , entonces ${\displaystyle O(|k|\cdot g)=O(g)}$ ${\displaystyle f=O(g)}$ ${\displaystyle k\cdot f=O(g).}$

Múltiples variables

La O grande (y la o pequeña, Ω, etc.) también se pueden utilizar con múltiples variables. Para definir formalmente O grande para múltiples variables, supongamos que y son dos funciones definidas en algún subconjunto de . Decimos ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty }$

si y sólo si existen constantes y tales que para todos con para algunos ^[7] De manera equivalente, la condición que para algunos se puede escribir , donde denota la norma de Chebyshev . Por ejemplo, la declaración ${\displaystyle M}$ ${\displaystyle C>0}$ ${\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle x_{i}\geq M}$ ${\displaystyle i.}$ ${\displaystyle x_{i}\geq M}$ ${\displaystyle i}$ ${\displaystyle \|\mathbf {x} \|_{\infty }\geq M}$ ${\displaystyle \|\mathbf {x} \|_{\infty }}$

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty }$

afirma que existen constantes C y M tales que

${\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}$

siempre que o se mantenga. Esta definición permite que todas las coordenadas de aumenten hasta el infinito. En particular, la declaración ${\displaystyle m\geq M}$ ${\displaystyle n\geq M}$ ${\displaystyle \mathbf {x} }$

${\displaystyle f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty }$

(es decir, ) es bastante diferente de ${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }$

${\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }$

(es decir, ). ${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }$

Según esta definición, el subconjunto en el que se define una función es importante al generalizar declaraciones del entorno univariado al entorno multivariado. Por ejemplo, si y , entonces si restringimos y a , pero no si están definidos en . ${\displaystyle f(n,m)=1}$ ${\displaystyle g(n,m)=n}$ ${\displaystyle f(n,m)=O(g(n,m))}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle [1,\infty )^{2}}$ ${\displaystyle [0,\infty )^{2}}$

Ésta no es la única generalización de O grande a funciones multivariadas y, en la práctica, existe cierta inconsistencia en la elección de la definición. ^[8]

Cuestiones de notación

Signo de igual

La afirmación " f ( x ) es O ( g ( x ))" como se define anteriormente generalmente se escribe como f ( x ) = O ( g ( x )) . Algunos consideran que esto es un abuso de notación , ya que el uso del signo igual podría inducir a error ya que sugiere una simetría que esta afirmación no tiene. Como dice de Bruijn , O ( x ) = O ( x ² ) es cierto pero O ( x ² ) = O ( x ) no lo es. ^[9] Knuth describe tales afirmaciones como "igualdades unidireccionales", ya que si los lados pudieran invertirse, "podríamos deducir cosas ridículas como n = n ² a partir de las identidades n = O ( n ² ) y n ² = O ( n ² ) ". ^[10] En otra carta, Knuth también señaló que "el signo de igualdad no es simétrico con respecto a tales notaciones", ya que, en esta notación, "los matemáticos suelen usar el signo = como usan la palabra "is" en inglés: Aristóteles es un hombre, pero un hombre no es necesariamente Aristóteles". ^[11]

Por estas razones, sería más preciso usar notación de conjuntos y escribir f ( x ) ∈ O ( g ( x )) (léase como: " f ( x ) es un elemento de O ( g ( x )) ", o " f ( x ) está en el conjunto O ( g ( x ))"), pensando en O ( g ( x )) como la clase de todas las funciones h ( x ) tales que | h ( x )| ≤  Cg ( x ) para algún número real positivo C . ^[10] Sin embargo, el uso del signo igual es habitual. ^{[9] [10]}

Otros operadores aritméticos

La notación O grande también se puede utilizar junto con otros operadores aritméticos en ecuaciones más complicadas. Por ejemplo, h ( x ) + O ( f ( x )) denota el conjunto de funciones que tienen el crecimiento de h ( x ) más una parte cuyo crecimiento se limita al de f ( x ). De este modo,

${\displaystyle g(x)=h(x)+O(f(x))}$

expresa lo mismo que

${\displaystyle g(x)-h(x)=O(f(x)).}$

Ejemplo

Supongamos que se está desarrollando un algoritmo para operar con un conjunto de n elementos. Sus desarrolladores están interesados ​​en encontrar una función T ( n ) que exprese cuánto tiempo tardará en ejecutarse el algoritmo (en alguna medida de tiempo arbitraria) en términos del número de elementos en el conjunto de entrada. El algoritmo funciona llamando primero a una subrutina para ordenar los elementos del conjunto y luego realizar sus propias operaciones. La clasificación tiene una complejidad temporal conocida de O ( n ^{2 ), y después de que se ejecuta la subrutina, el algoritmo debe tomar} 55 n ³ + 2 n + 10 pasos adicionales antes de terminar. Por lo tanto, la complejidad temporal general del algoritmo se puede expresar como T ( n ) = 55 n ³ + O ( n ² ) . Aquí los términos 2 n + 10 se incluyen dentro del O ( n ² ) de más rápido crecimiento. Nuevamente, este uso ignora parte del significado formal del símbolo "=", pero permite usar la notación O grande como una especie de marcador de posición conveniente.

Múltiples usos

En un uso más complicado, O (·) puede aparecer en diferentes lugares de una ecuación, incluso varias veces en cada lado. Por ejemplo, lo siguiente es cierto para : ${\displaystyle n\to \infty }$

$${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$

cualquierOalgunasOfnOgnOe ⁿn ^{f ( n )}gnrelación simétrican ^{O (1)} = O ( e ⁿ )O ( e ⁿ ) = n ^{O (1)}

Tipografía

La O grande se escribe como una "O" mayúscula en cursiva, como en el siguiente ejemplo: . ^{[12] [13]} En TeX , se produce simplemente escribiendo O dentro del modo matemático. A diferencia de las notaciones de Bachmann-Landau con nombre griego, no necesita ningún símbolo especial. Sin embargo, algunos autores utilizan en su lugar la variante caligráfica. ^{[14] [15]} ${\displaystyle O(n^{2})}$ ${\displaystyle {\mathcal {O}}}$

Órdenes de funciones comunes

A continuación se muestra una lista de clases de funciones que se encuentran comúnmente al analizar el tiempo de ejecución de un algoritmo. En cada caso, c es una constante positiva y n aumenta sin límite. Las funciones de crecimiento más lento generalmente se enumeran primero.

A veces, la afirmación se debilita para derivar fórmulas más simples para la complejidad asintótica. For any y , es un subconjunto de for any , por lo que puede considerarse como un polinomio con un orden mayor. ${\displaystyle f(n)=O(n!)}$ ${\displaystyle f(n)=O\left(n^{n}\right)}$ ${\displaystyle k>0}$ ${\displaystyle c>0}$ ${\displaystyle O(n^{c}(\log n)^{k})}$ ${\displaystyle O(n^{c+\varepsilon })}$ ${\displaystyle \varepsilon >0}$

Notaciones asintóticas relacionadas

Big O se usa ampliamente en informática. Junto con algunas otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau. ^{[ cita necesaria ]}

Notación pequeña o

Intuitivamente, la afirmación " f ( x ) es o ( g ( x )) " (léase " f ( x ) es pequeña-o de g ( x ) ") significa que g ( x ) crece mucho más rápido que f ( x ) . Como antes, sea f una función con valores reales o complejos y g una función con valores reales, ambas definidas en algún subconjunto ilimitado de los números reales positivos , de modo que g ( x ) sea estrictamente positivo para todos los valores suficientemente grandes de x . uno escribe

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

si para cada constante positiva ε existe una constante tal que ${\displaystyle x_{0}}$

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$^[dieciséis]

Por ejemplo, uno tiene

${\displaystyle 2x=o(x^{2})}$y     tanto como ${\displaystyle 1/x=o(1),}$ ${\displaystyle x\to \infty .}$

La diferencia entre la definición de la notación O grande y la definición de o pequeña es que mientras la primera tiene que ser cierta para al menos una constante M , la segunda debe ser válida para cada constante positiva ε , por pequeña que sea. ^[17] De esta manera, la notación o pequeña hace una declaración más fuerte que la notación O grande correspondiente: cada función que es o pequeña de g también es O grande de g , pero no toda función que es O grande de g g también es pequeño-o de g . Por ejemplo, pero . ${\displaystyle 2x^{2}=O(x^{2})}$ ${\displaystyle 2x^{2}\neq o(x^{2})}$

Como g ( x ) es distinto de cero, o al menos se vuelve distinto de cero más allá de cierto punto, la relación es equivalente a ${\displaystyle f(x)=o(g(x))}$

${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}$(y así es, de hecho, como Landau ^[16] definió originalmente la notación o pequeña).

Little-o respeta una serie de operaciones aritméticas. Por ejemplo,

si c es una constante distinta de cero y entonces , y ${\displaystyle f=o(g)}$ ${\displaystyle c\cdot f=o(g)}$

si y entonces ${\displaystyle f=o(F)}$ ${\displaystyle g=o(G)}$ ${\displaystyle f\cdot g=o(F\cdot G).}$

También satisface una relación de transitividad :

si y entonces ${\displaystyle f=o(g)}$ ${\displaystyle g=o(h)}$ ${\displaystyle f=o(h).}$

Notación Omega grande

Otra notación asintótica es , leída "gran omega". ^[18] Hay dos definiciones generalizadas e incompatibles de la declaración ${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))}$como , ${\displaystyle x\to a}$

donde a es un número real, o , donde f y g son funciones reales definidas en una vecindad de a , y donde g es positivo en esta vecindad. ${\displaystyle \infty }$ ${\displaystyle -\infty }$

La definición de Hardy-Littlewood se utiliza principalmente en teoría analítica de números , y la definición de Knuth principalmente en teoría de la complejidad computacional ; las definiciones no son equivalentes.

La definición de Hardy-Littlewood

En 1914 Godfrey Harold Hardy y John Edensor Littlewood introdujeron el nuevo símbolo , ^[19] que se define de la siguiente manera: ${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))}$como si ${\displaystyle x\to \infty }$ ${\displaystyle \limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.}$

Así es la negación de . ${\displaystyle f(x)=\Omega (g(x))}$ ${\displaystyle f(x)=o(g(x))}$

En 1916 los mismos autores introdujeron los dos nuevos símbolos y los definieron como: ^[20] ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{L}}$

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

${\displaystyle f(x)=\Omega _{L}(g(x))}$como si ${\displaystyle x\to \infty }$ ${\displaystyle \liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.}$

Estos símbolos fueron utilizados por Edmund Landau , con los mismos significados, en 1924. ^[21] Después de Landau, las notaciones nunca volvieron a usarse exactamente así; se convirtió y se convirtió . ^{[ cita necesaria ]} ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{+}}$ ${\displaystyle \Omega _{L}}$ ${\displaystyle \Omega _{-}}$

Estos tres símbolos , así como (lo que significa que y ambos se satisfacen), se utilizan actualmente en la teoría analítica de números . ^{[22] [23]} ${\displaystyle \Omega ,\Omega _{+},\Omega _{-}}$ ${\displaystyle f(x)=\Omega _{\pm }(g(x))}$ ${\displaystyle f(x)=\Omega _{+}(g(x))}$ ${\displaystyle f(x)=\Omega _{-}(g(x))}$

Ejemplos simples

Tenemos

${\displaystyle \sin x=\Omega (1)}$como ${\displaystyle x\to \infty ,}$

y más precisamente

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

Tenemos

${\displaystyle \sin x+1=\Omega (1)}$como ${\displaystyle x\to \infty ,}$

y más precisamente

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

sin embargo

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

La definición de Knuth

En 1976, Donald Knuth publicó un artículo para justificar su uso del símbolo - para describir una propiedad más fuerte. ^[24] Knuth escribió: "Para todas las aplicaciones que he visto hasta ahora en informática, un requisito más estricto... es mucho más apropiado". él definió ${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))}$

con el comentario: "Aunque he cambiado la definición de Hardy y Littlewood , me siento justificado al hacerlo porque su definición no es de ningún modo muy utilizada, y porque hay otras maneras de decir lo que quieren decir en casos comparativamente raros. cuando se aplica su definición." ^[24] ${\displaystyle \Omega }$

Familia de notaciones de Bachmann-Landau

Las definiciones de límites suponen que son suficientemente grandes . La tabla está (parcialmente) ordenada de menor a mayor, en el sentido de que (la versión de Knuth de) las funciones on corresponden a la línea real ^[27] (la versión de Hardy-Littlewood , sin embargo, no corresponde a ninguna descripción de este tipo). ). ${\displaystyle g(n)>0}$ ${\displaystyle n}$ ${\displaystyle o,O,\Theta ,\sim ,}$ ${\displaystyle \Omega ,\omega }$ ${\displaystyle <,\leq ,\approx ,=,}$ ${\displaystyle \geq ,>}$ ${\displaystyle \Omega }$

La informática utiliza las notaciones grande , gran Theta , pequeño , pequeño omega y el gran Omega de Knuth . ^[28] La teoría analítica de números a menudo utiliza el Omega grande , pequeño y grande de Hardy-Littlewood (con o sin los subíndices +, − o ±) y notaciones. ^[22] La notación omega pequeña no se utiliza con tanta frecuencia en el análisis. ^[29] ${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle o}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle O}$ ${\displaystyle o}$ ${\displaystyle \Omega }$ ${\displaystyle \sim }$ ${\displaystyle \omega }$

Uso en informática

De manera informal, especialmente en informática, la notación O grande a menudo se puede usar de manera algo diferente para describir un límite estrecho asintótico donde el uso de la notación Theta Θ grande podría ser más apropiado en un contexto dado. ^[30] Por ejemplo, al considerar una función T ( n ) = 73 n ³ + 22 n ² + 58, todos los siguientes son generalmente aceptables, pero los límites más estrictos (como los números 2 y 3 a continuación) generalmente se prefieren fuertemente a límites más flexibles (como el número 1 a continuación).

1. T ( norte ) = O ( norte ¹⁰⁰ )
2. T ( norte ) = O ( norte ³ )
3. T ( norte ) = Θ ( norte ³ )

Las declaraciones equivalentes en inglés son respectivamente:

1. T ( n ) crece asintóticamente no más rápido que n ¹⁰⁰
2. T ( n ) crece asintóticamente no más rápido que n ³
3. T ( n ) crece asintóticamente tan rápido como n ³ .

Entonces, si bien las tres afirmaciones son ciertas, cada una de ellas contiene progresivamente más información. En algunos campos, sin embargo, la notación O grande (número 2 en las listas anteriores) se usaría con más frecuencia que la notación Theta grande (elementos numerados 3 en las listas anteriores). Por ejemplo, si T ( n ) representa el tiempo de ejecución de un algoritmo recientemente desarrollado para un tamaño de entrada n , los inventores y usuarios del algoritmo podrían estar más inclinados a poner un límite asintótico superior al tiempo que tomará ejecutarse sin hacer un declaración explícita sobre el límite asintótico inferior.

Otra notación

En su libro Introducción a los algoritmos , Cormen , Leiserson , Rivest y Stein consideran el conjunto de funciones f que satisfacen

${\displaystyle f(n)=O(g(n))\quad (n\to \infty )~.}$

En una notación correcta, este conjunto puede, por ejemplo, llamarse O ( g ), donde

$${\displaystyle O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.}$$

^[31]

Los autores afirman que el uso del operador de igualdad (=) para indicar la pertenencia a un conjunto en lugar del operador de pertenencia a un conjunto (∈) es un abuso de notación, pero hacerlo tiene ventajas. ^[6] Dentro de una ecuación o desigualdad, el uso de notación asintótica representa una función anónima en el conjunto O ( g ), que elimina términos de orden inferior y ayuda a reducir el desorden no esencial en las ecuaciones, por ejemplo: ^[32]

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

Extensiones de las notaciones de Bachmann-Landau

Otra notación que se utiliza a veces en informática es Õ (léase O suave ), que oculta factores polilogarítmicos. Hay dos definiciones en uso: algunos autores usan f ( n ) =  Õ ( g ( n ) ) como abreviatura de f ( n ) = O ( g ( n ) log ^k n ) para algunos k , mientras que otros lo usan como abreviatura para f ( n ) = O ( g ( n ) log ^k g ( n )) . ^[33] Cuando g ( n ) es polinomio en n , no hay diferencia; sin embargo, la última definición permite decir, por ejemplo, que mientras que la primera definición permite cualquier constante k . Algunos autores escriben O ^* con el mismo propósito que la última definición. ^[34] Esencialmente, es una notación O grande, ignorando los factores logarítmicos porque los efectos de la tasa de crecimiento de alguna otra función superlogarítmica indican una explosión de la tasa de crecimiento para parámetros de entrada de gran tamaño que es más importante para predecir un mal rendimiento en tiempo de ejecución. que los efectos más finos aportados por los factores de crecimiento logarítmico. Esta notación se utiliza a menudo para evitar las "crisis" dentro de las tasas de crecimiento que se afirman como demasiado estrechamente acotadas para los asuntos que nos ocupan (ya que log ^k n es siempre o ( n ^ε ) para cualquier constante k y cualquier ε > 0 ). ${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$ ${\displaystyle \log ^{k}n={\tilde {O}}(1)}$ 

También la notación L , definida como

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$

es conveniente para funciones que están entre polinomiales y exponenciales en términos de . ${\displaystyle \ln n}$

Generalizaciones y usos relacionados

La generalización a funciones que toman valores en cualquier espacio vectorial normado es sencilla (reemplazando valores absolutos por normas), donde f y g no necesitan tomar sus valores en el mismo espacio. También es posible una generalización a funciones g que toman valores en cualquier grupo topológico ^{[ cita requerida ]} . El "proceso limitante" x  →  x _o también se puede generalizar introduciendo una base de filtro arbitraria, es decir, redes dirigidas f y  g . La notación o se puede utilizar para definir derivadas y diferenciabilidad en espacios bastante generales, y también equivalencia (asintótica) de funciones,

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

que es una relación de equivalencia y una noción más restrictiva que la relación " f es Θ( g )" vista arriba. (Se reduce a lim f / g = 1 si f y g son funciones de valores reales positivas). Por ejemplo, 2 x es Θ( x ), pero 2 x − x no es o ( x ).

Historia (notaciones de Bachmann-Landau, Hardy y Vinogradov)

El símbolo O fue introducido por primera vez por el teórico de números Paul Bachmann en 1894, en el segundo volumen de su libro Analytische Zahlentheorie (" teoría analítica de números "). ^[1] El teórico de números Edmund Landau la adoptó y, por tanto, se inspiró para introducir en 1909 la notación o; ^[2] por lo tanto, ambos ahora se denominan símbolos de Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. ^[35] El símbolo (en el sentido de "no es una o de") fue introducido en 1914 por Hardy y Littlewood. ^[19] Hardy y Littlewood también introdujeron en 1916 los símbolos ("derecha") e ("izquierda"), ^[20] precursores de los símbolos modernos ("no es más pequeño que una o pequeña de") y ("no es más grande que una o pequeña de"). Por eso, los símbolos Omega (con sus significados originales) a veces también se denominan "símbolos de Landau". Esta notación se volvió de uso común en la teoría de números al menos desde la década de 1950. ^[36] En la década de 1970, la O grande fue popularizada en la informática por Donald Knuth , quien introdujo la notación Theta relacionada y propuso una definición diferente para la notación Omega. ^[24] ${\displaystyle \Omega }$ ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{L}}$ ${\displaystyle \Omega _{+}}$ ${\displaystyle \Omega _{-}}$ ${\displaystyle \Omega }$

Landau nunca usó los símbolos Theta grande y omega pequeño.

Los símbolos de Hardy eran (en términos de la notación O moderna )

${\displaystyle f\preccurlyeq g\iff f\in O(g)}$   y   ${\displaystyle f\prec g\iff f\in o(g);}$

(Sin embargo, Hardy nunca definió ni usó la notación , ni , como se ha informado a veces). Hardy introdujo los símbolos y (así como algunos otros símbolos) en su tratado de 1910 "Orders of Infinity", y los utilizó sólo en tres artículos (1910-1913). En los casi 400 artículos y libros que le quedan, utilizó constantemente los símbolos de Landau O y o. ${\displaystyle \prec \!\!\prec }$ ${\displaystyle \ll }$ ${\displaystyle \preccurlyeq }$ ${\displaystyle \prec }$

La notación de Hardy ya no se utiliza. Por otro lado, en la década de 1930, ^[37] el teórico de números ruso Ivan Matveyevich Vinogradov introdujo su notación , que se ha utilizado cada vez más en teoría de números en lugar de la notación. Tenemos ${\displaystyle \ll }$ ${\displaystyle O}$

${\displaystyle f\ll g\iff f\in O(g),}$

y frecuentemente ambas notaciones se utilizan en el mismo artículo.

La O grande originalmente significa "orden de" ("Ordnung", Bachmann 1894) y, por lo tanto, es una letra latina. Ni Bachmann ni Landau lo llamaron nunca "Omicron". El símbolo fue visto mucho más tarde (1976) por Knuth como un ómicrón mayúscula , ^[24] probablemente en referencia a su definición del símbolo Omega . No se debe utilizar el dígito cero .

Ver también

• Expansión asintótica : aproximación de funciones que generalizan la fórmula de Taylor
• Algoritmo asintóticamente óptimo : frase utilizada frecuentemente para describir un algoritmo que tiene un límite superior asintóticamente dentro de una constante de un límite inferior para el problema.
• O grande en notación de probabilidad : O _p , o _p
• Límite inferior y límite superior : una explicación de algunas de las notaciones de límite utilizadas en este artículo.
• Teorema maestro (análisis de algoritmos) : para analizar algoritmos recursivos de divide y vencerás utilizando la notación Big O
• Teorema de Nachbin : un método preciso para acotar funciones analíticas complejas de modo que se pueda establecer el dominio de convergencia de transformadas integrales
• Orden de aproximación
• Complejidad computacional de las operaciones matemáticas.

Referencias y notas

1. Bachmann, Paul (1894). Analytische Zahlentheorie [ Teoría analítica de números ] (en alemán). vol. 2. Leipzig: Teubner.
2. Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Manual sobre la teoría de la distribución de los números primos ] (en alemán). Leipzig: BG Teubner. pag. 883.
3. Mohr, Austin. «Computación Cuántica en Teoría de la Complejidad y Teoría de la Computación» (PDF) . pag. 2. Archivado (PDF) desde el original el 8 de marzo de 2014 . Consultado el 7 de junio de 2014 .
4. Landau, Edmundo (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Manual sobre la teoría de la distribución de los números primos ] (en alemán). Leipzig: BG Teubner. pag. 31.
5. Michael Sipser (1997). Introducción a la Teoría de la Computación . Boston/MA: PWS Publishing Co.Aquí: Def.7.2, p.227
6. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3ª ed.). Cambridge/MA: MIT Press. pag. 45.ISBN _ 978-0-262-53305-8. Debido a que θ ( g ( n ) ) es un conjunto, podríamos escribir " f ( n ) ∈ θ ( g ( n )) " para indicar que f ( n ) es miembro de θ ( g ( n ) ). En cambio, normalmente escribiremos f ( n ) = θ ( g ( n )) para expresar la misma noción. Quizás se sienta confundido porque abusamos de la igualdad de esta manera, pero veremos más adelante en esta sección que hacerlo tiene sus ventajas.
7. Cormen et al. (2009), pág. 53
8. Howell, Rodney. "Sobre notación asintótica con múltiples variables" (PDF) . Archivado (PDF) desde el original el 24 de abril de 2015 . Consultado el 23 de abril de 2015 .
9. NG de Bruijn (1958). Métodos asintóticos en análisis. Ámsterdam: Holanda Septentrional. págs. 5–7. ISBN 978-0-486-64221-5. Archivado desde el original el 17 de enero de 2023 . Consultado el 15 de septiembre de 2021 .
10. Graham, Ronald ; Knuth, Donald ; Patashnik, Oren (1994). Matemáticas concretas (2 ed.). Reading, Massachusetts: Addison-Wesley. pag. 446.ISBN _ 978-0-201-55802-9. Archivado desde el original el 17 de enero de 2023 . Consultado el 23 de septiembre de 2016 .
11. Donald Knuth (junio-julio de 1998). "Enseñar cálculo con Big O" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 45 (6): 687. Archivado (PDF) desde el original el 14 de octubre de 2021 . Consultado el 5 de septiembre de 2021 .(Versión íntegra Archivada el 13 de mayo de 2008 en Wayback Machine )
12. Donald E. Knuth, El arte de la programación informática. vol. 1. Algoritmos fundamentales, tercera edición, Addison Wesley Longman, 1997. Sección 1.2.11.1.
13. Ronald L. Graham, Donald E. Knuth y Oren Patashnik, Matemáticas concretas: una base para la informática (2ª ed.) , Addison-Wesley, 1994. Sección 9.2, p. 443.
14. Sivaram Ambikasaran y Eric Darve, Un solucionador rápido y directo para matrices semiseparables jerárquicamente parciales, J. Scientific Computing 57 (2013), no. 3, 477–501. ${\displaystyle {\mathcal {O}}(N\log N)}$
15. Saket Saurabh y Meirav Zehavi, -Max-Cut: un algoritmo de tiempo y un núcleo polinómico, Algorithmica 80 (2018), no. 12, 3844–3860. ${\displaystyle (k,n-k)}$ ${\displaystyle {\mathcal {O}}^{*}(2^{p})}$
16. Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Manual sobre la teoría de la distribución de los números primos ] (en alemán). Leipzig: BG Teubner. pag. 61.
17. Thomas H. Cormen et al., 2001, Introducción a los algoritmos, segunda edición, cap. 3.1 Archivado el 16 de enero de 2009 en Wayback Machine.
18. Cormen TH, Leiserson CE, Rivest RL, Stein C (2009). Introducción a los algoritmos (3ª ed.). Cambridge, Massachusetts: MIT Press. pag. 48.ISBN _ 978-0-262-27083-0. OCLC  676697295.
19. Hardy, GH; Littlewood, JE (1914). "Algunos problemas de aproximación diofántica: Parte II. La serie trigonométrica asociada a las funciones θ elípticas". Acta Matemática . 37 : 225. doi : 10.1007/BF02401834 . Archivado desde el original el 12 de diciembre de 2018 . Consultado el 14 de marzo de 2017 .
20. GH Hardy y JE Littlewood, «Contribución a la teoría de la función zeta de Riemann y la teoría de la distribución de números primos», Acta Mathematica , vol. 41, 1916.
21. E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV". Nachr. Gesell. Wiss. Gött. Matemáticas y física. kl. 1924, 137-150.
22. Aleksandar Ivić. La función zeta de Riemann, capítulo 9. John Wiley & Sons 1985.
23. Gérald Tenenbaum, Introducción a la teoría analítica y probabilística de números, Capítulo I.5. Sociedad Estadounidense de Matemáticas, Providence RI, 2015.
24. Knuth, Donald (abril-junio de 1976). "Gran Omicron, gran Omega y gran Theta" (PDF) . Noticias SIGACT . 8 (2): 18–24. doi :10.1145/1008328.1008329. S2CID  5230246. Archivado desde el original el 8 de abril de 2022 . Consultado el 8 de diciembre de 2022 .{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
25. Balcázar, José L.; Gabarró, Joaquim. "Clases de complejidad no uniformes especificadas por límites superiores e inferiores" (PDF) . RAIRO – Informática Teórica y Aplicaciones – Informatique Théorique et Applications . 23 (2): 180. ISSN  0988-3754. Archivado (PDF) desde el original el 14 de marzo de 2017 . Consultado el 14 de marzo de 2017 .
26. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh y otras comparaciones". Condición: La geometría de los algoritmos numéricos . Berlín, Heidelberg: Springer. págs. 467–468. doi :10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
27. Vitányi, Paul ; Meertens, Lambert (abril de 1985). "Gran Omega versus funciones salvajes" (PDF) . Noticias ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . doi :10.1145/382242.382835. S2CID  11700420. Archivado (PDF) desde el original el 10 de marzo de 2016 . Consultado el 14 de marzo de 2017 . 
28. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 41–50. ISBN 0-262-03293-7.
29. por ejemplo, se omite en: Hildebrand, AJ "Notaciones asintóticas" (PDF) . Departamento de Matemáticas. Métodos asintóticos en análisis . Math 595, otoño de 2009. Urbana, IL: Universidad de Illinois. Archivado (PDF) desde el original el 14 de marzo de 2017 . Consultado el 14 de marzo de 2017 .
30. Cormen et al. (2009), pág. 64: "Mucha gente sigue utilizando la notación O donde la notación Θ es más técnicamente precisa".
31. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3ª ed.). Cambridge/MA: MIT Press. pag. 47.ISBN _ 978-0-262-53305-8. Cuando sólo tenemos un límite superior asintótico, utilizamos la notación O. Para una función dada g ( n ), denotamos por O ( g ( n )) (pronunciado "big-oh de g de n " o, a veces, simplemente "oh de g de n ") el conjunto de funciones O ( g ( n )) = { f ( n ) : existen constantes positivas c y n ₀ tales que 0 ≤ f ( n ) ≤ cg ( n ) para todo n ≥ n ₀ }
32. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3ª ed.). Cambridge/MA: MIT Press. pag. 49.ISBN _ 978-0-262-53305-8. Cuando la notación asintótica está sola (es decir, no dentro de una fórmula más grande) en el lado derecho de una ecuación (o desigualdad), como en n = O(n ² ), ya hemos definido el signo igual para significar conjunto membresía: n ∈ O(n ² ). Sin embargo, en general, cuando aparece notación asintótica en una fórmula, la interpretamos como si representara alguna función anónima que no nos interesa nombrar. Por ejemplo, la fórmula 2 n ² + 3 n + 1 = 2 n ² + θ ( n ) significa que 2 n ² + 3 n + 1 = 2 n ² + f ( n ), donde f ( n ) es alguna función en el conjunto θ ( n ). En este caso, dejamos f ( n ) = 3 n + 1, que de hecho está en θ ( n ). Usar la notación asintótica de esta manera puede ayudar a eliminar detalles no esenciales y el desorden en una ecuación.
33. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introducción a los algoritmos (4ª ed.). Cambridge, Massachusetts: The MIT Press. págs. 74–75. ISBN 9780262046305.
34. Andreas Björklund, Thore Husfeldt y Mikko Koivisto (2009). "Establecer partición mediante inclusión-exclusión" (PDF) . Revista SIAM de Computación . 39 (2): 546–563. doi : 10.1137/070683933. Archivado (PDF) desde el original el 3 de febrero de 2022 . Consultado el 3 de febrero de 2022 .Ver apartado 2.3, p.551.
35. Erdelyi, A. (1956). Expansiones asintóticas . Corporación de mensajería. ISBN 978-0-486-60318-6.
36. EC Titchmarsh, La teoría de la función Zeta de Riemann (Oxford; Clarendon Press, 1951)
37. Véase, por ejemplo, "Una nueva estimación de G ( n ) en el problema de Waring" (ruso). Doklady Akademii Nauk SSSR 5, núms. 5-6 (1934), 249–253. Traducido al inglés en: Obras seleccionadas / Ivan Matveevič Vinogradov; preparado por el Instituto de Matemáticas Steklov de la Academia de Ciencias de la URSS con motivo de su 90 cumpleaños. Springer-Verlag, 1985.

Otras lecturas

• Hardy, GH (1910). Órdenes del infinito: el 'Infinitärcalcül' de Paul du Bois-Reymond. Prensa de la Universidad de Cambridge .
• Knuth, Donald (1997). "1.2.11: Representaciones asintóticas". Algoritmos fundamentales . El arte de la programación informática. vol. 1 (3ª ed.). Addison-Wesley. ISBN 978-0-201-89683-1.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "3.1: Notación asintótica". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. ISBN 978-0-262-03293-3.
• Sipser, Michael (1997). Introducción a la Teoría de la Computación . Publicación PWS. págs. 226-228. ISBN 978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalizando la notación O en Isabelle/HOL (PDF) . Conferencia conjunta internacional sobre razonamiento automatizado. doi :10.1007/978-3-540-25984-8_27.
• Negro, Paul E. (11 de marzo de 2005). Negro, Paul E. (ed.). "notación O grande". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 16 de diciembre de 2006 .
• Negro, Paul E. (17 de diciembre de 2004). Negro, Paul E. (ed.). "notación o pequeña". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 16 de diciembre de 2006 .
• Negro, Paul E. (17 de diciembre de 2004). Negro, Paul E. (ed.). "Ω". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 16 de diciembre de 2006 .
• Negro, Paul E. (17 de diciembre de 2004). Negro, Paul E. (ed.). "ω". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 16 de diciembre de 2006 .
• Negro, Paul E. (17 de diciembre de 2004). Negro, Paul E. (ed.). "Θ". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 16 de diciembre de 2006 .

enlaces externos

• Crecimiento de secuencias - Wiki OEIS (Enciclopedia en línea de secuencias enteras)
• Introducción a las notaciones asintóticas
• Notación O grande: ¿para qué sirve?
• Un ejemplo de Big O en la precisión del esquema de diferencia dividida central para la primera derivada. Archivado el 7 de octubre de 2018 en Wayback Machine.
• Una suave introducción al análisis de la complejidad de los algoritmos