"O" grande y "o" pequeña

"O" grande y "o" pequeña ( y ) son notaciones matemáticas para comparar el comportamiento asintótico (asintótica) de funciones . Se utilizan en diversas ramas de las matemáticas, pero de forma más activa: en análisis matemático , teoría de números y combinatoria , así como en informática y teoría de algoritmos . Por asintótica se entiende la naturaleza del cambio en una función cuando su argumento tiende a un punto determinado. $O$ $o$

$de)$ , " o pequeño de " significa "infinitamente pequeño con respecto a " [1] , insignificante al considerar . El significado del término "Gran O" depende de su campo de aplicación, pero siempre crece no más rápido que (las definiciones exactas se dan a continuación). $F$ $F$ $F$ $De)$ $F$

En particular:

la frase "la complejidad del algoritmo es " significa que con un aumento en el parámetro que caracteriza la cantidad de información de entrada del algoritmo, el tiempo de ejecución del algoritmo no aumentará más rápido que multiplicado por alguna constante; $O(f(n))$ $norte$ $f(n)$
la frase "la función es" o "pequeña de la función en la vecindad del punto " significa que a medida que se acerca k , disminuye más rápido que (la relación tiende a cero). $f(x)$ $g(x)$ $pags$ $X$ $pags$ $f(x)$ $g(x)$ $\izquierda |f(x)\derecha |/\izquierda |g(x)\derecha |$

Definiciones

Sean y dos funciones definidas en alguna vecindad perforada del punto , y en esta vecindad no se anula. Ellos dijeron eso: $f(x)$ $g(x)$ $x_{0}$ $gramo$

$F$ es "O" mayor que cuando , si existe una constante tal que para todo desde alguna vecindad del punto se cumple la desigualdad $gramo$ $x\a x_0$ $C>0$ $X$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$F$ es "o" pequeño de en , si para cualquiera existe tal vecindad perforada del punto que la desigualdad se cumple para todos $gramo$ $x\a x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\en U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

En otras palabras, en el primer caso, la razón está en la vecindad del punto (es decir, está acotada por arriba), y en el segundo caso, tiende a cero en . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\a x_0$

Designación

Por lo general, la expresión " es grande ( pequeño) de " se escribe usando la igualdad (respectivamente, ). $F$ $O$ $o$ $gramo$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Esta notación es muy conveniente, pero requiere cierto cuidado en su uso (y por lo tanto puede evitarse en los libros de texto más elementales). El hecho es que no se trata de igualdad en el sentido habitual, sino de una relación asimétrica .

En particular, se puede escribir

f(x) = O(g(x))

(o ),

f(x) = o(g(x))

pero expresiones

O(g(x)) = f(x)

(o )

o(g(x)) = f(x)

sin sentido.

Otro ejemplo: si es cierto que $x\flecha derecha 0$

O(x^2) = o(x)

pero

o(x)\neq O(x^{2})

Para cualquier x es verdadero

o(x) = O(x)

es decir, una cantidad infinitesimal está acotada, pero

O(x)\neq o(x).

En lugar del signo igual, sería metodológicamente más correcto usar signos de pertenencia e inclusión, entendiendo y como designaciones para conjuntos de funciones, es decir, usando la notación en la forma $O({\,})$ $o({\,})$

x^{3}+x^{2}\en O(x^{3})

\mahop O(x^2)\subconjunto o(x)

en lugar de, respectivamente,

x^{3}+x^{2}=O(x^{3})

\mahop O(x^2) = o(x)

Sin embargo, en la práctica, tal registro es extremadamente raro, principalmente en los casos más simples.

Cuando se utilizan estas notaciones, debe indicarse explícitamente (o ser obvio por el contexto) qué vecindarios (uno o dos lados, que contienen números enteros, reales, complejos u otros) y qué conjuntos admisibles de funciones están en cuestión (ya que el mismo la notación se utiliza en relación con funciones de varias variables, funciones de una variable compleja, matrices, etc.).

