Notación O grande

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Notación que describe la limitación del comportamiento

Ejemplo de Big O notación:

{displaystyle {color {red}f(x)}in O{color {blue}(g(x))}}

como existe

0}" xmlns="http://www.w3.org/1998/Math/MathML">M■0{displaystyle M confidencial0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a7f423ab77b3411ec2803520a07c0dfae6ceb826" style="vertical-align: -0.338ex; width:6.703ex; height:2.176ex;"/>

(por ejemplo,

M=1

) y

x_{0}

(por ejemplo,

{displaystyle x_{0}=5}

{displaystyle {color {red}f(x)}leq {color {blue}Mg(x)}}

siempre

{displaystyle xgeq x_{0}}

La notación O grande es una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o infinito. Big O es miembro de una familia de notaciones inventadas por Paul Bachmann, Edmund Landau y otros, denominadas colectivamente notación de 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 grande se utiliza para clasificar los algoritmos según el tiempo de ejecución o los requisitos de espacio aumentan a medida que crece el tamaño de entrada. 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 según sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento asintótica se pueden representar usando la misma notación O. La letra O se 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, que utilizan los símbolos $o, Ω, ω$ y $Θ$ , para describir otros tipos de límites en las tasas de crecimiento asintótico.

Definición formal

Vamos $f$ , la función a estimar, ser una función valorada real o compleja y dejar $g$ , la función de comparación, ser una función real valorada. Que ambas funciones se definan en un subconjunto sin límites de los números reales positivos, y $g(x)$ ser estrictamente positivo para todos los valores suficientemente grandes $x$ . Uno escribe

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

f(x)

g(x)

x

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

M

x_{0}

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

En muchos contextos, la suposición de que estamos interesados en la tasa de crecimiento como variable $x$ va al infinito se deja sin estado, y uno escribe más simplemente que

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

La notación también se puede utilizar para describir el comportamiento de $f$ cerca de un número real $a$ (a menudo, $a=0$ ): diremos

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

delta

M

x

<math alttext="{displaystyle 0<|x-a|0.Silenciox- - aSilencio.δ δ {displaystyle 0 Seguido en silencio <img alt="{displaystyle 0<|x-a|

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

As $g(x)$ es elegido para ser estrictamente positivo para tales valores $x$ , ambas definiciones pueden ser unificadas usando el límite superior:

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

<math alttext="{displaystyle limsup _{xto a}{frac {left|f(x)right|}{g(x)}}lim supx→ → aSilenciof()x)Silenciog()x).JUEGO JUEGO .{displaystyle limsup _{xto a}{frac {lefttenciónf(x)right sometida}{g(x)}} {infty.}<img alt="{displaystyle limsup _{xto a}{frac {left|f(x)right|}{g(x)}}

Y en ambas definiciones el punto límite $a$ (Whether) $infty$ o no) es un punto de agrupación de los dominios de $f$ y $g$ en todos los barrios $a$ tiene que haber infinitamente muchos 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 ${displaystyle textstyle limsup _{xto a}}$ (al menos en la línea de números reales extendidos) siempre existe.

En la ciencia informática, una definición ligeramente más restrictiva es común: $f$ y $g$ ambos están obligados a ser funciones de algún subconjunto sin límites de los enteros positivos a los números reales no negativos; entonces ${displaystyle f(x)=O{bigl (}g(x){bigr)}}$ si existen números enteros positivos $M$ y $n_{0}$ tales que ${displaystyle f(n)leq Mg(n)}$ para todos ${displaystyle ngeq n_{0}}$ .

Ejemplo

En el uso típico, la notación $O$ es asintótica, es decir, se refiere a $x$ . En este escenario, la contribución de los términos que crecen "más rápido" eventualmente hará que los otros sean irrelevantes. En consecuencia, se pueden aplicar las siguientes reglas de simplificación:

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

Por ejemplo, sea $f (x) = 6 x 4 - 2 x 3 + 5$ , y supongamos que deseamos simplificar esta función, usando $O$ , para describir su tasa de crecimiento a medida que $x$ se acerca al infinito. Esta función es la suma de tres términos: $6 x 4$ , $-2 x 3$ y $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 $x$ , a saber, 6x⁴. Ahora se puede aplicar la segunda regla: $6 x 4$ es un producto de $6$ y $x 4$ en los que el primer factor no depende de $x$ . Omitir este factor da como resultado la forma simplificada $x 4$ . Por lo tanto, decimos que $f (x)$ es una "gran O" de $x 4$ . Matemáticamente, podemos escribir $f (x) = O (x 4)$ . Uno puede confirmar este cálculo usando la definición formal: let $f (x) = 6 x 4 - 2 x 3 + 5$ y $g (x) = x 4$ . Aplicando la definición formal anterior, la afirmación de que $f (x) = O (x 4)$ es equivalente a su expansión,

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

$x 0$ $M$ $x ■ x 0$ $x 0 = 1$ $M = 13$ $x ■ x 0$ ${displaystyle {begin{aligned}|6x^{4}-2x^{3}+5|&leq 6x^{4}+|2x^{3}|+5\&leq 6x^{4}+2x^{4}+5x^{4}\&=13x^{4}end{aligned}}}$ ${displaystyle |6x^{4}-2x^{3}+5|leq 13x^{4}.}$
Uso
La notación Big O tiene dos áreas principales de aplicación:
En matemáticas, se utiliza comúnmente para describir cómo una serie finita aproxima una función determinada, especialmente en el caso de una serie truncada de Taylor o expansión asintotica
En la ciencia informática, es útil en el análisis de algoritmos
En ambas aplicaciones, la función $g (x)$ que aparece dentro de $O (\cdot)$ normalmente se elige para que sea lo más simple posible, omitiendo factores constantes y términos de orden inferior.
Hay dos usos formalmente cercanos, pero notablemente diferentes, de esta notación:
infinito
Asintotismo infinitesimal.
Sin embargo, esta distinción es solo en aplicación y no en principio: la definición formal de la "gran O" es el mismo para ambos casos, solo que con diferentes límites para el argumento de la función.
Asintótica infinita

Gráficos de funciones utilizadas comúnmente en el análisis de algoritmos, mostrando el número de operaciones $N$ versus tamaño de entrada $n$ para cada función
La notación Big O es útil cuando se analiza la eficiencia de los algoritmos. Por ejemplo, el tiempo (o la cantidad de pasos) que lleva completar un problema de tamaño $n$ podría ser T(n) = 4n² − 2n + 2. A medida que $n$ crece, $n 2$ el término llegará a dominar, de modo que todos los demás términos pueden ignorarse; por ejemplo, cuando $n = 500$ , el término $4 n 2$ es 1000 veces más grande que $2 n$ té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 3$ o $n 4$ . Incluso si $T (n) = 1,000,000 n 2$ , si $U (n) = n 3$ , el último siempre superará al primero una vez que $n$ crezca más de $1,000,000$ ( $T (1 000 000) = 1 000 000 3 = U (1 000 000)$ ). Además, la cantidad de pasos depende de los detalles del modelo de máquina en el que se ejecuta el algoritmo, pero los diferentes tipos de máquinas suelen variar solo por un factor constante en la cantidad de pasos necesarios para ejecutar un algoritmo. Entonces, la notación O grande captura lo que queda: escribimos
${displaystyle T(n)=O(n^{2})}$
o
${displaystyle T(n)in O(n^{2})}$
y digamos que el algoritmo tiene orden de $n 2$ complejidad de tiempo. El signo " $=$ " no pretende expresar "es igual a" en su sentido matemático normal, sino más bien un 'es' más coloquial, por lo que la segunda expresión a veces se considera más precisa (consulte la discusión sobre el 'signo igual' a continuación) mientras que la primera se considera por algunos como un abuso de notación.
Asintótica infinitesimal
Gran O también se puede usar 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ño:
${displaystyle {begin{aligned}e^{x}&=1+x+{frac {x^{2}}{2!}}+{frac {x^{3}}{3!}}+{frac {x^{4}}{4!}}+dotsb &{text{for all }}x\[4pt]&=1+x+{frac {x^{2}}{2}}+O(x^{3})&{text{as }}xto 0\[4pt]&=1+x+O(x^{2})&{text{as }}xto 0end{aligned}}}$
La segunda expresión (la que tiene O(x³)) significa el valor absoluto del error e^x − (1 + x + x²/2) es a lo sumo algunos tiempos 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 mayor crecimiento determina el orden de $f (n)$ . Por ejemplo,
${displaystyle f(n)=9log n+5(log n)^{4}+3n^{2}+2n^{3}=O(n^{3})qquad {text{as }}nto infty.}$
En particular, si una función puede estar limitada por un polinomio en $n$ , entonces como $n$ tiende a infinito, uno puede ignorar los términos de orden inferior del polinomio. Los conjuntos $O (n c)$ y $O (c n)$ 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 n$ se llama subexponencial. Un algoritmo puede requerir un tiempo que sea 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 (registro(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, las exponenciales con diferentes bases no son del mismo orden. Por ejemplo, $2 n$ y $3 n$ no son del mismo orden.
Cambiar las unidades puede o no afectar el orden del algoritmo resultante. Cambiar unidades es equivalente a multiplicar la variable apropiada por una constante dondequiera que aparezca. Por ejemplo, si un algoritmo se ejecuta en el orden de $n 2$ , reemplazando el estilo $n$ por $cn$ significa que el algoritmo se ejecuta en el orden de $c 2 n 2$ , y la notación O grande ignora la constante $c 2$ . Esto se puede escribir como $c 2 n 2 = O(n 2)$ . Sin embargo, si un algoritmo se ejecuta en el orden de $2 n$ , reemplazando el estilo $n$ con $cn$ da $2 cn = (2 c) n$ . Esto no es equivalente a $2 n$ en general. El cambio de variables también puede afectar el orden del algoritmo resultante. Por ejemplo, si el tiempo de ejecución de un algoritmo es $O (n)$ cuando se mide en términos del número $n$ de dígitos de un número de entrada $x$ , entonces su tiempo de ejecución es $O (log x)$ cuando se mide como una función del número de entrada $x$ en sí 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})}$
$fcdot O(g)=O(fg)$
Suma
Si ${displaystyle f_{1}=O(g_{1})}$ y ${displaystyle f_{2}=O(g_{2})}$ entonces ${displaystyle f_{1}+f_{2}=O(max(g_{1},g_{2}))}$ . De ello se desprende que si ${displaystyle f_{1}=O(g)}$ y ${displaystyle f_{2}=O(g)}$ entonces ${displaystyle f_{1}+f_{2}in O(g)}$ . En otras palabras, esta segunda declaración dice que $O(g)$ es un cono convexo.
Multiplicación por una constante
Vamos $k$ ser una constante no cero. Entonces... ${displaystyle O(|k|cdot g)=O(g)}$ . En otras palabras, si ${displaystyle f=O(g)}$ , entonces ${displaystyle kcdot f=O(g).}$
Múltiples variables
Grande O (y poco o, Ω, etc.) también se puede utilizar con múltiples variables. Para definir grande O formalmente para múltiples variables, suponga $f$ y $g$ son dos funciones definidas en algún subconjunto $mathbb {R} ^{n}$ . Dijimos
${displaystyle f(mathbf {x}){text{ is }}O(g(mathbf {x}))quad {text{ as }}mathbf {x} to infty }$
si y sólo si existen constantes $M$ y $0}" xmlns="http://www.w3.org/1998/Math/MathML">C■0{displaystyle C confiar0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c84d4126c6df243734f9355927c026df6b0d3859" style="vertical-align: -0.338ex; width:6.027ex; height:2.176ex;"/>$ tales que ${displaystyle |f(mathbf {x})|leq C|g(mathbf {x})|}$ para todos $mathbf {x}$ con ${displaystyle x_{i}geq M}$ para algunos $i.$ Equivalentemente, la condición de que $x_{i}geq M$ para algunos $i$ puede ser escrito ${displaystyle |mathbf {x} |_{infty }geq M}$ , donde ${displaystyle |mathbf {x} |_{infty }}$ denota la norma Chebyshev. Por ejemplo, la declaración
${displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)quad {text{ as }}n,mto infty }$
afirma que existen constantes C y M tales que
${displaystyle |f(n,m)-(n^{2}+m^{3})|leq C|n+m|}$
cada vez ${displaystyle mgeq M}$ o ${displaystyle ngeq M}$ sostiene. Esta definición permite todas las coordenadas de $mathbf {x}$ aumentar a infinito. En particular, la declaración
${displaystyle f(n,m)=O(n^{m})quad {text{ as }}n,mto infty }$
(es decir, ${displaystyle exists C,exists M,forall n,forall m,cdots }$ ) es bastante diferente de
${displaystyle forall mcolon ~f(n,m)=O(n^{m})quad {text{ as }}nto infty }$
(es decir, ${displaystyle forall m,exists C,exists M,forall n,cdots }$ ).
De acuerdo con esta definición, el subconjunto en el que se define una función es significativo cuando se generalizan las declaraciones de la configuración univariada al entorno multivariable. Por ejemplo, si ${displaystyle f(n,m)=1}$ y ${displaystyle g(n,m)=n}$ , entonces ${displaystyle f(n,m)=O(g(n,m))}$ si restringimos $f$ y $g$ a ${displaystyle [1,infty)^{2}}$ , pero no si se definen en ${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.
Cuestiones de notación
Signo igual
La declaración "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 declaración no tiene. Como dice de Bruijn, O(x) = O(x²) es cierto pero O(x²) = O(x) no lo es. Knuth describe declaraciones 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²)." En otra carta, Knuth también señaló que "el signo de igualdad no es simétrico con respecto a tales notaciones", ya que, en esta notación, "los matemáticos suelen usar el signo = como usan la palabra & #34;es" en español: Aristóteles es un hombre, pero un hombre no es necesariamente Aristóteles.
Por estas razones, sería más preciso usar la notación de conjuntos y escribir f(x) ∈ O(g(x)) (léase como: "f(x) es un elemento de O(g(x))", o &# 34;f(x) está en el conjunto O(g(x))"), pensando en O(g(x)) como la clase de todos funciones h(x) tales que |h(x)| ≤ C|g(x)| para alguna constante C. Sin embargo, el uso del signo igual es habitual.
Otros operadores aritméticos
La notación Big O también se puede usar 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 se limita 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 en un conjunto de n elementos. Sus desarrolladores están interesados en encontrar una función T(n) que exprese cuánto tardará en ejecutarse el algoritmo (en alguna medida de tiempo arbitraria) en términos del número de elementos en el conjunto de entrada. El algoritmo funciona llamando primero a una subrutina para ordenar los elementos del conjunto y luego realizar sus propias operaciones. La clasificación tiene una complejidad de tiempo conocida de O(n²), y después de que se ejecuta la subrutina, el algoritmo debe tomar una 55n³ + 2n + 10 pasos antes de que termine. Por lo tanto, la complejidad temporal general del algoritmo se puede expresar como T(n) = 55n³ + O(n²). Aquí los términos 2n + 10 se subsumen dentro de O(n) de crecimiento más rápido ²). Nuevamente, este uso ignora parte del significado formal de "=" símbolo, pero permite usar la notación O grande como una especie de marcador de posición conveniente.
Múltiples usos
En uso más complicado, O(·) puede aparecer en diferentes lugares en una ecuación, incluso varias veces a cada lado. Por ejemplo, los siguientes son verdaderos $nto 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}}}$ cualquieraOalgunosOfnOgnOeⁿn^f()n)gnn^O1) = O()eⁿ)O()eⁿ) n^O1)
Composición tipográfica
Grande O es tipología como una maleta superior italicizada "O", como en el siguiente ejemplo: $O(n^{2})$ . En TeX, se produce simplemente escribiendo O en modo matemático. A diferencia de las notaciones de Bachmann-Landau, no necesita ningún símbolo especial. Sin embargo, algunos autores utilizan la variante caligráfica ${mathcal {O}}$ en su lugar.
Órdenes de funciones 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 y n crece sin límite. Las funciones de crecimiento más lento generalmente se enumeran primero.
Notación Nombre Ejemplo
$O(1)$ constante Determinar si un número binario es uniforme o extraño; Calcular $(-1)^{n}$ ; Usando una mesa de búsqueda de tamaño constante
$O(log log n)$ doble logarítmica Número medio de comparaciones gastadas encontrando un artículo usando búsqueda de interpolación en un conjunto de valores distribuidos uniformemente
$O(log n)$ logaritmic Encontrar un artículo en un array ordenados con una búsqueda binaria o un árbol de búsqueda equilibrado, así como todas las operaciones en un montón binomio
${displaystyle O((log n)^{c})}$
$1}" xmlns="http://www.w3.org/1998/Math/MathML">c■1{textstyle c]1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9057ec1c55def34aa105650bfe9491240553d160" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$ polilogarítmica Ordenación de cadena de matriz se puede resolver en el tiempo polilogarítmico en una máquina de acceso aleatorio paralelo.
$O(n^{c})$
$<math alttext="{textstyle 0<c0.c.1{textstyle 0 se hizo realidad <img alt="{textstyle 0<c$ poder fraccional Búsqueda en un árbol k-d
$O(n)$ lineal Encontrar un artículo en una lista sin surtido o en un array sin surtido; añadir dos n-bit enteros por carga ondulada
${displaystyle O(nlog ^{*}n)}$ n Log-star n Realizar triangulación de un simple polígono usando el algoritmo de Seidel, o el algoritmo de unión-encontrado. Note que $1end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">logAlternativa Alternativa ⁡ ⁡ ()n)={}0,sin≤ ≤ 11+logAlternativa Alternativa ⁡ ⁡ ()log⁡ ⁡ n),sin■1{displaystyle log ^{*}(n)={begin{cases}0, reducida{text{if }nleq 11+log ^{*}(log n), limit{text{if }nend{cases}}}}}}}}}1end{cases}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a8ce0b95ab4bdc244b0ad464677f1709df7c562" style="vertical-align: -2.505ex; width:37.979ex; height:6.176ex;"/>$
${displaystyle O(nlog n)=O(log n!)}$ linearithmic, loglinear, quasilinear, or "n log n" Realización de una rápida transformación Fourier; tipo de comparación más rápido posible; heapsort y combinar tipo
$O(n^{2})$ quadratic Multiplicando dos n- números de dígitos por multiplicación de libros escolares; algoritmos de clasificación simples, tales como burbujas, tipo de selección y tipo de inserción; (caso peor) ligados a algunos algoritmos de clasificación generalmente más rápidos como el surtido rápido, Shellsort y tipo de árbol
$O(n^{c})$ polinomio o algebraico Prótesis de gramática conjunción de árboles; ajuste máximo para gráficos bipartitos; encontrar el determinante con LU descomposición
${displaystyle L_{n}[alphac]=e^{(c+o(1))(ln n)^{alpha }(ln ln n)^{1-alpha }}}$
$<math alttext="{textstyle 0<alpha 0.α α .1{textstyle 0 0 0 0. <img alt="{textstyle 0<alpha$ L-notation or sub-exponential Factorización de un número utilizando el tamiz cuadrático o el sieve de campo número
$O(c^{n})$
$1}" xmlns="http://www.w3.org/1998/Math/MathML">c■1{textstyle c]1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9057ec1c55def34aa105650bfe9491240553d160" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$ exponencial Encontrar la solución (exacta) al problema del vendedor que viaja utilizando programación dinámica; determinar si dos declaraciones lógicas son equivalentes mediante búsqueda de fuerza bruta
$O(n!)$ factorial Resolver el problema de los vendedores itinerantes mediante la búsqueda de fuerza bruta; generar todas las permutaciones no restringidas de una pose; encontrar el determinante con la expansión de Laplace; enumerar todas las particiones de un conjunto
La declaración ${displaystyle f(n)=O(n!)}$ a veces se debilita ${displaystyle f(n)=Oleft(n^{n}right)}$ para obtener fórmulas más simples para la complejidad asintotica. Para cualquier $0}" xmlns="http://www.w3.org/1998/Math/MathML">k■0{displaystyle k]0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27b3af208b148139eefc03f0f80fa94c38c5af45" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;"/>$ y $0}" xmlns="http://www.w3.org/1998/Math/MathML">c■0{displaystyle c]0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$ , $O(n^{c}(log n)^{k})$ es un subconjunto de ${displaystyle O(n^{c+varepsilon })}$ para cualquier $0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/>$ , así se puede considerar como un polinomio con algún orden más grande.
Notaciones asintóticas relacionadas
Big O es ampliamente utilizado en informática. Junto con algunas otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau.
Notación de o pequeña
Intuitivamente, la afirmación " $f (x)$ es $o (g (x))$ " (léase " $f (x)$ es la pequeña o de $g (x)$ ") significa que $g (x)$ crece mucho más rápido que $f (x)$ . Como antes, sea f una función de valor real o complejo y g una función de valor real, ambas definidas en algún subconjunto ilimitado de 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 }}xto infty }$
si por cada constante positiva $ε$ existe una constante $x_{0}$ tales que
${displaystyle |f(x)|leq varepsilon g(x)quad {text{ for all }}xgeq x_{0}.}$
Por ejemplo, uno tiene
${displaystyle 2x=o(x^{2})}$ y ${displaystyle 1/x=o(1),}$ ambos ${displaystyle xto infty.}$
La diferencia entre la definición de la notación grande-O y la definición de little-o es que mientras que la primera tiene que ser verdadera para al menos uno constante M, este último debe esperar cada uno constante positiva $ε$ , por pequeño que sea. De esta manera, la pequeña notación hace una más firme declaración que la notación de gran-O correspondiente: cada función que es poco-o de g es también grande-O de g, pero no todas las funciones que son grandes g también es poco-o de g. Por ejemplo, ${displaystyle 2x^{2}=O(x^{2})}$ pero ${displaystyle 2x^{2}neq o(x^{2})}$ .
As g()x) es no cero, o al menos se convierte en no cero más allá de cierto punto, la relación ${displaystyle f(x)=o(g(x))}$ equivale a
${displaystyle lim _{xto infty }{frac {f(x)}{g(x)}}=0}$ (y esto es de hecho cómo Landau definió originalmente la pequeña notación).
Little-o respeta una serie de operaciones aritméticas. Por ejemplo,
si $c$ es una constante no cero y ${displaystyle f=o(g)}$ entonces ${displaystyle ccdot f=o(g)}$ , y
si ${displaystyle f=o(F)}$ y ${displaystyle g=o(G)}$ entonces ${displaystyle fcdot g=o(Fcdot G).}$
También satisface una relación de transitividad:
si ${displaystyle f=o(g)}$ y ${displaystyle g=o(h)}$ entonces ${displaystyle f=o(h).}$
Notación Big Omega
Otra notación asintotica es $Omega$ , lee "grande omega". Hay dos definiciones generalizadas e incompatibles de la declaración
$f(x)=Omega (g(x))$ como $xto 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 vecindario.
La definición de Hardy-Littlewood se usa 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 Godfrey Harold Hardy y John Edensor Littlewood presentaron el nuevo símbolo $Omega$ , que se define como sigue:
${displaystyle f(x)=Omega (g(x))}$ como $xto infty$ si $0.}" xmlns="http://www.w3.org/1998/Math/MathML">lim supx→ → JUEGO JUEGO Silenciof()x)g()x)Silencio■0.{displaystyle limsup _{xto infty }left forever{frac {f(x)}{g(x)}}right perpetua0.}0.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f02693ebc49fda74d24532947d3ec8ad39161c0f" style="vertical-align: -2.671ex; width:18.961ex; height:6.509ex;"/>$
Así $f(x)=Omega (g(x))$ es la negación de $f(x)=o(g(x))$ .
En 1916 los mismos autores presentaron los dos nuevos símbolos $Omega _{R}$ y $Omega _{L}$ , definido como:
$f(x)=Omega _{R}(g(x))$ como $xto infty$ si $0}" xmlns="http://www.w3.org/1998/Math/MathML">lim supx→ → JUEGO JUEGO f()x)g()x)■0{displaystyle limsup _{xto infty }{frac {f(x)}{g(x)}] 0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5c07767c7745ce1d57ae0684265036fe6542f232" style="vertical-align: -2.671ex; width:17.02ex; height:6.509ex;"/>$ ;
$f(x)=Omega _{L}(g(x))$ como $xto infty$ si $<math alttext="{displaystyle liminf _{xto infty }{frac {f(x)}{g(x)}}lim infx→ → JUEGO JUEGO f()x)g()x).0.{displaystyle liminf _{xto infty }{frac {f(x)}{g(x)}}} {0}}<img alt="{displaystyle liminf _{xto infty }{frac {f(x)}{g(x)}}$
Estos símbolos fueron utilizados por Edmund Landau, con los mismos significados, en 1924. Después de Landau, las notaciones nunca se utilizaron de nuevo exactamente así; $Omega _{R}$ se convirtió en $Omega _{+}$ y $Omega _{L}$ se convirtió en $Omega _{-}$ .
Estos tres símbolos $OmegaOmega _{+},Omega _{-}$ , así como $f(x)=Omega _{pm }(g(x))$ (que significa que $f(x)=Omega _{+}(g(x))$ y $f(x)=Omega _{-}(g(x))$ son ambos satisfechos), se utilizan actualmente en la teoría de números analíticos.
Ejemplos simples
Tenemos
${displaystyle sin x=Omega (1)}$ como ${displaystyle xto infty}$
y más precisamente
${displaystyle sin x=Omega _{pm }(1)}$ como $xto infty.$
Tenemos
${displaystyle sin x+1=Omega (1)}$ como ${displaystyle xto infty}$
y más precisamente
${displaystyle sin x+1=Omega _{+}(1)}$ como ${displaystyle xto infty;}$
sin embargo
${displaystyle sin x+1not =Omega _{-}(1)}$ como $xto infty.$
La definición de Knuth
En 1976 Donald Knuth publicó un documento para justificar su uso del $Omega$ - Símbolo para describir una propiedad más fuerte. Knuth escribió: "Para todas las aplicaciones que he visto hasta ahora en la informática, un requisito más fuerte... es mucho más apropiado". Definió
$f(x)=Omega (g(x))Leftrightarrow g(x)=O(f(x))$
con el comentario: "Aunque he cambiado la definición de Hardy y Littlewood $Omega$ , Me siento justificado al hacerlo porque su definición no es de ningún modo en uso amplio, y porque hay otras maneras de decir lo que quieren decir en los casos comparativamente raros cuando su definición se aplica."
Familia de notaciones de Bachmann-Landau
Notación Nombre Descripción Definición formal Definición
$f(n)=o(g(n))$ Pequeña O; Pequeña Oh $f$ está dominado por $g$ asintotically $0,exists n_{0},forall n>n_{0}colon |f(n)|О О k■0∃ ∃ n0О О n■n0:: Silenciof()n)Silencio.kg()n){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}0,exists n_{0},forall n>n_{0}colon |f(n)|$ ${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=0}$
$f(n)=O(g(n))$ Big O; Big Oh; Big Omicron $|f|$ está obligado por encima $g$ (hasta el factor constante) asintotípicamente $0,exists n_{0},forall n>n_{0}colon |f(n)|leq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0∃ ∃ n0О О n■n0:: Silenciof()n)Silencio≤ ≤ kg()n){displaystyle exists k Conf0,exists n_{0},forall no confían_{0}colon Silenciof(n)0,exists n_{0},forall n>n_{0}colon |f(n)|leq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16115602291a322030d1f83eaa012a3e8f11e10d" style="vertical-align: -0.838ex; width:35.342ex; height:2.843ex;"/>$ $<math alttext="{displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}}lim supn→ → JUEGO JUEGO f()n)g()n).JUEGO JUEGO {displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}} {infty }} {infty }<img alt="{displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}}$
$f(n)=Theta (g(n))$ Big Theta $f$ está obligado tanto por encima como por debajo $g$ asintotically $0,exists k_{2}>0,exists n_{0},forall n>n_{0}colon }" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k1■0∃ ∃ k2■0∃ ∃ n0О О n■n0:: {displaystyle exists k_{1} {0},exists k_{2}] confianza0,exists n_{0},forall n título0,exists k_{2}>0,exists n_{0},forall n>n_{0}colon }" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/be379e6bea41362b562f8783c99e54cc4b716ca2" style="vertical-align: -0.671ex; width:29.422ex; height:2.509ex;"/>$ ${displaystyle k_{1},g(n)leq f(n)leq k_{2},g(n)}$ $f(n)=O(g(n))$ y $f(n)=Omega (g(n))$ (Versión numérica)
${displaystyle f(n)sim g(n)}$ Por orden de $f$ es igual a $g$ asintotically $0,exists n_{0},forall n>n_{0}colon left|{frac {f(n)}{g(n)}}-1right|О О ε ε ■0∃ ∃ n0О О n■n0:: Silenciof()n)g()n)− − 1Silencio.ε ε {displaystyle forall varepsilon √0,exists n_{0},forall n títulon_{0}colon left sometida{frac {f(n)}{g(n)}}}-1derechactamente escuchadavarepsilon }0,exists n_{0},forall n>n_{0}colon left|{frac {f(n)}{g(n)}}-1right|$ ${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=1}$
$f(n)=Omega (g(n))$ Gran Omega en la teoría de la complejidad (Knuth) $f$ se vincula a continuación $g$ asintotically $0,exists n_{0},forall n>n_{0}colon f(n)geq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0∃ ∃ n0О О n■n0:: f()n)≥ ≥ kg()n){displaystyle exists k título0,exists n_{0},forall no confían_{0}colon f(n)geq k,g(n)}0,exists n_{0},forall n>n_{0}colon f(n)geq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb5154c98624eb114e71485abb7ec1396d157e6a" style="vertical-align: -0.838ex; width:34.048ex; height:2.843ex;"/>$ $0}" xmlns="http://www.w3.org/1998/Math/MathML">lim infn→ → JUEGO JUEGO f()n)g()n)■0{displaystyle liminf _{nto infty }{frac {f(n)}{g(n)} {n]} {f}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9e629f09dbf872b91187297980c2e624d58a54" style="vertical-align: -2.671ex; width:16.235ex; height:6.509ex;"/>$
$f(n)=omega (g(n))$ Pequeña Omega $f$ dominados $g$ asintotically $0,exists n_{0},forall n>n_{0}colon f(n)>k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">О О k■0∃ ∃ n0О О n■n0:: f()n)■kg()n){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}0,exists n_{0},forall n>n_{0}colon f(n)>k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b016c45b28b07815ff7f1e86ce09064f61057faf" style="vertical-align: -0.838ex; width:34.048ex; height:2.843ex;"/>$ ${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=infty }$
$f(n)=Omega (g(n))$ Gran Omega en la teoría de números (Hardy-Littlewood) $|f|$ no está dominado por $g$ asintotically $0,forall n_{0},exists n>n_{0}colon |f(n)|geq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0О О n0∃ ∃ n■n0:: Silenciof()n)Silencio≥ ≥ kg()n){displaystyle exists k confía0,forall n_{0},exists n confían_{0}colon Silenciof(n)0,forall n_{0},exists n>n_{0}colon |f(n)|geq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee1de6bf9135e3729da954f9a7e35225a1689c31" style="vertical-align: -0.838ex; width:35.342ex; height:2.843ex;"/>$ $0}" xmlns="http://www.w3.org/1998/Math/MathML">lim supn→ → JUEGO JUEGO Silenciof()n)Silenciog()n)■0{displaystyle limsup _{nto infty }{frac {left habitf(n)right sobre la vida}{g(n)}} {}}}}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6fd52d75e1283fbf16cee8ade84c95a94b39e776" style="vertical-align: -2.671ex; width:18.379ex; height:6.509ex;"/>$
Las definiciones límite suponen $0}" xmlns="http://www.w3.org/1998/Math/MathML">g()n)■0{displaystyle g(n)}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59f58b017ed2f12e925640328d716644bced11d4" style="vertical-align: -0.838ex; width:8.581ex; height:2.843ex;"/>$ suficientemente grande $n$ . La tabla está (en parte) clasificada de la más pequeña a la más grande, en el sentido de que ${displaystyle o,O,Thetasim}$ (Versión de Knuth) ${displaystyle Omegaomega }$ en funciones corresponden a $<math alttext="{displaystyle .,\leq \leq ,.. ,=,{displaystyle ■,leqapprox=,} <img alt="{displaystyle$ $}" xmlns="http://www.w3.org/1998/Math/MathML">≥ ≥ ,■{displaystyle geq confianza}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d0adc8772efbceb6ee25889368c7e0b08c1abf8" style="vertical-align: -0.671ex; width:4.65ex; height:2.343ex;"/>$ en la línea real (la versión Hardy-Littlewood de ${displaystyle Omega }$ , sin embargo, no corresponde a tal descripción).
La ciencia informática utiliza el gran ${displaystyle O}$ , grande Theta ${displaystyle Theta }$ , poco ${displaystyle o}$ , pequeña omega ${displaystyle omega }$ y la gran Omega de Knuth ${displaystyle Omega }$ notaciones. La teoría del número analítico a menudo utiliza el grande ${displaystyle O}$ , pequeño ${displaystyle o}$ , Hardy-Littlewood grande Omega ${displaystyle Omega }$ (con o sin los subscriptos +, − o ±) y $sim$ notaciones. La pequeña omega ${displaystyle omega }$ la notación no se utiliza tan a menudo en el análisis.
Uso en informática
De manera informal, especialmente en informática, la notación O grande a menudo se puede usar de manera algo diferente para describir un límite estrecho asintótico donde usar la notación Theta Θ grande podría ser más apropiado en un contexto dado. Por ejemplo, al considerar una función T(n) = 73n³ + 22n² + 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 preferirse a los límites más flexibles (como el número 1 a continuación).
T()n) O()n¹⁰⁰)
T()n) O()n³)
T()n.n³)
Las declaraciones equivalentes en inglés son respectivamente:
T()n) crece asintoticamente no más rápido que n¹⁰⁰
T()n) crece asintoticamente no más rápido que n³
T()n) crece asintoticamente tan rápido como n³.
Entonces, si bien las tres afirmaciones son verdaderas, cada una contiene progresivamente más información. En algunos campos, sin embargo, la notación O grande (número 2 en las listas anteriores) se usaría 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ía estar más inclinado a poner un límite asintótico superior sobre cuánto 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 (nto 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}}~0leq f(n)leq cg(n){text{ for all }}ngeq n_{0}}.}$
Los autores afirman que el uso del operador de igualdad (=) para denotar la pertenencia a un conjunto en lugar del operador de pertenencia al conjunto (∈) es un abuso de la notación, pero que hacerlo tiene ventajas. 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 los elementos no esenciales. desorden en las ecuaciones, por ejemplo:
${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 Õ (léase soft-O): f(n) = Õ(g(n)) es la abreviatura de f(n) = O(g(n) registro^k n ) por algo de k. Algunos autores escriben O^* con el mismo propósito. Esencialmente, es 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 el más fino. -efectos puntuales aportados por el (los) factor(es) 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 limitadas para los asuntos en cuestión (dado que log^k n siempre es o(n^ε) para cualquier constante k y cualquier ε > 0).
También la notación L, definida como
${displaystyle L_{n}[alphac]=e^{(c+o(1))(ln n)^{alpha }(ln ln n)^{1-alpha }}}$
es conveniente para las funciones que están entre polinomio y exponencial en términos de $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. 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 usar para definir derivadas y diferenciabilidad en espacios bastante generales, y también (asintótica) equivalencia de funciones,
$fsim giff (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)" desde arriba. (Se reduce a lim f / g = 1 si f y g son funciones de valor real positivo.) Para ejemplo, 2x es Θ(x), pero 2x − x no es o(x).
Historia (notaciones de Bachmann–Landau, Hardy y Vinogradov)
El símbolo O fue introducido por el teórico número Paul Bachmann en 1894, en el segundo volumen de su libro Analytische Zahlentheorie ("teoría de números análicos"). El teórico número Edmund Landau lo adoptó, y por lo tanto se inspiró en introducir en 1909 la notación o; por lo tanto, ambos se llaman símbolos Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintotico. El símbolo $Omega$ (en el sentido "no es un o de") fue presentado en 1914 por Hardy y Littlewood. Hardy y Littlewood también introducido en 1916 los símbolos $Omega _{R}$ ("derecho") y $Omega _{L}$ ("izquierda"), precursores de los símbolos modernos $Omega _{+}$ ("no es más pequeño que un pequeño o de") y $Omega _{-}$ ("no es más grande que un pequeño o de"). Así, los símbolos Omega (con sus significados originales) a veces también se denominan "símbolos de Landau". Esta notación $Omega$ se usó comúnmente en la teoría de números al menos desde la década de 1950. En la década de 1970 el gran O fue popularizado 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.
Landau nunca usó los símbolos theta grande y omega pequeño.
Los símbolos de Hardy eran (en términos de la notación O moderna)
${displaystyle fpreccurlyeq giff fin O(g)}$ y $fprec giff fin o(g);$
(Hardy sin embargo nunca definió o utilizó la notación $prec !!prec$ , ni $ll$ , como se ha informado a veces). Hardy introdujo los símbolos $preccurlyeq$ y $prec$ (así como algunos otros símbolos) en su tracto de 1910 "Orders of Infinity", e hizo uso de ellos sólo en tres papeles (1910-1913). En sus casi 400 documentos y libros restantes utilizó sistemáticamente los símbolos de Landau O y o.
La notación de Hardy ya no se utiliza. Por otro lado, en la década de 1930, el teórico ruso Ivan Matveyevich Vinogradov introdujo su notación $ll$ , que se ha utilizado cada vez más en la teoría de números en lugar de la $O$ notación. Tenemos
$fll giff fin 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 llaman nunca 'Omicron'. El símbolo fue visto mucho más tarde (1976) por Knuth como un omicrón mayúscula, probablemente en referencia a su definición del símbolo Omega. No se debe usar el dígito cero.
Referencias y notas
^ a b Bachmann, Paul (1894). Analytische Zahlentheorie [Número analítico Teoría] (en alemán). Vol. 2. Leipzig: Teubner.
^ a b Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Manual sobre la teoría de la distribución de los primos] (en alemán). Leipzig: B. G. Teubner. p. 883.
^ Mohr, Austin. "Cuantum Computing in Complexity Theory and Theory of Computation" (PDF). p. 2. Archivado (PDF) del original el 8 de marzo de 2014. Retrieved 7 de junio 2014.
^ Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Manual sobre la teoría de la distribución de los primos] (en alemán). Leipzig: B.G. Teubner. p. 31.
^ Michael Sipser (1997). Introducción a la teoría de la computación. Boston/MA: PWS Publishing Co. Aquí: Def.7.2, p.227
^ a b Cormen,Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3a edición). Cambridge/MA: MIT Press. p. 45. ISBN 978-0-262-53305-8. Porque... Silencio()g()n) es un conjunto, podríamos escribir "f()n) Silencio()g()n)" para indicar que f()n) es un miembro de Silencio()g()n)). En lugar de eso, normalmente escribiremos f()n) Silencio()g()n)) para expresar la misma noción. Usted podría estar confundido porque abusamos de la igualdad de esta manera, pero veremos más adelante en esta sección que hacerlo tiene sus ventajas.
^ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introducción a los algoritmos (Tercera edición). MIT. pág. 53.
^ Howell, Rodney. "En la notación asintotica con múltiples variables" (PDF). Archivado (PDF) del original en 2015-04-24. Retrieved 2015-04-23.
^ a b N. G. de Bruijn (1958). Métodos asintoticos en Análisis. Amsterdam: North-Holland. pp. 5–7. ISBN 978-0-486-64221-5. Archivado desde el original el 2023-01-17. Retrieved 2021-09-15.
^ a b c Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). Matemáticas concretas (2 ed.). Reading, Massachusetts: Addison–Wesley. p. 446. ISBN 978-0-201-55802-9. Archivado desde el original el 2023-01-17. Retrieved 2016-09-23.
^ Donald Knuth (junio a julio de 1998). "Teach Calculus con Big O" (PDF). Avisos de la Sociedad Americana de Matemáticas. 45 (6): 687. (PDF) del original el 2021-10-14. Retrieved 2021-09-05. (versión sin puente Archivado 2008-05-13 en la máquina Wayback)
^ 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.
^ Ronald L. Graham, Donald E. Knuth y Oren Patashnik, Matemáticas concretas: Fundación para la Ciencia de la Computación (2a edición)., Addison-Wesley, 1994. Sección 9.2, pág. 443.
^ Sivaram Ambikasaran y Eric Darve, An ${displaystyle {mathcal {O}}(Nlog N)}$ Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices, J. Computación científica 57 (2013), No. 3, 477-501.
^ Saket Saurabh y Meirav Zehavi, $(k,n-k)$ -Max-Cut: An ${displaystyle {mathcal {O}}^{*}(2^{p})}$ - Algoritmo de tiempo y un núcleo polinomio, Algorithmica 80 (2018), 12, 3844–3860.
^ a b Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Manual sobre la teoría de la distribución de los primos] (en alemán). Leipzig: B. G. Teubner. p. 61.
^ Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition, Ch. 3.1 Archived 2009-01-16 at the Wayback Machine
^ Cormen TH, Leiserson CE, Rivest RL, Stein C (2009). Introducción a algoritmos (3rd ed.). Cambridge, Mass.: MIT Press. p. 48. ISBN 978-0-262-27083-0. OCLC 676697295.
^ a b c Hardy, G. H.; Littlewood, J. E. (1914). "Algunos problemas de aproximación diofantina: Parte II. La serie trigonométrica asociada a las funciones elípticas θ". Acta Mathematica. 37: 225. doi:10.1007/BF02401834. Archivado desde el original en 2018-12-12. Retrieved 2017-03-14.
^ a b G. H. Hardy y J. E. Littlewood, « Contribución a la teoría de la función Riemann zeta y la teoría de la distribución de los primos », Acta Mathematica, vol. 41, 1916.
^ E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Matemáticas. Kl. 1924, 137–150.
^ a b Aleksandar Ivić. La función de Riemann zeta, capítulo 9. John Wiley ' Sons 1985.
^ Gérald Tenenbaum, Introducción a la teoría analítica y probabilística del número, Capítulo I.5. American Mathematical Society, Providence RI, 2015.
^ a b c d e f Knuth, Donald (abril a junio de 1976). "Gran Omicron y gran Omega y gran Theta" (PDF). SIGACT Noticias. 8 (2): 18–24. doi:10.1145/1008328.1008329. S2CID 5230246. Archivado desde el original el 2022-04-08. Retrieved 2022-12-08.{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
^ Balcázar, José L.; Gabarró, Joaquim. Clases de complejidad no uniformes especificadas por límites inferiores y superiores (PDF). RAIRO – Teoretical Informatics and Applications – Informatique Théorique et Applications. 23 (2): 180. ISSN 0988-3754. Archivado (PDF) del original el 14 marzo 2017. Retrieved 14 de marzo 2017.
^ Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, y otras comparaciones". Condición: Geometría de los algoritmos numéricos. Berlín, Heidelberg: Springer. pp. 467-468. doi:10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
^ a b Vitányi, Paul; Meertens, Lambert (abril de 1985). "Big Omega contra las funciones salvajes" (PDF). ACM SIGACT Noticias. 16 (4): 56–59. CiteSeerX10.1.1.694.3072. doi:10.1145/382242.382835. S2CID 11700420. Archivado (PDF) del original en 2016-03-10. Retrieved 2017-03-14.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introducción a los algoritmos (2a edición). MIT Press and McGraw-Hill. pp. 41–50. ISBN 0-262-03293-7.
^ por ejemplo se omite en: Hildebrand, A.J. "Notaciones sintomáticas" (PDF). Departamento de Matemáticas. Métodos asintoticos en el análisis. Matemáticas 595, otoño 2009. Urbana, IL: Universidad de Illinois. Archivado (PDF) del original el 14 marzo 2017. Retrieved 14 de marzo 2017.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3a edición). Cambridge/MA: MIT Press. p. 47. ISBN 978-0-262-53305-8. Cuando sólo tenemos un límite superior asintotico, utilizamos O-notación. Para una función determinada g()n), denotamos O()g()n) (pronunciado "grande-oh de g de no a 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 todos n ≥ n₀}
^ Cormen,Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Introducción a los algoritmos (3a edición). Cambridge/MA: MIT Press. p. 49. ISBN 978-0-262-53305-8. Cuando la notación asintotica permanece 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 a la membresía fija: n²). En general, sin embargo, cuando la notación asintotica aparece en una fórmula, la interpretamos como de pie para alguna función anónima que no nos importa nombrar. Por ejemplo, la fórmula 2n² + 3n + 1 = 2n² + Silencio()n) significa que 2n² + 3n + 1 = 2n² + f()n), donde f()n) es una función en el conjunto Silencio()n). En este caso, dejamos que f()n) = 3n + 1, que es en efecto Silencio()n). Utilizar la notación asintotica de esta manera puede ayudar a eliminar el detalle inesencial y el desorden en una ecuación.
^ Introducción a algoritmos. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. p. 63. ISBN 978-0-262-27083-0. OCLC 676697295.{{cite book}}: CS1 maint: others (link)
^ Andreas Björklund y Thore Husfeldt y Mikko Koivisto (2009). "Seguir partición a través de la inclusión" (PDF). SIAM Journal on Computing. 39 (2): 546–563. doi:10.1137/070683933. Archivado (PDF) del original el 2022-02-03. Retrieved 2022-02-03. See sect.2.3, p.551.
^ Erdelyi, A. (1956). Expansions asintotic. ISBN 978-0-486-60318-6.
^ E. C. Titchmarsh, The The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
^ Vea por ejemplo "Una nueva estimación para G()n) en el problema de Waring" (ruso). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Traducido en inglés en: Obras seleccionadas / Ivan Matveevič Vinogradov; preparado por el Steklov Mathematical Institute de la Academia de Ciencias de la URSS con motivo de su 90 cumpleaños. Springer-Verlag, 1985.

