Notación Big O - Big O notation

Ejemplo de notación Big O: como existe (por ejemplo, ) y (por ejemplo, ) tal que siempre .

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 , Edmund Landau y otros, denominadas 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. 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 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, usando los símbolos o , Ω, ω y Θ , para describir otros tipos de límites en las tasas de crecimiento asintóticas.

Definicion 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 . Uno escribe

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 0 tal que

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

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

si existen números positivos y M tales que para todo x con ,

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 :

si

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 0 tales que para todos . Cuando sea necesario, los intervalos finitos son (tácitamente) excluidos de 's y ' dominio s eligiendo n 0 suficientemente grande. (Por ejemplo, no está definido en ).

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 4 - 2 x 3 + 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 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 mayor exponente en función de x , es decir, 6 x 4 . Ahora se puede aplicar la segunda regla: 6 x 4 es un producto de 6 y x 4 en el 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 ) . Se puede confirmar este cálculo usando la definición formal: sea f ( x ) = 6 x 4 - 2 x 3 + 5 y g ( x ) = x 4 . Aplicando la definición formal de arriba, el enunciado de que f ( x ) = O ( x 4 ) es equivalente a su expansión,

para alguna elección adecuada de x 0 y M y para todo x > x 0 . Para probar esto, sea x 0 = 1 y M = 13 . Entonces, para todo x > x 0 :

asi que

Uso

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

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:

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 versus el 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 necesita para completar un problema de tamaño n puede ser T ( n ) = 4 n 2 - 2 n + 2 . A medida que n crece, el término n 2 llegará a dominar, por lo que todos los demás términos pueden despreciarse; por ejemplo, cuando n = 500 , el término 4 n 2 es 1000 veces más grande que el término 2 n . Ignorar este último tendría un efecto insignificante en el valor de la expresión para la mayoría de los propósitos. Además, los coeficientes se vuelven irrelevantes si los comparamos con cualquier otro orden de expresión, como una expresión que contiene un término n 3 o n 4 . Incluso si T ( n ) = 1,000,000 n 2 , si U ( n ) = n 3 , este último siempre excederá 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, 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

o

y decir que el algoritmo tiene un orden de complejidad de tiempo n 2 . El signo " = " no pretende expresar "es igual a" en su sentido matemático normal, sino más bien un "es" más coloquial, por lo que la segunda expresión a veces se considera más precisa (consulte la discusión sobre " Signo igual " a continuación) mientras el primero es considerado por algunos como un abuso de notación .

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:

La segunda expresión (el uno con O ( x 3 )) significa que el valor absoluto del error e x - (1 + x + x 2 /2) es a lo sumo algunas veces constantes | x 3 | cuando x está lo suficientemente cerca de 0.

Propiedades

Si la función f puede escribirse como una suma finita de otras funciones, entonces la de más rápido crecimiento determina el orden de f ( n ) . Por ejemplo,

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 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 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 n y 3 n 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 2 , reemplazar 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 , al reemplazar n con cn se obtiene 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 en función del número de entrada x mismo. , porque n = O (log x ) .

Producto

Suma

Si y luego . De ello se deduce que si y luego . En otras palabras, esta segunda afirmación dice que es un cono convexo .

Multiplicación por una constante

Sea k una constante distinta de cero. Entonces . En otras palabras, si , entonces

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

si y solo si

De manera equivalente, la condición de que para algunos se puede reemplazar con la condición de que , donde denota la norma de Chebyshev . Por ejemplo, la declaración

afirma que existen constantes C y M tales que

donde g ( n , m ) se define por

Esta definición permite que todas las coordenadas de aumenten hasta el infinito. En particular, la declaración

(es decir, ) es bastante diferente de

(es decir, ).

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 .

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.

Asuntos de notación

Signo de 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 la 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 2 ) es cierto pero O ( x 2 ) = O ( x ) no lo es. Knuth describe tales afirmaciones como "igualdad unidireccional", ya que si los lados pudieran invertirse, "podríamos deducir cosas ridículas como n = n 2 de las identidades n = O ( n 2 ) y n 2 = O ( n 2 ) . " 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" es "en inglés: 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: " f ( x ) es un elemento de O ( g ( x ))", o " f ( x ) está en el conjunto O ( g ( x ))"), pensando en O ( g ( x )) como la clase de todas las funciones h ( x ) tales que | h ( x ) | ≤  C | g ( x ) | para alguna constante C . Sin embargo, es habitual el uso del signo igual.

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,

expresa lo mismo que

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 2 ), y después de que se ejecuta la subrutina, el algoritmo debe tomar 55 n 3 + 2 n + 10 pasos adicionales antes de terminar. Por tanto, la complejidad temporal global del algoritmo se puede expresar como T ( n ) = 55 n 3 + O ( n 2 ) . Aquí, los términos 2 n + 10 se incluyen dentro del O ( n 2 ) 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 :

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 dos lados 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 n ) 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 formal que, a diferencia del uso habitual de "=", no es una relación simétrica . Así, por ejemplo, n O (1) = O ( e n ) no implica el enunciado falso O ( e n ) = n O (1)

Tipografía

Big O se compone tipo como una "O" en cursiva mayúsculas, como en el siguiente ejemplo: . 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.

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

Notación Nombre Ejemplo
constante Determinar si un número binario es par o impar; Calculando ; Usar una tabla de búsqueda de tamaño constante
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
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

polilogarítmico El orden de la cadena de matrices se puede resolver en tiempo polilogarítmico en una máquina paralela de acceso aleatorio .

