Notación O grande

Describe el comportamiento limitante de una función.

Ejemplo de notación Big O: como existe (p. ej., ) y (p. ej., ) tales que siempre que . ${\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 Big O es una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o hacia el infinito. Big O es miembro de una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann , ^[1] Edmund Landau , ^[2] y otros, llamadas colectivamente notación Bachmann-Landau o notación asintótica . La letra O fue elegida por Bachmann para representar Ordnung , es decir, el orden de aproximación .

En informática , la notación O mayúscula 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 mayúscula 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 en el teorema de los números primos . La notación O mayúscula también se utiliza en muchos otros campos para proporcionar estimaciones similares.

La notación O mayúscula caracteriza las funciones según sus tasas de crecimiento: distintas funciones con la misma tasa de crecimiento asintótico pueden representarse utilizando la misma notación O. Se utiliza la letra O porque la tasa de crecimiento de una función también se conoce como el orden de la función . Una descripción de una función en términos de notación O mayúscula generalmente solo proporciona un límite superior para 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. ^[3]

Definición formal

Sea la función a estimar una función de valor real o complejo , y sea la función de comparación una función de valor real. Dejemos que ambas funciones se definan en algún subconjunto ilimitado de los números reales positivos , y sean distintas de cero (a menudo, pero no necesariamente, estrictamente positivas) para todos los valores suficientemente grandes de ^[4] Se escribe y se lee " es grande O de " o más a menudo " es del orden de " si el valor absoluto de es como máximo un múltiplo constante positivo del valor absoluto de para todos los valores suficientemente grandes de Es decir, si existe un número real positivo y un número real tal que En muchos contextos, la suposición de que estamos interesados ​​en la tasa de crecimiento a medida que la variable tiende a infinito o a cero se deja sin establecer, y se escribe de forma más sencilla que La notación también se puede utilizar para describir el comportamiento de cerca de algún número real (a menudo, ): decimos si existen números positivos y tales que para todos definidos con Como es distinto de cero para valores adecuadamente grandes (o pequeños) de ambas definiciones se pueden unificar utilizando el límite superior : si Y en ambas definiciones el punto límite (sea o no) un punto de clúster de los dominios de e i. es decir, en cada entorno de deben existir infinitos puntos en común. Además, como se señala en el artículo sobre el límite inferior y el límite superior , el (al menos en la línea de números reales extendida ) siempre existe. ${\displaystyle f,}$ ${\displaystyle \ g\,}$ ${\displaystyle g(x)}$ ${\displaystyle x.}$ $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }$$ ${\displaystyle \ f(x)\ }$ ${\displaystyle g(x)}$ ${\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 M\ |g(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 M|g(x)|.}$$ ${\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|}{\left|g(x)\right|}}<\infty .}$$ ${\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 ligeramente más restrictiva: y se requiere que ambos sean funciones desde algún subconjunto ilimitado de los números enteros positivos hasta los 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 M|g(n)|}$ ${\displaystyle n\geq n_{0}.}$

Ejemplo

En el uso típico, la notación O es asintótica, es decir, se refiere a valores x muy grandes . En este contexto, la contribución de los términos que crecen "más rápidamente" 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 conservar y omitir todos los demás.
• Si f ( x ) es un producto de varios factores, se pueden omitir todas las constantes (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, utilizando la notación O , para describir su tasa de crecimiento a medida que x tiende 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 la tasa de crecimiento más alta es el que tiene el 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 lo tanto, decimos que f ( x ) es una "O grande" de x ⁴ . Matemáticamente, podemos escribir f ( x ) = O ( x ⁴ ) . Se puede confirmar este cálculo usando la definición formal: sea f ( x ) = 6 x ⁴ − 2 x ³ + 5 y g ( x ) = x ⁴ . Aplicando la definición formal de arriba, la afirmación de que f ( x ) = O ( x ⁴ ) es equivalente a su desarrollo, para alguna elección adecuada de un número real x ₀ y un número real positivo M y para todo x > x ₀ . Para probar esto, sea x ₀ = 1 y M = 13 . Entonces, para todo x > x ₀ : entonces $${\displaystyle |f(x)|\leq Mx^{4}}$$ $${\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}.}$$

Usar

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

• En matemáticas , se utiliza comúnmente para describir qué tan cerca una serie finita se aproxima 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. ^[3]

