Notación Big O

Notación que describe el comportamiento limitante

Aproximación de ajuste
Conceptos
Órdenes de aproximación Análisis de escala  · Notación Big O Ajuste de curvas  · Precisión falsa Cifras significativas
Otros fundamentos
Aproximación  · Error de generalización Polinomio de Taylor Modelado científico
v t mi

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

La notación Big O es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito. Big O es miembro de una familia de notaciones inventadas por Paul Bachmann , ^[1] Edmund Landau , ^[2] y otros, llamadas colectivamente notación de Bachmann-Landau o notación asintótica .

En ciencias de la computación , la notación O grande se usa para clasificar algoritmos de acuerdo con cómo crecen sus requisitos de espacio o tiempo de ejecución a medida que aumenta el tamaño de entrada. ^[3] En la teoría analítica de números , la notación O grande se usa 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 Big O también se usa en muchos otros campos para proporcionar estimaciones similares.

La notación Big O caracteriza las funciones de acuerdo con sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento se pueden representar utilizando la misma notación O. La letra O se usa 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 grande generalmente solo proporciona un límite superior en la tasa de crecimiento de la función. Asociadas con la notación O grande hay varias notaciones relacionadas, usando los símbolos o , Ω, ω y Θ , para describir otros tipos de límites en las tasas de crecimiento asintóticas.

Definición formal

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

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

si el valor absoluto de es como máximo un múltiplo constante positivo de para todos los valores suficientemente grandes de x . Es decir, si existe un número real positivo M y un número real x ₀ tal que${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$

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

En muchos contextos, la suposición de que estamos interesados ​​en la tasa de crecimiento a medida que la variable x llega al infinito no se menciona, y se escribe de manera más simple que

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

La notación también se puede usar para describir el comportamiento de f cerca de algún número real a (a menudo, a = 0 ): decimos

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

si existen números positivos y M tales que para todo x con ,${\displaystyle \delta }$${\displaystyle 0<|x-a|<\delta }$

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

Como se elige que g ( x ) sea ​​distinto de cero para valores de x suficientemente cercanos a a , ambas definiciones se pueden unificar utilizando el límite superior :

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

si

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

En ciencias de la computación, es común una definición un poco más restrictiva: y se requiere que ambas sean funciones de los números enteros positivos a los números reales no negativos; si existen números enteros positivos M y n ₀ tales que para todos . ^[5] En caso necesario, los rangos finitos son (tácitamente) excluidos de 's y ' s dominio eligiendo n ₀ suficientemente grande. (Por ejemplo, no está definido en ).${\displaystyle f}$${\displaystyle g}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$${\displaystyle f(n)\leq Mg(n)}$${\displaystyle n\geq n_{0}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle \log(n)}$${\displaystyle n=0}$

Ejemplo

En el uso típico, la notación O es asintótica, es decir, se refiere a una 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 todos los demás se pueden omitir.
• Si f ( x ) es un producto de varios factores, se pueden omitir las constantes (términos del producto que no dependen de x ).

Por ejemplo, sea f ( x ) = 6 x ⁴ - 2 x ³ + 5 , y suponga 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 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 "gran O" 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, el enunciado de que f ( x ) = O ( x ⁴ ) es equivalente a su expansión,

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

para alguna elección adecuada de x ₀ y M y para todo x > x ₀ . Para probar esto, sea x ₀ = 1 y M = 13 . Entonces, para todo x > 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}}}$

asi que

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

Uso

La notación Big O 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 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 (...) 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:

• asintótica infinita
• asintótica infinitesimal .

Sin embargo, esta distinción es solo en aplicación y no en principio; la definición formal de la "gran O" es la misma para ambos casos, solo que con límites diferentes para el argumento de la función.

Asintótica infinita

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 Big O es útil cuando se analizan algoritmos para determinar la eficiencia. Por ejemplo, el tiempo (o el número de pasos) que se tarda en completar un problema de tamaño n puede ser T ( n ) = 4 n ² - 2 n + 2 . A medida que n crece, el término n ² llegará a dominar, por lo 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 2 ntérmino. 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 contiene 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 de 1,000,000 ( 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 en un factor constante en el número de pasos necesarios para ejecutar un algoritmo. Entonces, la notación O grande captura lo que queda: escribimos o

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

o

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

y decir que el algoritmo tiene un orden de complejidad de tiempo 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 " Signo igual " a continuación) mientras el primero es considerado por algunos como un abuso de notación . ^[6]

