robot de la enciclopedia para niños

Cota superior asintótica para niños

Enciclopedia para niños

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:

O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } x_0, c>0\mbox{ tales que} \\ \forall x\ge x_0 >0 : 0\le |f(x)|\le c|g(x)| \end{matrix}\right\}

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor x_0, f(x) no sobrepasa a cg(x). 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 definen las clases de complejidad.

Archivo:CotaSuperiorAsintotica
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)), ya que la clase de equivalencia de f coincide con el conjunto O(g(x). Muchas veces también se habla de la función nombrando únicamente su expresión, como en x² 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 cg(x) con respecto a f(x) cuando x tiende a infinito. Nótese además que dicho conjunto es no vacío pues g(x)=O(g(x)).

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

f(x)=\Theta(g(x)) \mbox{ si y solo si } f(x)=O(g(x)) \mbox{ y } f(x)=\Omega(g(x))\,

Propiedades

Sea E\subseteq \mathbb{R}, sean f_1:E\to \mathbb{R}, g_1:E\to \mathbb{R}, f_2:E\to \mathbb{R}, g_2:E\to \mathbb{R} funciones y k un real. Entonces los siguientes enunciados son ciertos:

i) Si f_1 = O(g_1)\, y g_1 = O(g_2)\,, entonces f_1 = O(g_2)\,
ii) Si f_1=O(g_1)\, y f_2=O(g_2)\,,entonces f_1f_2=O(g_1g_2)\,
iii) f_2O(g_1)=O(f_2g_1)\, (aquí es igualdad entre conjuntos)
iv) Si f_1=O(g_1)\, y f_2=O(g_2)\,, entonces f_1+f_2=O(|g_1|+|g_2|)\,
v) Si k\neq 0\, entonces O(g_1)=O(kg_1)\, (aquí es igualdad entre conjuntos)
vi) Si f_1= O(g_1)\,, entonces kf_1=O(g_1)\,.

Ejemplos

  • La función f(x) = x+10 puede ser acotada superiormente por la función g(x) = x². Para demostrarlo basta notar que para todo valor de x ≥ 3.7016, se cumple x+10 ≤ x². Por tanto x+10 = O(x²). Sin embargo, x² no sirve como cota inferior para x+10, es decir, x^2\neq\bigcirc(x+10).
    Observación: Este ejemplo muestra que f = O(g)\, no implica g = O(f)\,, es decir, la relación entre funciones dada por la notación de Landau no es simétrica. Sin embargo, sí es reflexiva: f = O(f)\,
  • La función 200x está acotada superiormente por x². Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x².

Órdenes usuales para funciones

Los órdenes más utilizados en análisis de algoritmos, en orden creciente, son los siguientes (donde c representa una constante y n el tamaño de la entrada):

notación nombre
O(1) orden constante
O(log log n) orden sublogarítmica
O(log n) orden logarítmica
O(\sqrt n) orden sublineal
O(n) orden lineal o de primer orden
O(n · log n) orden lineal logarítmica
O(n2) orden cuadrática o de segundo orden
O(n3), ... orden cúbica o de tercer orden, ...
O(nc) orden potencial fija
O(cn), n > 1 orden exponencial
O(n!) orden factorial
O(nn) orden potencial exponencial

Véase también

Kids robot.svg En inglés: Big O notation Facts for Kids

  • Cota inferior asintótica
  • Cota ajustada asintótica
  • Notación de Landau
Obtenido de «https://ninos.kiddle.co/index.php?title=Cota_superior_asintótica&oldid=3811822»
kids search engine
Todo el contenido de los artículos de la Enciclopedia Kiddle (incluidas las imágenes) se puede utilizar libremente para fines personales y educativos bajo la licencia Atribución-CompartirIgual a menos que se indique lo contrario. Citar este artículo:
Cota superior asintótica para Niños. Enciclopedia Kiddle.