En ambas aplicaciones, la función g ( x ) que aparece dentro de O (·) se elige típicamente 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 requerida ]}

• asintóticas infinitas
• asintótica infinitesimal

Sin embargo, esta distinción es sólo práctica y no de principio: la definición formal de la "gran O" es la misma para ambos casos, sólo que con diferentes límites para el argumento de la función. ^{[ ¿ Investigación 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 versus el tamaño de entrada n para cada función

La notación O grande es útil cuando se analizan algoritmos para determinar su eficiencia. Por ejemplo, el tiempo (o la cantidad de pasos) que se necesitan para completar un problema de tamaño n puede ser T ( n ) = 4 n ² − 2 n + 2 . A medida que n se hace grande, el término n ² pasará a dominar, de modo que todos los demás términos pueden ignorarse; por ejemplo, cuando n = 500 , el término 4 n ² es 1000 veces más grande que el término 2 n . Ignorar este ú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 superará al primero una vez que n crezca más de 1.000.000 , es decir, T (1.000.000) = 1.000.000 ³ = U (1.000.000) . Además, el número 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 suelen variar solo por un factor constante en el número de pasos necesarios para ejecutar un algoritmo. Por lo tanto, la notación O mayúscula captura lo que queda: escribimos

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

o

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

y decir que el algoritmo tiene una complejidad temporal de orden n ^2. 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 (ver la discusión sobre el "signo igual" a continuación) mientras que la primera es considerada por algunos como un abuso de notación . ^[6]

Asintótica infinitesimal

La O mayúscula 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 mayúscula. Consideremos, por ejemplo, la serie exponencial y dos expresiones de la misma 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 finite }}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 algunas veces constantes | x ³ | cuando x está lo suficientemente cerca de 0.

Propiedades

Si la función f puede escribirse como una suma finita de otras funciones, entonces la que crece más rápidamente 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 a 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 . Una que crece más lentamente que cualquier función exponencial de la forma c ⁿ se llama subexponencial . Un algoritmo puede requerir tiempo que sea tanto superpolinomio como subexponencial; ejemplos de esto incluyen los algoritmos más rápidos conocidos para la factorización de números 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 el mismo que O (log( n ^c )) . Los logaritmos difieren solo 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 logaritmos con diferentes bases constantes son equivalentes. Por otro lado, los exponenciales con diferentes bases no son del mismo orden. Por ejemplo, 2 ⁿ y 3 ⁿ no son del mismo orden.

Cambiar las unidades puede afectar o no el orden del algoritmo resultante. Cambiar las unidades es equivalente a multiplicar la variable apropiada por una constante donde sea 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 por cn da 2 ^cn = (2 ^c ) ⁿ . Esto no es equivalente a 2 ⁿ en general. Cambiar las 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 de la cantidad 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 en sí, 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).}$

Variables múltiples

La O mayúscula (y la o minúscula, Ω, etc.) también se puede utilizar con múltiples variables. Para definir la O mayúscula formalmente 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 de que para algunos puede escribirse , donde denota la norma de Chebyshev . Por ejemplo, la afirmació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 se cumpla o . Esta definición permite que todas las coordenadas de aumenten hasta el infinito. En particular, la afirmació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 significativo al generalizar enunciados del contexto univariante al contexto multivariante. 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}}$

Esta 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 igual

