Notación O grande
La notación O grande es una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor o infinito particular. Big O es miembro de una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann , [1] Edmund Landau , [2] y otros, denominadas colectivamente notación de Bachmann-Landau o notación asintótica . Bachmann eligió la letra O para representar Ordnung , es decir, el orden de aproximación .
En informática , la notación O grande se utiliza para clasificar algoritmos según cómo crecen sus requisitos de tiempo de ejecución o espacio a medida que crece el tamaño de entrada. [3] En teoría analítica de números , la notación O grande se utiliza 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 del teorema de los números primos . La notación O grande también se utiliza en muchos otros campos para proporcionar estimaciones similares.
La notación O grande caracteriza funciones según sus tasas de crecimiento: diferentes funciones con la misma tasa de crecimiento asintótica se pueden representar usando la misma notación O. La letra O se utiliza porque la tasa de crecimiento de una función también se conoce como 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 a 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ótico.
Sea , la función a estimar, una función con valor real o complejo y sea , la función de comparación, una función con valor real. Dejemos 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 . [4] Se escribe
En muchos contextos, el supuesto de que estamos interesados en la tasa de crecimiento cuando la variable tiende al infinito no se plantea, y se escribe de manera más simple que