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 . La letra O fue elegida por Bachman para representar Ordnung , es decir, el orden de aproximación .

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$ , la función a estimar, una función de valor real o complejo y sea $g$ , la función de comparación, 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)}$

En muchos contextos, la suposición de que estamos interesados en la tasa de crecimiento a medida que la variable $x$ tiende al infinito no se establece, y se escribe de manera más simple que