Notación	Nombre	Ejemplo
$O(1)$	constante	Determinar si un número binario es uniforme o extraño; Calcular $(-1)^{n}$ ; Usando una mesa de búsqueda de tamaño constante
$O(log log n)$	doble logarítmica	Número medio de comparaciones gastadas encontrando un artículo usando búsqueda de interpolación en un conjunto de valores distribuidos uniformemente
$O(log n)$	logaritmic	Encontrar un artículo en un array ordenados con una búsqueda binaria o un árbol de búsqueda equilibrado, así como todas las operaciones en un montón binomio
${displaystyle O((log n)^{c})}$ $1}" xmlns="http://www.w3.org/1998/Math/MathML">c■1{textstyle c]1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9057ec1c55def34aa105650bfe9491240553d160" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$	polilogarítmica	Ordenación de cadena de matriz se puede resolver en el tiempo polilogarítmico en una máquina de acceso aleatorio paralelo.
$O(n^{c})$ $<math alttext="{textstyle 0<c0.c.1{textstyle 0 se hizo realidad <img alt="{textstyle 0<c$	poder fraccional	Búsqueda en un árbol k-d
$O(n)$	lineal	Encontrar un artículo en una lista sin surtido o en un array sin surtido; añadir dos n-bit enteros por carga ondulada
${displaystyle O(nlog ^{*}n)}$	n Log-star n	Realizar triangulación de un simple polígono usando el algoritmo de Seidel, o el algoritmo de unión-encontrado. Note que $1end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">logAlternativa Alternativa ⁡ ⁡ ()n)={}0,sin≤ ≤ 11+logAlternativa Alternativa ⁡ ⁡ ()log⁡ ⁡ n),sin■1{displaystyle log ^{}(n)={begin{cases}0, reducida{text{if }nleq 11+log ^{}(log n), limit{text{if }nend{cases}}}}}}}}}1end{cases}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a8ce0b95ab4bdc244b0ad464677f1709df7c562" style="vertical-align: -2.505ex; width:37.979ex; height:6.176ex;"/>$
${displaystyle O(nlog n)=O(log n!)}$	linearithmic, loglinear, quasilinear, or "n log n"	Realización de una rápida transformación Fourier; tipo de comparación más rápido posible; heapsort y combinar tipo
$O(n^{2})$	quadratic	Multiplicando dos n- números de dígitos por multiplicación de libros escolares; algoritmos de clasificación simples, tales como burbujas, tipo de selección y tipo de inserción; (caso peor) ligados a algunos algoritmos de clasificación generalmente más rápidos como el surtido rápido, Shellsort y tipo de árbol
$O(n^{c})$	polinomio o algebraico	Prótesis de gramática conjunción de árboles; ajuste máximo para gráficos bipartitos; encontrar el determinante con LU descomposición
${displaystyle L_{n}[alphac]=e^{(c+o(1))(ln n)^{alpha }(ln ln n)^{1-alpha }}}$ $<math alttext="{textstyle 0<alpha 0.α α .1{textstyle 0 0 0 0. <img alt="{textstyle 0<alpha$	L-notation or sub-exponential	Factorización de un número utilizando el tamiz cuadrático o el sieve de campo número
$O(c^{n})$ $1}" xmlns="http://www.w3.org/1998/Math/MathML">c■1{textstyle c]1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9057ec1c55def34aa105650bfe9491240553d160" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$	exponencial	Encontrar la solución (exacta) al problema del vendedor que viaja utilizando programación dinámica; determinar si dos declaraciones lógicas son equivalentes mediante búsqueda de fuerza bruta
$O(n!)$	factorial	Resolver el problema de los vendedores itinerantes mediante la búsqueda de fuerza bruta; generar todas las permutaciones no restringidas de una pose; encontrar el determinante con la expansión de Laplace; enumerar todas las particiones de un conjunto

Notación	Nombre	Descripción	Definición formal	Definición
$f(n)=o(g(n))$	Pequeña O; Pequeña Oh	$f$ está dominado por $g$ asintotically	$0,exists n_{0},forall n>n_{0}colon \|f(n)\|О О k■0∃ ∃ n0О О n■n0:: Silenciof()n)Silencio.kg()n){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}0,exists n_{0},forall n>n_{0}colon \|f(n)\|$	${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=0}$
$f(n)=O(g(n))$	Big O; Big Oh; Big Omicron	$\|f\|$ está obligado por encima $g$ (hasta el factor constante) asintotípicamente	$0,exists n_{0},forall n>n_{0}colon \|f(n)\|leq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0∃ ∃ n0О О n■n0:: Silenciof()n)Silencio≤ ≤ kg()n){displaystyle exists k Conf0,exists n_{0},forall no confían_{0}colon Silenciof(n)0,exists n_{0},forall n>n_{0}colon \|f(n)\|leq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16115602291a322030d1f83eaa012a3e8f11e10d" style="vertical-align: -0.838ex; width:35.342ex; height:2.843ex;"/>$	$<math alttext="{displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}}lim supn→ → JUEGO JUEGO f()n)g()n).JUEGO JUEGO {displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}} {infty }} {infty }<img alt="{displaystyle limsup _{nto infty }{frac {f(n)}{g(n)}}$
$f(n)=Theta (g(n))$	Big Theta	$f$ está obligado tanto por encima como por debajo $g$ asintotically	$0,exists k_{2}>0,exists n_{0},forall n>n_{0}colon }" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k1■0∃ ∃ k2■0∃ ∃ n0О О n■n0:: {displaystyle exists k_{1} {0},exists k_{2}] confianza0,exists n_{0},forall n título0,exists k_{2}>0,exists n_{0},forall n>n_{0}colon }" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/be379e6bea41362b562f8783c99e54cc4b716ca2" style="vertical-align: -0.671ex; width:29.422ex; height:2.509ex;"/>$ ${displaystyle k_{1},g(n)leq f(n)leq k_{2},g(n)}$	$f(n)=O(g(n))$ y $f(n)=Omega (g(n))$ (Versión numérica)
${displaystyle f(n)sim g(n)}$	Por orden de	$f$ es igual a $g$ asintotically	$0,exists n_{0},forall n>n_{0}colon left\|{frac {f(n)}{g(n)}}-1right\|О О ε ε ■0∃ ∃ n0О О n■n0:: Silenciof()n)g()n)− − 1Silencio.ε ε {displaystyle forall varepsilon √0,exists n_{0},forall n títulon_{0}colon left sometida{frac {f(n)}{g(n)}}}-1derechactamente escuchadavarepsilon }0,exists n_{0},forall n>n_{0}colon left\|{frac {f(n)}{g(n)}}-1right\|$	${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=1}$
$f(n)=Omega (g(n))$	Gran Omega en la teoría de la complejidad (Knuth)	$f$ se vincula a continuación $g$ asintotically	$0,exists n_{0},forall n>n_{0}colon f(n)geq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0∃ ∃ n0О О n■n0:: f()n)≥ ≥ kg()n){displaystyle exists k título0,exists n_{0},forall no confían_{0}colon f(n)geq k,g(n)}0,exists n_{0},forall n>n_{0}colon f(n)geq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb5154c98624eb114e71485abb7ec1396d157e6a" style="vertical-align: -0.838ex; width:34.048ex; height:2.843ex;"/>$	$0}" xmlns="http://www.w3.org/1998/Math/MathML">lim infn→ → JUEGO JUEGO f()n)g()n)■0{displaystyle liminf _{nto infty }{frac {f(n)}{g(n)} {n]} {f}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9e629f09dbf872b91187297980c2e624d58a54" style="vertical-align: -2.671ex; width:16.235ex; height:6.509ex;"/>$
$f(n)=omega (g(n))$	Pequeña Omega	$f$ dominados $g$ asintotically	$0,exists n_{0},forall n>n_{0}colon f(n)>k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">О О k■0∃ ∃ n0О О n■n0:: f()n)■kg()n){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}0,exists n_{0},forall n>n_{0}colon f(n)>k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b016c45b28b07815ff7f1e86ce09064f61057faf" style="vertical-align: -0.838ex; width:34.048ex; height:2.843ex;"/>$	${displaystyle lim _{nto infty }{frac {f(n)}{g(n)}}=infty }$
$f(n)=Omega (g(n))$	Gran Omega en la teoría de números (Hardy-Littlewood)	$\|f\|$ no está dominado por $g$ asintotically	$0,forall n_{0},exists n>n_{0}colon \|f(n)\|geq k,g(n)}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ k■0О О n0∃ ∃ n■n0:: Silenciof()n)Silencio≥ ≥ kg()n){displaystyle exists k confía0,forall n_{0},exists n confían_{0}colon Silenciof(n)0,forall n_{0},exists n>n_{0}colon \|f(n)\|geq k,g(n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee1de6bf9135e3729da954f9a7e35225a1689c31" style="vertical-align: -0.838ex; width:35.342ex; height:2.843ex;"/>$	$0}" xmlns="http://www.w3.org/1998/Math/MathML">lim supn→ → JUEGO JUEGO Silenciof()n)Silenciog()n)■0{displaystyle limsup _{nto infty }{frac {left habitf(n)right sobre la vida}{g(n)}} {}}}}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6fd52d75e1283fbf16cee8ade84c95a94b39e776" style="vertical-align: -2.671ex; width:18.379ex; height:6.509ex;"/>$

Contenido relacionado

Afinación pitagórica
Espacio vectorial normado
Espacio métrico completo
Más resultados...
Te puede interesar