La afirmación " f ( x )   es O [ g ( x ) ]   ", tal como se definió anteriormente, se escribe generalmente 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 ser engañoso, ya que sugiere una simetría que esta afirmación no tiene. Como dice de Bruijn , O [ x ] = O [ x ² ]   es verdadera, 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", [como, en esta notación,] "los matemáticos habitualmente usan el signo '=' como usan la palabra 'es' 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 utilizar la notación de conjuntos y escribir f ( x ) ∈ O [ g ( x ) ]   (que se lee 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 ) | ≤ C | g ( 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 la colección de funciones que tienen el crecimiento de h ( x ) más una parte cuyo crecimiento está limitado al de f ( x ). Por lo tanto,

${\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 sobre 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 arbitraria de tiempo) 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 ordenación tiene una complejidad temporal conocida de O ( n ^{2 ), y después de que se ejecuta la subrutina, el algoritmo debe realizar} 55 n ³ + 2 n + 10 pasos adicionales antes de terminar. Por lo tanto, la complejidad temporal total del algoritmo se puede expresar como T ( n ) = 55 n ³ + O ( n ² ) . Aquí los términos 2 n + 10 se subsumen dentro del O ( n ² ) de crecimiento más rápido. Nuevamente, este uso ignora parte del significado formal del símbolo "=", pero permite utilizar la notación O grande como una especie de marcador de posición conveniente.

Usos múltiples

En un uso más complicado, O (·) puede aparecer en diferentes lugares en una ecuación, incluso varias veces en cada lado. Por ejemplo, lo siguiente es cierto para : El significado de tales afirmaciones es el siguiente: para cualquier función que satisfaga cada O (·) en el lado izquierdo, hay algunas funciones que satisfacen cada O (·) en el lado derecho, de modo que al sustituir todas estas funciones en la ecuación los dos lados son iguales. Por ejemplo, la tercera ecuación anterior significa: "Para cualquier función f ( n ) = O (1), hay alguna función g ( n ) = O ( e ⁿ ) tal que n ^{f ( n )} = g ( n )". En términos de la "notación de conjuntos" anterior, el significado es que la clase de funciones representadas por el lado izquierdo es un subconjunto de la clase de funciones representadas por el lado derecho. En este uso, el "=" es un símbolo formal que, a diferencia del uso habitual de "=", no es una relación simétrica . Así, por ejemplo, n ^{O (1)} = O ( e ⁿ ) no implica la afirmación falsa O ( e ⁿ ) = n ^{O (1)} . ${\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}}}$$

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 un símbolo especial. Sin embargo, algunos autores usan la variante caligráfica en su lugar. ^{[14] [15]} ${\displaystyle O(n^{2})}$ ${\displaystyle {\mathcal {O}}}$

Órdenes de funciones comunes

A continuación se incluye 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.

El enunciado se debilita a veces para derivar fórmulas más simples para la complejidad asintótica. Para cualquier y , es un subconjunto de para cualquier , 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

La notación O grande se utiliza ampliamente en informática. Junto con otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau. ^{[ cita requerida ]}

Notación minúscula

Intuitivamente, la afirmación " f ( x ) es o ( g ( x )) " (léase " f ( x ) es un poquito de g ( x ) " o " f ( x ) es de orden inferior a g ( x ) ") significa que g ( x ) crece mucho más rápido que f ( x ) o, equivalentemente, f ( x ) crece mucho más lento que g ( x ) . Como antes, sea f una función real o compleja y g una función real, ambas definidas en algún subconjunto no acotado de los números reales positivos , de modo que g ( x ) sea estrictamente positivo para todos los valores suficientemente grandes de x . Se 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}.}$^[16]

Por ejemplo, uno tiene

${\displaystyle 2x=o(x^{2})}$y     ambos 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 que la primera tiene que ser verdadera para al menos una constante M , la segunda debe cumplirse 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 cada función que es O grande de g es O pequeña de g . Por ejemplo, pero . ${\displaystyle 2x^{2}=O(x^{2})}$ ${\displaystyle 2x^{2}\neq o(x^{2})}$

Si 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 con o minúscula).

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 , que se lee "omega grande". ^[18] Hay dos definiciones generalizadas e incompatibles de la afirmació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 un entorno de a , y donde g es positivo en este entorno. ${\displaystyle \infty }$ ${\displaystyle -\infty }$

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

La definición de Hardy-Littlewood

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

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

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

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}{\bigl (}\ g(x)\ {\bigr )}\quad }$como si ${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}$

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

Estos símbolos fueron utilizados por E. Landau , con los mismos significados, en 1924. ^[21] Los autores que siguieron a Landau, sin embargo, utilizan una notación diferente para las mismas definiciones: ^{[ cita requerida ]} El símbolo ha sido reemplazado por la notación actual con la misma definición y se convirtió en ${\displaystyle \ \Omega _{R}\ }$ ${\displaystyle \ \Omega _{+}\ }$ ${\displaystyle \ \Omega _{L}\ }$ ${\displaystyle \ \Omega _{-}~.}$

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

Ejemplos sencillos

Tenemos

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

y más precisamente

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

Tenemos

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

y más precisamente

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

