Notación Big O

La notación Big O es una notación matemática que describe el tamaño aproximado de una función en un dominio . Big O pertenece a una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann ^{[ 1 ]} y Edmund Landau ^{[ 2 ]} y ampliadas por otros, conocidas colectivamente como notación Bachmann-Landau . La letra O significa Ordnung , es decir, el orden de aproximación .

En ciencias de la computación , la notación O grande se utiliza para clasificar algoritmos según cómo sus requisitos de tiempo de ejecución o espacio ^{[ a ]} crecen con la entrada. ^{[ 3 ]} En teoría analítica de números , la notación O grande expresa límites en el crecimiento de una función aritmética , como para el término restante en el teorema de los números primos . ^{[ 4 ]} En análisis matemático , incluido el cálculo , la notación O grande limita el error al truncar una serie de potencias y expresa la calidad de aproximación de una función de valor real o complejo por una función más simple.

A menudo, la notación O mayúscula caracteriza las funciones según su tasa de crecimiento a medida que la variable aumenta: diferentes funciones con la misma tasa de crecimiento asintótico pueden representarse con la misma notación O. La letra O se utiliza porque la tasa de crecimiento de una función también se conoce como su orden . La descripción de una función mediante la notación O mayúscula solo proporciona una cota superior para su tasa de crecimiento.

Asociadas a la notación de la gran O hay varias notaciones relacionadas, que utilizan los símbolos${\displaystyle o}$,${\displaystyle \sim }$,${\displaystyle \Omega }$,${\displaystyle \ll }$,${\displaystyle \gg }$,${\displaystyle \asymp }$,${\displaystyle \omega }$, y${\displaystyle \Theta }$para describir otros tipos de límites en las tasas de crecimiento. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]}

Bachmann propuso la notación en 1894 y Landau la amplió en 1909. Una notación anterior fue propuesta por Paul du Bois-Reymond en 1870. ^{[ 9 ]}

Dejar${\textstyle f,}$La función que se va a estimar puede ser una función de valores reales o complejos definida en un dominio.${\textstyle D,}$y dejar${\textstyle g,}$la función de comparación, sea una función de valor real no negativo definida en el mismo conjunto${\textstyle D.}$Las opciones comunes para el dominio son intervalos de números reales, acotados o no acotados, el conjunto de enteros positivos, el conjunto de números complejos y tuplas de números reales/complejos. Con el dominio escrito explícitamente o entendido implícitamente, se escribe

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

que se lee como "${\textstyle f(x)}$es grande${\textstyle O}$de${\textstyle g(x)}$" si existe un número real positivo${\textstyle M}$de tal manera que

$${\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ para\ todo\ }}~\quad x\in D.}$$

