Notación Big O

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

En ciencias de la computación , la notación O grande se usa para clasificar algoritmos de acuerdo con cómo crecen sus requisitos de espacio o tiempo de ejecución a medida que aumenta el tamaño de entrada. ^[3] En la teoría analítica de números , la notación O grande se usa a menudo para expresar un límite en la diferencia entre una función aritmética y una aproximación mejor entendida; un ejemplo famoso de tal diferencia es el término restante en el teorema de los números primos . La notación Big O también se utiliza 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.

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

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

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

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.