poder fraccional Buscando en un árbol kd
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
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
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
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
polinomio o algebraico Análisis gramatical adyacente al árbol ; coincidencia máxima para gráficos bipartitos ; encontrar el determinante con la descomposición LU

Notación L o sub-exponencial Factorizar un número usando el tamiz cuadrático o el tamiz de campo numérico

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
factorial Resolver el problema del vendedor ambulante 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.

Notaciones asintóticas relacionadas

Big O se usa ampliamente en informática. Junto con algunas otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau.

Notación pequeña-o

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 números reales positivos , de modo que g ( x ) es estrictamente positivo para todos los valores suficientemente grandes de x . Uno escribe

si para cada constante positiva ε existe una constante N tal que

Por ejemplo, uno tiene

y

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. De esta manera, la notación o pequeña hace una declaración más fuerte que la correspondiente notación O grande: toda función que es pequeña o de g también es grande O de g , pero no todas las funciones que son grandes O de g también son poco-o de g . Por ejemplo, pero .

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

(y así es como Landau definió originalmente la notación de o pequeña).

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

si c es una constante distinta de cero y luego , y
si y luego

También satisface una relación de transitividad :

si y luego

Gran notación Omega

Otra notación asintótica es "gran omega". Hay dos definiciones generalizadas e incompatibles de la declaración.

como ,

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.

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 introdujeron el nuevo símbolo , que se define de la siguiente manera:

como si

Así es la negación de .

En 1916 los mismos autores introdujeron los dos nuevos símbolos y , definidos como:

como si ;
como si

Estos símbolos fueron usados ​​por Edmund Landau , con los mismos significados, en 1924. Después de Landau, las notaciones nunca se volvieron a usar exactamente así; se convirtió y se convirtió .

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 .

Ejemplos sencillos

Tenemos

como

y mas precisamente

como

Tenemos

como

y mas precisamente

como

sin embargo

como

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ó

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 ".

Familia de notaciones de Bachmann-Landau

Notación Nombre Descripción Definicion formal Definición de límite
Big O; Big Oh; Omicrón grande está acotado por encima de g (hasta un factor constante) asintóticamente
Gran theta f está acotada tanto por arriba como por abajo por g asintóticamente y (versión Knuth)
Gran Omega en la teoría de la complejidad (Knuth) f está acotada por debajo de g asintóticamente
Pequeña O; Pequeño oh f está dominado por g asintóticamente
Del orden de f es igual ag asintóticamente
Pequeño Omega f domina g asintóticamente
Gran Omega en teoría de números (Hardy-Littlewood) no está dominado por g asintóticamente

Las definiciones de límite asumen que es suficientemente grande . La tabla está (en parte) ordenada de menor a mayor, en el sentido de que (la versión de Knuth de) en funciones corresponde a la línea real (la versión de Hardy-Littlewood de , sin embargo, no corresponde a ninguna de estas descripciones).

La ciencia de la computación usa las notaciones grande , grande Theta , pequeño , pequeño omega y gran Omega de Knuth . La teoría analítica de números a menudo usa el gran , pequeño , grande Omega de Hardy-Littlewood (con o sin los subíndices +, - o ±) y notaciones. La notación omega pequeña no se usa con tanta frecuencia en el análisis.

Uso en ciencias de la computación

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 podría ser más apropiado en términos de hechos en un contexto dado. Por ejemplo, cuando se considera una función T ( n ) = 73 n 3 + 22 n 2 + 58, todos los siguientes son generalmente aceptables, pero los límites más estrictos (como los números 2 y 3 a continuación) generalmente se prefieren mucho a los límites más flexibles ( como el número 1 a continuación).

  1. T ( n ) = O ( n 100 )
  2. T ( n ) = O ( n 3 )
  3. T ( n ) = Θ ( n 3 )

Las declaraciones equivalentes en inglés son respectivamente:

  1. T ( n ) crece asintóticamente no más rápido que n 100
  2. T ( n ) crece asintóticamente no más rápido que n 3
  3. T ( n ) crece asintóticamente tan rápido como n 3 .

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 un 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

En una notación correcta, este conjunto puede, por ejemplo, llamarse O ( g ), donde

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. Dentro de una ecuación o desigualdad, el uso de la notación asintótica representa una función anónima en el conjunto O ( g ), que elimina los términos de orden inferior y ayuda a reducir el desorden no esencial en las ecuaciones, por ejemplo:

Extensiones de 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 . 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

es conveniente para funciones que están entre polinomios y exponenciales en términos de .

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 fg . La notación o se puede utilizar para definir derivadas y diferenciabilidad en espacios bastante generales, y también equivalencia (asintótica) de funciones,

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 "). El teórico de números Edmund Landau lo adoptó y, por lo tanto, se inspiró para introducir en 1909 la notación o; de ahí que ambos se llamen ahora símbolos de Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. El símbolo (en el sentido de "no es una o de") fue introducido en 1914 por Hardy y Littlewood. Hardy y Littlewood también introdujeron en 1916 los símbolos ("derecha") e ("izquierda"), precursores de los símbolos modernos ("no es más pequeño que una pequeña o de") y ("no es más grande 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. En la década de 1970, la gran O fue popularizada en 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 grandes símbolos Theta y los pequeños omega.

Los símbolos de Hardy eran (en términos de la notación O moderna)

  y  

(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.

La notación de Hardy ya no se usa. Por otro lado, en la década de 1930, 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

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

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 , probablemente en referencia a su definición del símbolo Omega . No se debe utilizar el dígito cero .

Ver también

Referencias y notas

Otras lecturas

enlaces externos