Asintótica infinitesimal

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 solo término O grande. Considere, por ejemplo, la serie exponencial y dos expresiones de la misma que son válidas cuando x es pequeña:

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

La segunda expresión (el uno con O ( x ³ )) significa que el valor absoluto del error e ^x - (1 + x + x ² /2) es a lo sumo algunas veces constantes | x ³ | 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 de más rápido crecimiento 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 limitada 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, 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 llamasubexponencial . Un algoritmo puede requerir un tiempo tanto superpolinomial como 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 solo por un factor constante (ya que log ( n ^c ) = c log n ) y, por lo tanto, la notación O grande lo ignora. De manera similar, los registros con diferentes bases constantes son equivalentes. Por otro lado, las exponenciales con bases diferentes no son del mismo orden. Por ejemplo, 2 ⁿ y 3 ⁿ no son del mismo orden.

El cambio de unidades puede afectar o no al orden del algoritmo resultante. Cambiar unidades 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 ⁿ , reemplazando n con cnda 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 en 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

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

Esto implica , lo que significa que es un cono convexo .${\displaystyle f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)}$${\displaystyle O(g)}$

Multiplicación por una constante

Sea k constante. Entonces:

${\displaystyle O(|k|g)=O(g)}$si k es distinto de cero.

${\displaystyle f=O(g)\Rightarrow kf=O(g).}$

Varias variables

Big O (y little o, Ω, etc.) también se puede utilizar con múltiples variables. Para definir formalmente la gran O para múltiples variables, suponga 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 solo si ^[7]

${\displaystyle \exists M\exists C>0~{\text{ such that for all }}~\mathbf {x} ~{\text{ with }}~x_{i}\geq M~{\text{ for some }}~i,|f(\mathbf {x} )|\leq C|g(\mathbf {x} )|~.}$

De manera equivalente, la condición que para algunos puede ser reemplazada por la condición que , donde denota la norma Chebyshev . Por ejemplo, la declaración${\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 \forall \|(n,m)\|_{\infty }\geq M:\quad |g(n,m)|\leq C|n+m|}$

donde g ( n , m ) se define por

${\displaystyle f(n,m)=n^{2}+m^{3}+g(n,m)~.}$

Esta definición permite que todas las coordenadas de aumenten hasta el infinito. En particular, la declaración${\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\dots }$

${\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\dots }$

Según esta definición, el subconjunto en el que se define una función es significativo cuando se generalizan las declaraciones de la configuración univariante a la configuración 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 la gran O a funciones multivariadas y, en la práctica, existe cierta inconsistencia en la elección de la definición. ^[8]

Asuntos de notación

Signo igual

El enunciado " f ( x ) es O ( g ( x ))" como se definió 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 ser engañoso 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 ² de las identidades n = O ( n ² ) y n ² = O ( n ² ) ". ^[10]

Por estas razones, sería más preciso usar la notación de conjuntos y escribir f ( x ) ∈ 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 alguna constante C . ^[10]Sin embargo, es habitual el uso del signo igual. Knuth señaló que "los matemáticos usan habitualmente el signo = como usan la palabra 'es' en inglés: Aristóteles es un hombre, pero un hombre no es necesariamente Aristóteles". ^[11]

Otros operadores aritméticos

La notación Big O 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

Suponga 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 de la cantidad 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 de tiempo conocida de O ( n ² ), y después de que se ejecuta la subrutina, el algoritmo debe tomar 55 n ³ + 2 n + 10 adicionales .pasos antes de que termine. Por tanto, la complejidad temporal global 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 crecimiento más rápido . Nuevamente, este uso ignora algunos de los significados formales del símbolo "=", pero permite usar 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 de una ecuación, incluso varias veces en cada lado. Por ejemplo, lo siguiente es cierto para${\displaystyle n\to \infty }$

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

${\displaystyle (n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})}$

${\displaystyle n^{O(1)}=O(e^{n}).}$

El significado de tales declaraciones 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 hace que los dos lados sean 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 conjunto "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 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 declaración falsa O ( e ⁿ ) = n ^{O (1)}

Tipografía

Big O se compone tipo como una "O" en cursiva mayúsculas, 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 de nombre griego, no necesita ningún símbolo especial. Sin embargo, algunos autores utilizan la variante caligráfica en su lugar. ^{[14] [15]}${\displaystyle O(n^{2})}$${\displaystyle {\mathcal {O}}}$

Órdenes de funciones comunes

