Cota superior asintótica

En análisis de algoritmos una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación de Landau: O(g(x)), Orden de g(x), coloquialmente llamada Notación O Grande, para referirse a las funciones acotadas superiormente por la función g(x).

Formalmente se define:

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor , f(x) no sobrepasa a . Quiere decir que la función f es inferior a g a partir de un valor dado salvo por un factor constante.

La cota superior asintótica tiene gran importancia en la Teoría de la complejidad computacional cuando se defininen las clases de complejidad.

f(x)=O(g(x)).

A pesar de que O(g(x)) está definida como un conjunto, se acostumbra escribir f(x)=O(g(x)) en lugar de f(x)∈O(g(x)). Muchas veces también se habla de la función nombrando únicamente su expresión, como en en lugar de h(x)=x², siempre que esté claro cuál es el parámetro de la función dentro de la expresión. En la gráfica se da un ejemplo esquemático de cómo se comporta con respecto a f(x) cuando x tiende a infinito. Nótese además que dicho conjunto es no vacío pues f(x)=O(g(x)).

La cota ajustada asintótica (notación Θ) tiene relación con las cotas asintóticas superior e inferior (notación Ω):

Propiedades

Sea , sean , , , funciones y un real. Entonces los siguientes enunciados son ciertos:

i) Si y , entonces
ii) Si y ,entonces
iii) (aquí es igualdad entre conjuntos)
iv) Si y , entonces
v) Si entonces (aquí es igualdad entre conjuntos)
vi) Si , entonces .
Other Languages
العربية: رمز O الكبير
беларуская: О-натацыя
čeština: Landauova notace
Esperanto: Granda O
magyar: O jelölés
Bahasa Indonesia: Notasi O besar
italiano: O-grande
한국어: 점근 표기법
Nederlands: Grote-O-notatie
norsk bokmål: Stor O-notasjon
português: Grande-O
Simple English: Big O notation
slovenščina: O notacija
српски / srpski: Велико О
svenska: Ordo
українська: Нотація Ландау
Tiếng Việt: Kí hiệu O lớn
中文: 大O符号