sin embargo

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$como ${\displaystyle \quad 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 fuerte... es mucho más apropiado". 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 de , me siento justificado en hacerlo porque su definición no es de ninguna manera de uso amplio, y porque hay otras formas de decir lo que quieren decir en los casos comparativamente raros en que se aplica su definición". ^[24] ${\displaystyle \Omega }$

Familia de notaciones de Bachmann-Landau

Las definiciones de límite suponen que es suficientemente grande . La tabla está (parcialmente) ordenada del más pequeño al más grande, en el sentido de que (la versión de Knuth de) en funciones corresponde a en la línea real ^[27] (la versión de Hardy–Littlewood de , 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 big , big Theta , little , little omega y la notación big Omega de Knuth . ^[28] La teoría analítica de números a menudo utiliza las notaciones big , small , Hardy's , ^[29] Hardy–Littlewood big Omega (con o sin los subíndices +, − o ±) y . ^[22] La notación small omega no se utiliza tan a menudo en el análisis. ^[30] ${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle o}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle O}$ ${\displaystyle o}$ ${\displaystyle \asymp }$ ${\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 asintótico estricto , donde el uso de la notación Theta grande Θ podría ser más apropiado en un contexto dado. ^[31] Por ejemplo, al considerar una función T ( n ) = 73 n ³ + 22 n ² + 58, todas las 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 sobre los límites más flexibles (como el número 1 a continuación).

1. T ( n ) = O ( n100 ⁾
2. T ( n ) = O ( n3 ⁾
3. T ( n ) = Θ( n3 ⁾

Las afirmaciones 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 ³ .

Por lo tanto, si bien las tres afirmaciones son verdaderas, cada vez se incluye más información en cada una de ellas. Sin embargo, en algunos campos, la notación O mayúscula (número 2 en las listas anteriores) se usaría con más frecuencia que la notación Theta mayúscula (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 establecer un límite asintótico superior sobre cuánto tiempo tomará ejecutarse sin hacer una 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}\}.}$$^[32]

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

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

Extensiones de las notaciones de Bachmann-Landau

Otra notación que a veces se utiliza en informática es Õ (léase soft-O ), que oculta factores polilogarítmicos. Hay dos definiciones en uso: algunos autores utilizan f ( n ) =  Õ ( g ( n )) como abreviatura de f ( n ) = O ( g ( n ) log ^k n ) para algún k , mientras que otros la utilizan como abreviatura de f ( n ) = O ( g ( n ) log ^k g ( n )) . ^[34] Cuando g ( n ) es polinomial en n , no hay diferencia; sin embargo, la última definición permite decir, por ejemplo, que mientras que la primera definición permite para cualquier constante k . Algunos autores escriben O ^* con el mismo propósito que la última definición. ^[35] Básicamente, se trata de una notación O grande , que ignora 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 de punto más fino aportados por el factor o factores de crecimiento logarítmico. Esta notación se utiliza a menudo para obviar la "critica" dentro de las tasas de crecimiento que se indican como demasiado estrechamente limitadas para los asuntos en cuestión (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)}$ 

Además, 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 polinómicas 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 puede generalizarse introduciendo una base de filtro arbitraria, es decir, a redes dirigidas f y  g . La notación o puede usarse 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 )" de arriba. (Se reduce a lim f / g = 1 si f y g son funciones 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 lo adoptó, y así se inspiró para introducir en 1909 la notación o; ^[2] por lo que ahora ambos se llaman símbolos de Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. ^[36] 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 menor que una o minúscula de") y ("no es mayor que una o minúscula de"). Por lo tanto, los símbolos Omega (con sus significados originales) a veces también se denominan "símbolos de Landau". Esta notación se empezó a utilizar comúnmente en la teoría de números al menos desde la década de 1950. ^[37] ${\displaystyle \Omega }$ ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{L}}$ ${\displaystyle \Omega _{+}}$ ${\displaystyle \Omega _{-}}$ ${\displaystyle \Omega }$

El símbolo , aunque había sido usado antes con diferentes significados, ^[27] recibió su definición moderna por Landau en 1909 ^[38] y por Hardy en 1910. ^[39] Justo arriba en la misma página de su tratado Hardy definió el símbolo , donde significa que tanto como se satisfacen. La notación todavía se usa actualmente en la teoría analítica de números. ^{[40] [29]} En su tratado Hardy también propuso el símbolo , donde significa que para alguna constante . ${\displaystyle \sim }$ ${\displaystyle \asymp }$ ${\displaystyle f(x)\asymp g(x)}$ ${\displaystyle f(x)=O(g(x))}$ ${\displaystyle g(x)=O(f(x))}$ ${\displaystyle \,\asymp \!\!\!\!\!\!-}$ ${\displaystyle f\asymp \!\!\!\!\!\!-g}$ ${\displaystyle f\sim Kg}$ ${\displaystyle K\not =0}$