Más información: Complejidad temporal § Tabla de complejidades temporales comunes

Aquí hay 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 yn aumenta sin límite. Las funciones de crecimiento más lento generalmente se enumeran primero.

Notación	Nombre	Ejemplo
${\displaystyle O(1)}$	constante	Determinar si un número binario es par o impar; Calculando ; Usar una tabla de búsqueda de tamaño constante${\displaystyle (-1)^{n}}$
${\displaystyle O(\log \log n)}$	doble logarítmico	Número de comparaciones dedicadas a la búsqueda de un elemento mediante la búsqueda de interpolación en una matriz ordenada de valores distribuidos uniformemente
${\displaystyle O(\log n)}$	logarítmico	Encontrar un elemento en una matriz ordenada con una búsqueda binaria o un árbol de búsqueda equilibrado , así como todas las operaciones en un montón Binomial
${\displaystyle O((\log n)^{c})}$ ${\displaystyle \scriptstyle c>1}$	polilogarítmico	El orden de la cadena de matrices se puede resolver en tiempo polilogarítmico en una máquina paralela de acceso aleatorio .
${\displaystyle O(n^{c})}$ ${\displaystyle \scriptstyle 0<c<1}$	poder fraccional	Buscando en un árbol kd
${\displaystyle O(n)}$	lineal	Encontrar un elemento en una lista sin clasificar o en una matriz sin clasificar; sumando dos enteros de n bits por acarreo de ondulación
${\displaystyle O(n\log ^{*}n)}$	n estrella de registro n	Realización de la triangulación de un polígono simple usando el algoritmo de Seidel , o el algoritmo de unión-búsqueda . Tenga en cuenta que${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)}$	lineal , loglineal, cuasilineal o "n log n"	Realización de una transformada rápida de Fourier ; Clasificación de comparación más rápida posible ; heapsort y merge sort
${\displaystyle O(n^{2})}$	cuadrático	Multiplicar dos números de n dígitos por un algoritmo simple; algoritmos de clasificación simples, como clasificación de burbujas , clasificación de selección y clasificación de inserción ; (en el peor de los casos) vinculado a algunos algoritmos de clasificación generalmente más rápidos, como quicksort , Shellsort y tree sort
${\displaystyle O(n^{c})}$	polinomio o algebraico	Análisis gramatical adyacente al árbol ; coincidencia máxima para gráficos bipartitos ; encontrar el determinante con la descomposición LU
${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ ${\displaystyle \scriptstyle 0<\alpha <1}$	Notación L o sub-exponencial	Factorizar un número usando el tamiz cuadrático o el tamiz de campo numérico
${\displaystyle O(c^{n})}$ ${\displaystyle \scriptstyle c>1}$	exponencial	Encontrar la solución (exacta) al problema del viajante mediante programación dinámica ; determinar si dos declaraciones lógicas son equivalentes mediante la búsqueda de fuerza bruta
${\displaystyle O(n!)}$	factorial	Resolver el problema del viajante de comercio mediante la búsqueda por fuerza bruta; generar todas las permutaciones sin restricciones de un poset ; encontrar el determinante con la expansión de Laplace ; enumerando todas las particiones de un conjunto

El enunciado a veces 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 es la notación asintótica más utilizada para comparar funciones. ^{[ cita requerida ]} Junto con algunas otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau.

Notación pequeña-o

La "pequeña o" vuelve a dirigir aquí. Para el jugador de béisbol, vea Omar Vizquel .

Intuitivamente, la afirmación " f ( x ) es o ( g ( x )) " (lea " f ( x ) es pequeño-o de g ( x ) ") significa que g ( x ) crece mucho más rápido que f ( x ) . Sea como antes f una función de valor real o complejo yg una función de valor real, ambas definidas en algún subconjunto ilimitado de los números reales positivos , tal que g ( x) es 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 N tal que

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

Por ejemplo, uno tiene

${\displaystyle 2x=o(x^{2})}$ y ${\displaystyle 1/x=o(1).}$

La diferencia entre la definición anterior para la notación de O grande y la definición actual de o pequeña es que mientras que la primera debe ser cierta para al menos una constante M , la última 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: toda función que es O pequeña de g también es O grande de g , pero no todas las funciones O grande de 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 diferente de cero, o al menos se vuelve diferente 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 de hecho, así es como Landau ^[16] definió originalmente la notación pequeña-o).

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

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