Si${\displaystyle g(x)>0}$(es decir, g nunca es cero) en todo el dominio${\displaystyle D,}$una definición equivalente es que la razón${\textstyle {\frac {f(x)}{g(x)}}}$está acotado , es decir, hay un número real positivo${\displaystyle M}$de modo que${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$a pesar de${\displaystyle x\in D.}$Estos abarcan todos los usos de gran tamaño${\textstyle O}$en ciencias de la computación y matemáticas, incluyendo su uso donde el dominio es finito, infinito, real, complejo, de una sola variable o de múltiples variables. En la mayoría de las aplicaciones, se elige la función${\displaystyle g(x)}$apareciendo dentro del argumento de${\textstyle O{\bigl (}\cdot {\bigr )}}$ser una forma lo más simple posible, omitiendo factores constantes y términos de orden inferior. El número${\textstyle M}$se denomina constante implícita porque normalmente no se especifica. Al usar grandes${\textstyle O}$notación, lo que importa es que algún finito${\displaystyle M}$Existe, no su valor específico. Esto simplifica la presentación de muchas desigualdades analíticas.

Para funciones definidas en números reales positivos o enteros positivos, todavía se usa comúnmente una definición más restrictiva y algo contradictoria, ^{[ 3 ] [ 10 ]} especialmente en ciencias de la computación. Cuando se restringe a funciones que eventualmente son positivas, la notación

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

significa que para algún número real${\textstyle a,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$en el dominio${\textstyle \left[a,\infty \right).}$Aquí, la expresión${\textstyle x\to \infty }$no indica un límite , sino la noción de que la desigualdad se cumple para valores suficientemente grandes.${\textstyle x.}$La expresión${\textstyle x\to \infty }$a menudo se omite. ^{[ 3 ]}

De manera similar, para un número real${\textstyle a,}$la notación

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

significa que para alguna constante${\textstyle c>0,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$en el intervalo${\displaystyle \left[a-c,a+c\right];}$es decir, en un pequeño barrio de${\displaystyle a.}$ Además, la notación $${\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ }$$ medio${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}$También son posibles expresiones más complejas .

A pesar de la presencia del signo igual ( = ) como está escrito, la expresión${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$no se refiere a una igualdad , sino más bien a una desigualdad relacionada${\textstyle f}$y${\textstyle g.}$

En la década de 1930, ^{[ 6 ]} el teórico de números ruso IM Vinogradov introdujo la notación${\displaystyle \ll ,}$que se ha utilizado cada vez más en la teoría de números ^{[ 4 ] [ 11 ] [ 12 ]} y otras ramas de las matemáticas, como una alternativa a la${\textstyle O}$notación. Tenemos

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

Con frecuencia, ambas notaciones se utilizan en la misma obra.

En el uso típico el${\displaystyle O}$La notación se aplica a un intervalo infinito de números reales.${\displaystyle [a,\infty )}$y captura el comportamiento de la función para valores muy grandes${\displaystyle x}$En este contexto, la contribución de los términos que crecen "más rápidamente" acabará por hacer irrelevantes a los demás. Por consiguiente, se pueden aplicar las siguientes reglas de simplificación:

• Si${\displaystyle f(x)}$es la suma de varios términos; si hay uno con la mayor tasa de crecimiento, se puede conservar y omitir todos los demás.
• Si${\displaystyle f(x)}$es producto de varios factores, cualesquiera constantes (factores en el producto que no dependen de${\displaystyle x}$) puede omitirse.

Por ejemplo, dejemos${\displaystyle f(x)=6x^{4}-2x^{3}+5}$y supongamos que deseamos simplificar esta función, usando${\displaystyle O}$notación, para describir su tasa de crecimiento para grandes${\displaystyle x}$Esta función es la suma de tres términos:${\displaystyle 6x^{4}}$,${\displaystyle -2x^{3}}$, y${\displaystyle 5}$De estos tres términos, el que tiene la tasa de crecimiento más alta es el que tiene el exponente más grande en función de${\displaystyle x}$, es decir${\displaystyle 6x^{4}}$Ahora se puede aplicar la segunda regla:${\displaystyle 6x^{4}}$es un producto de${\displaystyle 6}$y${\displaystyle x^{4}}$en el que el primer factor no depende de${\displaystyle x}$Omitir este factor da como resultado la forma simplificada.${\displaystyle x^{4}}$Por lo tanto, decimos que${\displaystyle f(x)}$es una "gran O" de${\displaystyle x^{4}}$Matemáticamente, podemos escribir${\displaystyle f(x)=O(x^{4})}$a pesar de${\displaystyle x\geq 1}$. Este cálculo puede confirmarse utilizando la definición formal: sea${\displaystyle f(x)=6x^{4}-2x^{3}+5}$y${\displaystyle g(x)=x^{4}}$. Aplicando la definición formal anterior, la afirmación de que${\displaystyle f(x)=O(x^{4})}$es equivalente a su expansión, $${\displaystyle |f(x)|\leq Mx^{4}}$$ para alguna elección adecuada de un número real positivo${\displaystyle M}$y para todos${\displaystyle x\geq 1}$Para probar esto, dejemos${\displaystyle M=13}$. Entonces, para todos${\displaystyle x\geq 1}$: $${\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}}}$$ entonces $${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$ Si bien también es cierto, por el mismo argumento, que ${\displaystyle f(x)=O(x^{10})}$, esta es una aproximación menos precisa de la función${\displaystyle f}$Por otro lado, la declaración${\displaystyle f(x)=O(x^{3})}$es falso, porque el término${\displaystyle 6x^{4}}$causas ${\displaystyle f(x)/x^{3}}$ser ilimitado.

Cuando una función${\displaystyle T(n)}$describe el número de pasos necesarios en un algoritmo con entrada${\displaystyle n}$, una expresión como $${\displaystyle T(n)=O(n^{2})}$$ con el dominio implícito siendo el conjunto de enteros positivos, puede interpretarse como que el algoritmo tiene como máximo el orden de${\displaystyle n^{2}}$complejidad temporal.

La notación Big O también se puede utilizar para describir el término de error en una aproximación a una función matemática en un intervalo finito. Los términos más significativos se escriben explícitamente y luego los menos significativos se resumen en un único término Big O. Consideremos, por ejemplo, la serie exponencial y dos expresiones de la misma que son válidas cuando${\displaystyle 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{ for all }}|x|\leq 1\\[4pt]&=1+x+O(x^{2})&&{\text{ for all }}|x|\leq 1.\end{aligned}}}$$ La expresión del medio ( la línea con "${\displaystyle O(|x^{3}|)}$" ) significa el valor absoluto del error ${\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }$es como máximo algunos tiempos constantes${\displaystyle ~|x^{3}|\ }$cuando${\displaystyle \ x~}$es pequeño. Este es un ejemplo del uso del teorema de Taylor .

El comportamiento de una función dada puede ser muy diferente en dominios finitos que en dominios infinitos, por ejemplo, $${\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ for }}x\geq 1}$$ mientras $${\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ for }}|x|\leq 1.}$$

