En este tutorial, aprenderá qué son las notaciones asintóticas. Además, aprenderá sobre la notación Big-O, la notación Theta y la notación Omega.
La eficiencia de un algoritmo depende de la cantidad de tiempo, almacenamiento y otros recursos necesarios para ejecutar el algoritmo. La eficiencia se mide con la ayuda de notaciones asintóticas.
Es posible que un algoritmo no tenga el mismo rendimiento para diferentes tipos de entradas. Con el aumento del tamaño de entrada, el rendimiento cambiará.
El estudio del cambio en el rendimiento del algoritmo con el cambio en el orden del tamaño de entrada se define como análisis asintótico.
Notaciones asintóticas
Las notaciones asintóticas son las notaciones matemáticas que se utilizan para describir el tiempo de ejecución de un algoritmo cuando la entrada tiende hacia un valor particular o un valor límite.
Por ejemplo: en la clasificación de burbujas, cuando la matriz de entrada ya está ordenada, el tiempo que tarda el algoritmo es lineal, es decir, en el mejor de los casos.
Pero, cuando la matriz de entrada está en condición inversa, el algoritmo toma el tiempo máximo (cuadrático) para ordenar los elementos, es decir, el peor de los casos.
Cuando la matriz de entrada no está ordenada ni en orden inverso, se necesita un tiempo promedio. Estas duraciones se indican mediante notaciones asintóticas.
Hay principalmente tres notaciones asintóticas:
- Notación Big-O
- Notación omega
- Notación theta
Notación Big-O (notación O)
La notación Big-O representa el límite superior del tiempo de ejecución de un algoritmo. Por lo tanto, proporciona la complejidad del peor de los casos de un algoritmo.
Big-O da el límite superior de una función
O (g (n)) = (f (n): existen constantes positivas c y n 0 tales que 0 ≦ f (n) ≦ cg (n) para todo n ≧ n 0 )
La expresión anterior puede describirse como una función que f(n)pertenece al conjunto O(g(n))si existe una constante positiva ctal que se encuentra entre 0y cg(n), para lo suficientemente grande n.
Para cualquier valor de n, el tiempo de ejecución de un algoritmo no cruza el tiempo proporcionado por O(g(n)).
Dado que da el peor tiempo de ejecución de un algoritmo, se usa ampliamente para analizar un algoritmo, ya que siempre estamos interesados en el peor de los casos.
Notación Omega (notación Ω)
La notación Omega representa el límite inferior del tiempo de ejecución de un algoritmo. Por lo tanto, proporciona la mejor complejidad de caso de un algoritmo.
Omega da el límite inferior de una función
Ω (g (n)) = (f (n): existen constantes positivas cy n 0 tales que 0 ≦ cg (n) ≦ f (n) para todo n ≧ n 0 )
La expresión anterior se puede describir como una función que f(n)pertenece al conjunto Ω(g(n))si existe una constante positiva ctal que se encuentre por encima cg(n), para lo suficientemente grande n.
Para cualquier valor de n, Omega da el tiempo mínimo requerido por el algoritmo Ω(g(n)).
Notación theta (notación Θ)
La notación theta encierra la función desde arriba y desde abajo. Dado que representa el límite superior e inferior del tiempo de ejecución de un algoritmo, se utiliza para analizar la complejidad de caso promedio de un algoritmo.
Theta limita la función dentro de factores constantes
Para una función g(n), Θ(g(n))viene dada por la relación:
Θ (g (n)) = (f (n): existen constantes positivas c 1 , c 2 y n 0 tales que 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) para todos n ≧ n 0 )
La expresión anterior puede describirse como una función que f(n)pertenece al conjunto Θ(g(n))si existen constantes positivas y de tal modo que se puede intercalar entre y , para n suficientemente grande.c1c2c1g(n)c2g(n)
Si una función se f(n)encuentra en cualquier punto intermedio y para todos , se dice que tiene un límite asintóticamente ajustado.c1g(n)c2g(n)n ≧ n0f(n)