En la década de 1970, la gran O fue popularizada en la ciencia informática por Donald Knuth , quien propuso una notación diferente para Hardy y propuso una definición diferente para la notación Omega de Hardy y Littlewood. ^[24] ${\displaystyle f(x)=\Theta (g(x))}$ ${\displaystyle f(x)\asymp g(x)}$

Otros dos símbolos acuñados por Hardy fueron (en términos de la notación O moderna)

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

(Sin embargo, Hardy nunca definió ni utilizó la notación , ni , como se ha informado a veces). Hardy introdujo los símbolos y (así como los otros símbolos ya mencionados) en su tratado de 1910 "Órdenes del infinito", y los utilizó solo en tres artículos (1910-1913). En sus casi 400 artículos y libros restantes utilizó sistemáticamente los símbolos de Landau O y o. ${\displaystyle \prec \!\!\prec }$ ${\displaystyle \ll }$ ${\displaystyle \preccurlyeq }$ ${\displaystyle \prec }$

Los símbolos de Hardy y (así como ) ya no se utilizan. Por otro lado, en la década de 1930, ^[41] el teórico de números ruso Ivan Matveyevich Vinogradov introdujo su notación , que se ha utilizado cada vez más en la teoría de números en lugar de la notación . Tenemos ${\displaystyle \preccurlyeq }$ ${\displaystyle \prec }$ ${\displaystyle \,\asymp \!\!\!\!\!\!-}$ ${\displaystyle \ll }$ ${\displaystyle O}$

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

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

La O mayúscula originalmente significaba "orden de" ("Ordnung", Bachmann 1894), y por lo tanto es una letra latina. Ni Bachmann ni Landau la llamaron nunca "ómicron". Mucho más tarde (1976) Knuth consideró que el símbolo era un ómicron mayúscula , ^[24] probablemente en referencia a su definición del símbolo Omega . El dígito cero no debería utilizarse.

Véase también