$${\displaystyle x\sin y=O(x)\quad {\text{ for }}x\geq 1,y{\text{ any real number}}}$$

$${\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}$$

$${\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}$$

$${\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}$$

Aquí tenemos una función de variable compleja de dos variables. En general, cualquier función acotada es${\displaystyle O(1)}$.

$${\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}$$

El último ejemplo ilustra una mezcla de dominios finitos e infinitos en las diferentes variables.

En todos estos ejemplos, el límite es uniforme en ambas variables. A veces, en una expresión multivariable, una variable es más importante que las demás, y se puede expresar que la constante implícita${\displaystyle M}$depende de una o más de las variables usando subíndices al símbolo de la gran O o el${\displaystyle \ll }$símbolo. Por ejemplo, considere la expresión

$${\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}$$

Esto significa que para cada número real${\displaystyle b}$, hay una constante${\displaystyle M_{b}}$, que depende de${\displaystyle b}$, para que para todos${\displaystyle 0\leq x\leq 1}$, $${\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}$$ Esta afirmación en particular se deriva del teorema general del binomio .

Otro ejemplo, común en la teoría de las series de Taylor , es $${\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}$$ En este caso, la constante implícita depende del tamaño del dominio.

La convención de subíndices se aplica a todas las demás notaciones de esta página.

Aquí se presenta 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 indefinidamente. Las funciones de crecimiento más lento generalmente se enumeran primero.

La declaración${\displaystyle f(n)=O(n!)}$a veces se debilita a${\displaystyle f(n)=O\left(n^{n}\right)}$para derivar fórmulas más simples para la complejidad asintótica. En muchos de estos ejemplos, el tiempo de ejecución es realmente${\displaystyle \Theta (g(n))}$, lo que transmite mayor precisión.

Para funciones de valor real o complejo de una variable real. ${\displaystyle x}$con${\displaystyle g(x)>0}$para suficientemente grande${\displaystyle x}$, escribe uno ^{[ 2 ]}

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

si $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$$ Es decir, para cada constante positiva ε existe una constante${\displaystyle x_{0}}$de tal manera que

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

Intuitivamente, esto significa que${\displaystyle g(x)}$crece mucho más rápido que${\displaystyle f(x)}$o equivalentemente${\displaystyle f(x)}$crece mucho más lentamente que ${\displaystyle g(x)}$. Por ejemplo, uno tiene

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

Cuando uno está interesado en el comportamiento de una función para valores grandes de${\displaystyle x}$, la notación little-o hace una afirmación más fuerte que la notación big-O correspondiente: toda función que sea little-o de${\displaystyle g}$también es big-O de${\displaystyle g}$a intervalos${\displaystyle [a,\infty )}$, pero no todas las funciones que son de notación big-O de${\displaystyle g}$es pequeño-o de${\displaystyle g}$. Por ejemplo,${\displaystyle 2x^{2}=O(x^{2})}$pero${\displaystyle 2x^{2}\neq o(x^{2})}$para${\displaystyle x\geq 1}$.

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

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

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

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

También satisface una relación de transitividad :

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

