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), o coloquialmente llamada Notación O Grande, para referirse a las funciones acotadas superiormente por la función g(x).

Más 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 Teoría de la complejidad computacional a la hora de definir las clases de complejidad.

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

A pesar de que O(g(x)) está definido 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 una 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 como se comporta con respecto a f(x) cuando x tiende a infinito. Note 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符号