Otras denominaciones similares

La siguiente notación se utiliza para funciones y para : $f(n)$ $g(n)$ $n \a n_0$

Designacion	Explicación intuitiva	Definición
$f(n)\en O(g(n))$	$F$ está acotado superiormente por una función (hasta un factor constante) asintóticamente $gramo$	$\existe (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\en \Omega (g(n))$	$F$ está acotado desde abajo por una función (hasta un factor constante) asintóticamente $gramo$	$\existe (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\en \Theta (g(n))$	$F$ acotado por abajo y por arriba por la función asintóticamente $gramo$	$\exists (C>0), (C'>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\| \leq C'\|g(n)\|$
$f(n)\en o(g(n))$	$gramo$ domina asintóticamente $F$	$\forall (C>0) ,\existe U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\en \omega (g(n))$	$F$ domina asintóticamente $gramo$	$\forall (C>0) ,\existe U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$F$ es equivalente asintóticamente $gramo$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

donde es la vecindad perforada del punto . $tu$ $n_ {0}$

Propiedades básicas

Transitividad

${\begin{matriz}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implica &f(n)=\Theta (h( n))\\f(n)=O(g(n))\land g(n)=O(h(n))&\implica &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\implica &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\implica &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\implica &f(n)=\omega (h(n))\end{matriz}}$

Reflexividad

$f(n)=\Theta(f(n))$ ; ; $f(n)=O(f(n))$ $f(n)=\Omega(f(n))$

Simetría

$f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))$

Simetría de permutación

$\begin{matriz} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Flecha izquierda-derecha & g(n)=\omega(f(n)) \end{matriz}$

Otros

$C\cdot o(f) = o(f)$

C\cdot O(f) = O(f)

$o(C \cdot f) = o(f)$

O(C \cdot f) = O(f)

y, en consecuencia,

o(-f) = o(f)

O(-f) = O(f)

$o(f) + o(f) = o(f)$

o(f) + O(f) = O(f) + O(f) = O(f)

$O(f) \cdot O(g) = O(fg)$

o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg)

$O(O(f)) = O(f)$

o(o(f)) = o(O(f)) = O(o(f)) = o(f)

Notación asintótica en ecuaciones

Si el lado derecho de la ecuación contiene solo la notación asintótica (por ejemplo ), entonces el signo igual denota pertenencia al conjunto ( ). $n=O(n^{2})$ $n\en O(n^{2})$
Si la notación asintótica ocurre en una ecuación en otra situación, se tratan como si sustituyeran algunas funciones por ellas. Por ejemplo, como x → 0, la fórmula significa que , donde es una función de la que solo se sabe que pertenece al conjunto . Se supone que hay tantas funciones de este tipo en una expresión como notaciones asintóticas hay en ella. Por ejemplo, - contiene solo una función del . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $buey)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Si la notación asintótica ocurre en el lado izquierdo de la ecuación, se usa la siguiente regla:
cualquier función que elijamos (según la regla anterior) en lugar de la notación asintótica en el lado izquierdo de la ecuación, podemos elegir funciones en lugar de la notación asintótica (según la regla anterior) en el lado derecho para que la ecuación sea correcta .
Por ejemplo, la entrada significa que para cualquier función , hay alguna función tal que la expresión es verdadera para todos . $x+o(x)=O(x)$ $f(x)\en o(x)$ $g(x)\en O(x)$ $x+f(x)=g(x)$ $X$
Varias de estas ecuaciones se pueden combinar en cadenas. Cada una de las ecuaciones en este caso debe interpretarse de acuerdo con la regla anterior.
Por ejemplo: . Nótese que tal interpretación implica el cumplimiento de la relación . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

La interpretación anterior implica el cumplimiento de la relación:

\izquierda. \begin{matriz}A = B \\ B = C \end{matriz} \right\} \Rightarrow A = C

, donde A , B , C son expresiones que pueden contener notación asintótica.