si y luego${\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 luego${\displaystyle f=o(g)}$${\displaystyle g=o(h)}$${\displaystyle f=o(h).}$

Gran notación Omega

Otra notación asintótica es "gran Omega". Desafortunadamente, 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 positiva en esta vecindad.

El primero (cronológicamente) se usa en la teoría analítica de números y el otro en la teoría de la complejidad computacional . Cuando los dos sujetos se encuentran, esta situación seguramente generará confusión.

La definición de Hardy-Littlewood

En 1914, Godfrey Harold Hardy y John Edensor Littlewood introdujeron el nuevo símbolo , ^[18] 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 , definidos como: ^[19]${\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 usados ​​por Edmund Landau , con los mismos significados, en 1924. ^[20] Después de Landau, las notaciones nunca se volvieron a usar exactamente así; se convirtió y se convirtió . ^{[ cita requerida ]}${\displaystyle \Omega _{R}}$${\displaystyle \Omega _{+}}$${\displaystyle \Omega _{L}}$${\displaystyle \Omega _{-}}$

Estos tres símbolos , así como (lo que significa que y ambos están satisfechos), se utilizan actualmente en la teoría analítica de números . ^{[21] [22]}${\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 mas 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 mas 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. Knuth escribió: "Para todas las aplicaciones que he visto hasta ahora en informática, un requisito más fuerte ... 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 de , me siento justificado al hacerlo porque su definición de ninguna manera es de uso generalizado, y porque hay otras formas de decir lo que quieren decir en los casos comparativamente raros cuando se aplique su definición ". ^[23]${\displaystyle \Omega }$

Familia de notaciones de Bachmann-Landau

Notación	Nombre [23]	Descripción	Definicion formal	Definición de límite [24] [25] [26] [23] [18]
${\displaystyle f(n)=O(g(n))}$	Big O; Big Oh; Omicrón grande	${\displaystyle |f|}$está acotado arriba por g (hasta factor constante) asintóticamente	${\displaystyle \exists k>0\exists n_{0}\forall n>n_{0}\colon |f(n)|\leq k\cdot g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}<\infty }$
${\displaystyle f(n)=\Theta (g(n))}$	Gran theta	f está acotada tanto arriba como abajo por g asintóticamente	${\displaystyle \exists k_{1}>0\exists k_{2}>0\exists n_{0}\forall n>n_{0}\colon }$ ${\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)}$	${\displaystyle f(n)=O(g(n))}$y (versión Knuth)${\displaystyle f(n)=\Omega (g(n))}$
${\displaystyle f(n)=\Omega (g(n))}$	Gran Omega en la teoría de la complejidad (Knuth)	f está delimitada por debajo de g asintóticamente	${\displaystyle \exists k>0\exists n_{0}\forall n>n_{0}\colon f(n)\geq k\cdot g(n)}$	${\displaystyle \liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=o(g(n))}$	Pequeña O; Pequeño oh	f está dominado por g asintóticamente	${\displaystyle \forall k>0\exists n_{0}\forall n>n_{0}\colon |f(n)|<k\cdot g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}=0}$
${\displaystyle f(n)\sim g(n)}$	Del orden de	f es igual ag asintóticamente	${\displaystyle \forall \varepsilon >0\exists n_{0}\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1}$
${\displaystyle f(n)=\omega (g(n))}$	Pequeño Omega	f domina g asintóticamente	${\displaystyle \forall k>0\exists n_{0}\forall n>n_{0}\colon |f(n)|>k\cdot |g(n)|}$	${\displaystyle \lim _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}=\infty }$
${\displaystyle f(n)=\Omega (g(n))}$	Gran Omega en teoría de números (Hardy-Littlewood)	${\displaystyle |f|}$no está dominado por g asintóticamente	${\displaystyle \exists k>0\forall n_{0}\exists n>n_{0}\colon |f(n)|\geq k\cdot g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}$

Las definiciones de los límites suponen un n suficientemente grande . La tabla está (en parte) ordenada de menor a mayor, en el sentido de que o, O, Θ, ∼, (versión de Knuth de) Ω, ω en funciones corresponden a <, ≤, ≈, =, ≥,> en el valor real. línea ^[26] (la versión de Hardy-Littlewood de Ω, sin embargo, no corresponde a ninguna de estas descripciones).${\displaystyle g(n)>0}$

Las ciencias de la computación usan las notaciones de gran O , gran Theta Θ, pequeña o , pequeña omega ω y gran Omega Ω de Knuth. ^[27] La teoría analítica de números a menudo usa la O grande , la o pequeña , el Omega grande Ω de Hardy-Littlewood (con o sin los subíndices +, - o ±) y notaciones. ^[21] La notación omega ω pequeña no se usa con tanta frecuencia en el análisis. ^[28]${\displaystyle \sim }$