• Complejidad computacional asintótica
• Expansión asintótica : aproximación de funciones generalizando la fórmula de Taylor
• Algoritmo asintóticamente óptimo : frase que se utiliza con frecuencia 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 las transformadas integrales.
• Orden de aproximación
• Complejidad computacional de 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. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. (1990). "Crecimiento de funciones". Introducción a los algoritmos (1.ª ed.). MIT Press y McGraw-Hill. págs. 23–41. ISBN 978-0-262-53091-0.
4. 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. 31.
5. Sipser, Michael (1997). Introducción a la teoría de la computación . Boston, MA: PWS Publishing. p. 227, definición 7.2.
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. Como θ ( g ( n )) es un conjunto, podríamos escribir " f ( n ) ∈ θ ( g ( n ))" para indicar que f ( n ) es un miembro de θ ( g ( n )). En cambio, normalmente escribiremos f ( n ) = θ ( g ( n )) para expresar la misma noción. Puede que te confundas porque abusamos de la igualdad de esta manera, pero veremos más adelante en esta sección que hacerlo tiene sus ventajas.
7. Cormen y otros (2009), pág. 53
8. Howell, Rodney. "Sobre la 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. de Bruijn, NG (1958). Métodos asintóticos en análisis. Amsterdam: Holanda Septentrional. págs. 5–7. ISBN 978-0-486-64221-5Archivado 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. pág. 446. ISBN 978-0-201-55802-9Archivado desde el original el 17 de enero de 2023. Consultado el 23 de septiembre de 2016 .
11. Donald Knuth (junio-julio de 1998). "Teach Calculus with Big O" (PDF) . Avisos de la American Mathematical Society . 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 ciencia informática (2.ª ed.) , Addison-Wesley, 1994. Sección 9.2, pág. 443.
14. Sivaram Ambikasaran y Eric Darve, Un solucionador directo rápido para matrices jerárquicamente semiseparables parciales, J. Scientific Computing 57 (2013), n.º 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 polinomial, Algorithmica 80 (2018), n.º 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. Las series trigonométricas asociadas a las funciones elípticas θ». Acta Mathematica . 37 : 225. doi : 10.1007/BF02401834 . Archivado desde el original el 2018-12-12 . Consultado el 2017-03-14 .
20. Hardy, GH ; Littlewood, JE (1916). "Contribución a la teoría de la función zeta de Riemann y a la teoría de la distribución de primos". Acta Mathematica . 41 : 119–196. doi :10.1007/BF02422942.
21. Landau, E. (1924). "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV" [Sobre el número de puntos de la cuadrícula en regiones conocidas]. Nachr. Gesell. Wiss. Gött. Matemáticas y física. (en alemán): 137-150.
22. Ivić, A. (1985). La función zeta de Riemann . John Wiley & Sons. Capítulo 9.
23. Tenenbaum, G. (2015). Introducción a la teoría analítica y probabilística de números . Providence, RI: American Mathematical Society. § I.5.
24. Knuth, Donald (abril-junio de 1976). "Gran ómicron, gran omega y gran theta". SIGACT News . 8 (2): 18–24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
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 a través de Numdam.
26. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Estado: 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. , 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. Gérald Tenenbaum, Introducción a la teoría analítica y probabilística de números, « Notación », página xxiii. American Mathematical Society, Providence RI, 2015.
30. Por ejemplo, se omite en: Hildebrand, AJ "Asymptotic Notations" (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) del original el 14 de marzo de 2017. Consultado el 14 de marzo de 2017 .
31. Cormen et al. (2009), pág. 64: "Muchas personas continúan usando la notación O donde la notación Θ es técnicamente más precisa".
32. 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 "oh grande 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 ₀ }
33. 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 aparece sola (es decir, no dentro de una fórmula mayor) en el lado derecho de una ecuación (o desigualdad), como en n = O(n ² ), ya hemos definido el signo igual para significar pertenencia al conjunto: n ∈ O(n ² ). En general, sin embargo, cuando la notación asintótica aparece en una fórmula, la interpretamos como que representa alguna función anónima que no nos importa 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 que f ( n ) = 3 n + 1, que de hecho está en θ ( n ). El uso de la notación asintótica de esta manera puede ayudar a eliminar detalles innecesarios y desorden en una ecuación.
34. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introducción a los algoritmos (4.ª ed.). Cambridge, Mass.: The MIT Press. págs. 74–75. ISBN 9780262046305.
35. Andreas Björklund y Thore Husfeldt y Mikko Koivisto (2009). "Set particioning via inclusion-exclusion" (PDF) . SIAM Journal on Computing . 39 (2): 546–563. doi :10.1137/070683933. Archivado (PDF) desde el original el 2022-02-03 . Consultado el 2022-02-03 .Véase sección 2.3, pág. 551.
36. Erdelyi, A. (1956). Expansiones asintóticas . Courier Corporation. ISBN 978-0-486-60318-6.
37. EC Titchmarsh, La teoría de la función zeta de Riemann (Oxford; Clarendon Press, 1951)
38. 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. 62.
39. Hardy, GH (1910). Órdenes del infinito: el «cálculo del infinito» de Paul du Bois-Reymond. Cambridge University Press , pág. 2.
40. Hardy, GH; Wright, EM (2008) [1.ª ed. 1938]. "1.6. Algunas notaciones". Introducción a la teoría de números . Revisado por DR Heath-Brown y JH Silverman , con prólogo de Andrew Wiles (6.ª ed.). Oxford: Oxford University Press. ISBN 978-0-19-921985-8.
41. Véase, por ejemplo, "Una nueva estimación de G ( n ) en el problema de Waring" (en ruso). Doklady Akademii Nauk SSSR 5, núm. 5-6 (1934), 249-253. Traducido al inglés en: Selected works / 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.

Lectura adicional

• Hardy, GH (1910). Órdenes del infinito: el «cálculo del infinito» de Paul du Bois-Reymond. Cambridge University Press .
• 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 . PWS Publishing. pp. 226–228. ISBN 978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalización de la notación O en Isabelle/HOL (PDF) . Conferencia conjunta internacional sobre razonamiento automatizado. doi :10.1007/978-3-540-25984-8_27.
• Black, Paul E. (11 de marzo de 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "little-o notation". Dictionary of Algorithms and Data Structures . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "Ω". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "ω". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "Θ". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .

Enlaces externos

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