La notación Little-o también se puede generalizar al caso finito: ^{[ 2 ]}${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}$si $${\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$$ En otras palabras, ${\displaystyle f(x)=\alpha (x)g(x)}$para algunos${\displaystyle \alpha (x)}$con${\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}$.

Esta definición es especialmente útil en el cálculo de límites mediante series de Taylor . Por ejemplo:

${\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}$, entonces${\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}$

La generalización a funciones que toman valores en cualquier espacio vectorial normado es directa (reemplazando los valores absolutos por normas), donde${\displaystyle f}$y${\displaystyle g}$No es necesario que sus valores estén en el mismo espacio. Una generalización a funciones${\displaystyle g}$También es posible tomar valores en cualquier grupo topológico . El "proceso límite"${\displaystyle x\to x_{0}}$También se puede generalizar introduciendo una base de filtro arbitraria, es decir, a redes dirigidas.${\displaystyle f}$y${\displaystyle g}$. El${\displaystyle o}$La notación se puede utilizar para definir derivadas y diferenciabilidad en espacios bastante generales, y también la 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 "${\displaystyle f}$es${\displaystyle \Theta (g)}$" desde arriba. (Se reduce a${\displaystyle \lim f/g=1}$si${\displaystyle f}$y${\displaystyle g}$son funciones de valor real positivo.) Por ejemplo,${\displaystyle 2x=\Theta (x)}$lo es, pero ${\displaystyle 2x-x\neq o(x)}$.

En 1870, Paul du Bois-Reymond ^{[ 9 ]} definió${\displaystyle f(x)\succ \phi (x)}$,${\displaystyle f(x)\sim \phi (x)}$y${\displaystyle f(x)\prec \phi (x)}$ significar, respectivamente, $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=\infty ,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}>0,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=0.}$$ Estas no fueron ampliamente adoptadas y no se utilizan en la actualidad. La primera y la tercera son simétricas:${\displaystyle f(x)\prec \phi (x)}$significa lo mismo que${\displaystyle \phi (x)\succ f(x)}$Landau adoptó posteriormente${\displaystyle \sim }$con la definición más estrecha que el límite de${\displaystyle f(x)/\phi (x)}$es igual a 1.

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, por lo tanto, se inspiró para introducir en 1909 la notación o; ^{[ 2 ]} de ahí que ambos se denominen ahora símbolos de Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. ^{[ 23 ]} El símbolo${\displaystyle \Omega }$(en el sentido de "no es pequeño o de") fue introducido en 1914 por Hardy y Littlewood. ^{[ 7 ]} Hardy y Littlewood también introdujeron en 1916 la izquierda y la derecha${\displaystyle \Omega }$símbolos${\displaystyle \Omega _{R}}$,${\displaystyle \Omega _{L}}$(ahora comúnmente denominado${\displaystyle \Omega _{+},\Omega _{-}}$). ^{[ 15 ]} Esto${\displaystyle \Omega }$La notación se ha utilizado comúnmente en la teoría de números desde la década de 1950. ^{[ 13 ]}

Hardy introdujo los símbolos${\displaystyle \preccurlyeq }$y abogó por Bois-Reymond${\displaystyle \prec }$(así como los otros símbolos ya mencionados) en su tratado de 1910 "Órdenes del infinito", ^{[ 5 ]} pero los utilizó solo en tres artículos (1910-1913). En sus casi 400 artículos y libros restantes, utilizó consistentemente los símbolos de Landau O y o. ^{[ 24 ]} Los símbolos de Hardy${\displaystyle \preccurlyeq }$y${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$ya no se utilizan.

El símbolo${\displaystyle \sim }$, aunque se había usado antes con diferentes significados, ^{[ 9 ]} Landau le dio su definición moderna en 1909 ^{[ 2 ]} y Hardy en 1910. ^{[ 5 ]} En la misma página, Hardy definió el símbolo${\displaystyle \asymp }$, dónde${\displaystyle f(x)\asymp g(x)}$significa que ambos${\displaystyle f(x)=O(g(x))}$y${\displaystyle g(x)=O(f(x))}$están satisfechos. La notación todavía se usa en la teoría analítica de números. ^{[ 25 ] [ 12 ]} Hardy también propuso el símbolo${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$, dónde${\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g}$significa que${\displaystyle f\sim Kg}$por alguna constante${\displaystyle K\not =0}$(esto corresponde a la notación de Bois-Reymond)${\displaystyle f\sim g}$).