Ejemplos de uso

$e^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\ldots +{\frac {x^{n}}{n!}}+\ldots =1+x+{\frac {x^{2}}{2}}+O(x^{3})$ en . $x\flecha derecha 0$

$¡norte! = O\izquierda(\izquierda(\frac{n}{e}\derecha)^{n + \frac{1}{2}}\derecha)$ en (sigue de la fórmula de Stirling ) $n \rightarrow \infty$

$T(n)=(n+1)^2=O(n^2)$ en . $n \rightarrow \infty$

Cuando se cumple la desigualdad . Así que pongamos .

n>1

(n+1)^2<4n^2

n_0=1, c=4

Nótese que no podemos poner , ya que y, por tanto, este valor es mayor que , para cualquier constante .

n_{0}=0

T(0)=1

C

c \cdot 0^2=0

La función para tiene un grado de crecimiento . $T(n)=3n^3+2n^2$ $n \rightarrow \infty$ $O(n^{3})$

Para mostrar esto, debemos poner y . Uno puede, por supuesto, decir que tiene orden , pero esta es una declaración más débil que eso .

n_{0}=0

c=5

Tennesse)

O(n^{4})

T(n) = O(n^3)

Probemos que la función para no puede tener el orden . $3^n$ $n \rightarrow \infty$ $O(2^n)$

Supongamos que hay constantes y tales que la desigualdad se cumple para todos .

C

n_ {0}

n \geq n_0

3^n \leq c \cdot 2^n

Entonces para todos . Pero toma cualquier valor, arbitrariamente grande, para suficientemente grande , por lo que no existe tal constante que pueda ser mayoritaria para todos los grandes de algunos .

c \geq \left( \frac{3}{2} \right)^n

n \geq n_0

\izquierda( \frac{3}{2} \derecha)^n

norte

C

\izquierda( \frac{3}{2} \derecha)^n

norte

n_ {0}

$T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty$ .

Para verificar, simplemente ponga . Entonces por .

c=1

T(n) \geq cn^3

n=0, 1, ...

Historia

La notación "O" es grande, introducida por el matemático alemán Paul Bachmann en el segundo volumen de su libro "Analytische Zahlentheorie" (Teoría analítica de los números), publicado en 1894 . La notación "o pequeño" fue utilizada por primera vez por otro matemático alemán, Edmund Landau en 1909 ; la popularización de ambas designaciones también está relacionada con las obras de este último, en relación con las cuales también se denominan símbolos de Landau . La designación proviene de la palabra alemana "Ordnung" (orden) [2] .

Véase también

infinitesimal

Notas

↑ Shvedov I. A. Curso compacto de análisis matemático. Parte 1. Funciones de una variable. - Novosibirsk, 2003. - S. 43.
↑ DE Knuth. Gran Omicron y gran Omega y gran Theta : Artículo . - ACM Sigact News, 1976. - V. 8 , No. 2 . - S. 18-24 . Archivado desde el original el 15 de agosto de 2016.

Literatura

D. Verde, D. Knuth. Métodos matemáticos para el análisis de algoritmos. — Por. De inglés. — M .: Mir, 1987. — 120 p.
J. McConnell. Fundamentos de los algoritmos modernos. - Ed. 2 adicionales - M. : Technosfera, 2004. - 368 p. — ISBN 5-94836-005-9 .
John E. Salvaje. Complejidad de los cálculos. - M. : Factorial, 1998. - 368 p. — ISBN 5-88688-039-9 .
V. N. Krupsky. Una introducción a la complejidad computacional. - M. : Prensa Factorial, 2006. - 128 p. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmos y Complejidades .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capítulo 3. Crecimiento de funciones // Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolski. Matemáticas superiores, volumen 2.
Dionisis Zindros. Introducción al Análisis de Complejidad de Algoritmos (2012). Consultado el 11 de octubre de 2013. Archivado desde el original el 10 de octubre de 2013. (Ruso)