Uso en informática

Más información: Análisis de algoritmos

De manera informal, especialmente en ciencias de la computación, la notación O grande a menudo se puede usar de manera algo diferente para describir un límite apretado asintótico donde el uso de la notación Theta grande big podría ser más apropiado de hecho en un contexto dado. ^{[ cita requerida ]} Por ejemplo, cuando se considera 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) suelen ser muy preferidos sobre límites más flexibles (como el número 1 a continuación).

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

Las declaraciones en inglés equivalentes 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 verdaderas, cada una contiene más información. En algunos campos, sin embargo, la notación O grande (número 2 en las listas anteriores) se usaría más comúnmente 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 el 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 en cuánto tiempo tardará en 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}\}}$. ^[29]

Los autores afirman que el uso del operador de igualdad (=) para denotar la pertenencia al conjunto en lugar del operador de pertenencia al conjunto (∈) es un abuso de notación, pero que 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: ^[30]

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

Extensiones a las notaciones de Bachmann-Landau

Otra notación que se usa a veces en informática es Õ (leer soft-O ): f ( n ) =  Õ ( g ( n )) es la abreviatura de f ( n ) = O ( g ( n ) log ^k g ( n )) para algunos k . ^[31]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 desempeño en tiempo de ejecución que los más finos. efectos puntuales contribuidos por el factor o factores de crecimiento logarítmico. Esta notación se usa a menudo para obviar el "quisquilloso" dentro de las tasas de crecimiento que se establecen como demasiado estrechamente acotadas para los asuntos en cuestión (ya que log ^k  n es siempre o ( n ^ε ) para cualquier constante k y cualquier ε > 0 ).

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 polinomios 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 de limitación" x  →  x _o también se puede generalizar introduciendo una base de filtro arbitraria , es decir, a 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 )" de arriba. (Se reduce a lím f / g = 1 si f y g son funciones positivas con valor real). 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, por lo tanto, se inspiró para introducir en 1909 la notación o; ^[2] por lo tanto, ambos ahora se llaman símbolos Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. ^[32] El símbolo (en el sentido de "no es una o de") fue introducido en 1914 por Hardy y Littlewood. ^[18] Hardy y Littlewood también introdujeron en 1918 los símbolos ("derecha") y${\displaystyle \Omega }$${\displaystyle \Omega _{R}}$${\displaystyle \Omega _{L}}$("izquierda"), ^[19] precursores de los símbolos modernos ("no es menor que una pequeña o de") y ("no es mayor que una pequeña o de"). Por lo tanto, los símbolos Omega (con sus significados originales) a veces también se denominan "símbolos 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. ^[33] En la década de 1970, la gran O 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. ^[23]${\displaystyle \Omega _{+}}$${\displaystyle \Omega _{-}}$${\displaystyle \Omega }$

Landau nunca usó los símbolos grandes Theta y pequeños omega.

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);}$

(Hardy, sin embargo, nunca definió ni usó la notación , ni tampoco , 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 trabajos y libros que le quedaban usó constantemente los símbolos O y O de Landau.${\displaystyle \prec \!\!\prec }$${\displaystyle \ll }$${\displaystyle \preccurlyeq }$${\displaystyle \prec }$

La notación de Hardy ya no se usa. Por otro lado, en la década de 1930, ^[34] 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 \ll }$${\displaystyle O}$

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

y con frecuencia ambas notaciones se utilizan en el mismo documento.

