Notación O grande

La notación Big O 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 , ^[1] Edmund Landau , ^[2] y otros, denominadas colectivamente notación Bachmann-Landau o notación asintótica .

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

La notación Big O caracteriza las funciones según sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento pueden representarse 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óticas.

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

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 ₀ tales que${\ estilo de visualización f (x)}$${\ estilo de visualización g (x)}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr)}}$

Ejemplo de notación Big O: como existe (p. ej., ) y (p. ej., ) tales que siempre que .${\displaystyle {\color {rojo}f(x)}\in O{\color {azul}(g(x))}}$${\ estilo de visualización M> 0}$${\ estilo de visualización M = 1}$${\ estilo de visualización x_ {0}}$${\ estilo de visualización x_ {0} = 5}$${\displaystyle {\color {rojo}f(x)}\leq {\color {azul}Mg(x)}}$${\displaystyle x\geq x_{0}}$

Gráficas de funciones comúnmente utilizadas en el análisis de algoritmos, que muestran el número de operaciones N frente al tamaño de entrada n para cada función