La gran O originalmente significa "orden de" ("Ordnung", Bachmann 1894), y por lo tanto es una letra latina. Ni Bachmann ni Landau lo llamaron "Omicron". El símbolo fue visto mucho más tarde (1976) por Knuth como un omicron mayúscula , ^[23] 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 generalizando la fórmula de Taylor
• Algoritmo asintóticamente óptimo : una frase que se usa 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.
• Big O en notación de probabilidad : O _p , o _p
• Límite superior y límite inferior : 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 de delimitar funciones analíticas complejas de modo que se pueda establecer el dominio de convergencia de las transformadas integrales.
• Órdenes 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). 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 . Consultado el 7 de junio de 2014 .
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. 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. 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, usualmente escribiremos f ( n ) = θ ( g ( n )) para expresar la misma noción. Puede estar 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, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introducción a los algoritmos (Tercera ed.). MIT. pag. 53 .
8. Howell, Rodney. "En notación asintótica con múltiples variables" (PDF) . Consultado el 23 de abril de 2015 .
9. NG de Bruijn (1958). Métodos asintóticos en análisis . Amsterdam: Holanda Septentrional. págs. 5-7. ISBN 978-0-486-64221-5.
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.
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. ( Versión íntegra )
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, Unsolucionador directo rápido para matricessemiseparablesjerá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: An-Time Algorithm and a Polynomial Kernel, 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 ^{[ página necesaria ]}
18. Hardy, GH; Littlewood, JE (1914). "Algunos problemas de aproximación diofántica: Parte II. La serie trigonométrica asociada con las funciones ϑ elípticas" . Acta Mathematica . 37 : 225. doi : 10.1007 / BF02401834 .
19. G. H. 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 los números primos», Acta Mathematica , vol. 41, 1916.
20. E. Landau, "Über die Anzahl der Gitdoorsunkte in gewissen Bereichen. IV". Nachr. Gesell. Wiss. Gött. Math-Phys. Kl. 1924, 137-150.
21. Aleksandar Ivić. La función zeta de Riemann, capítulo 9. John Wiley & Sons 1985.
22. Gérald Tenenbaum, Introducción a la teoría de números analítica y probabilística, Capítulo I.5. Sociedad Americana de Matemáticas, Providence RI, 2015.
23. Knuth, Donald (abril-junio de 1976). "Gran Omicron y gran Omega y gran Theta" (PDF) . Noticias SIGACT : 18-24.
24. Balcázar, José L .; Gabarró, Joaquim. "Clases de complejidad no uniformes especificadas por límites superior e inferior" (PDF) . RAIRO - Informática teórica y aplicaciones - Informatique Théorique et Applications . 23 (2): 180. ISSN 0988-3754 . Consultado el 14 de marzo de 2017 .  
25. 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.
26. Vitányi, Paul ; Meertens, Lambert (abril de 1985). "Big Omega versus las funciones salvajes" (PDF) . Noticias ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . doi : 10.1145 / 382242.382835 .  
27. 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.
28. 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 . Consultado el 14 de marzo de 2017 .
29. 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 solo tenemos un límite superior asintótico, usamos la notación O. Para una función dada g ( n ), denotamos por O ( g ( n )) (pronunciado "gran-oh de g de n " oa veces simplemente "oh de g de n ") el conjunto de funciones O ( g ( n )) = { f ( n ): existen constantes positivas c y n ₀ tal que 0 ≤ f ( n ) ≤ cg ( n ) para todon ≥ n ₀ }
30. 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 la pertenencia al conjunto. : n ∈ O (n²). Sin embargo, en general, cuando la notación asintótica aparece en una fórmula, la interpretamos como una función anónima que no queremos 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 del conjunto θ ( n ). En este caso, dejamos 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 los detalles no esenciales y el desorden en una ecuación.
31. Introducción a los algoritmos . Cormen, Thomas H. (Tercera ed.). Cambridge, Mass .: MIT Press. 2009. p. 63 . ISBN 978-0-262-27083-0. OCLC  676697295 .
32. Erdelyi, A. (1956). Expansiones asintóticas . ISBN 978-0-486-60318-6.
33. EC Titchmarsh, La teoría de la función Zeta de Riemann (Oxford; Clarendon Press, 1951)
34. Véase, por ejemplo, "Una nueva estimación de G ( n ) en el problema de Waring" (ruso). Doklady Akademii Nauk SSSR 5, No 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.

Lectura adicional

• 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. 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 de PWS. 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.). "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 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "notación pequeña-o" . 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 .
• 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 EE. UU . 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 EE. UU . 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 EE. UU . Consultado el 16 de diciembre de 2006 .

Enlaces externos

Las estructuras de datos de Wikibook tienen una página sobre el tema: Notación Big-O

Wikiversity resolvió un problema de MyOpenMath usando la notación Big-O

• Crecimiento de secuencias - Wiki OEIS (Enciclopedia en línea de secuencias enteras)
• Introducción a las notaciones asintóticas ^{[ enlace muerto permanente ]}
• Símbolos de Landau
• Notación Big-O: para qué sirve
• La notación Big O explicada en inglés sencillo
• Un ejemplo de Big O en la precisión del esquema de diferencia dividida central para la primera derivada
• Una suave introducción al análisis de complejidad de algoritmos