Hemos discutido el análisis asintótico y los peores, promedios y mejores casos de algoritmos . La idea principal del análisis asintótico es tener una medida de la eficiencia de los algoritmos que no dependan de las constantes específicas de la máquina y no requieran la implementación de algoritmos ni el tiempo que toman los programas para compararlos. Las notaciones asintóticas son herramientas matemáticas para representar la complejidad temporal de los algoritmos para el análisis asintótico. Las siguientes 3 notaciones asintóticas se utilizan principalmente para representar la complejidad temporal de los algoritmos.
1) Notación Θ: La notación theta limita una función desde arriba y desde abajo, por lo que define el comportamiento asintótico exacto.
Una forma sencilla de obtener la notación Theta de una expresión es eliminar los términos de orden inferior e ignorar las constantes iniciales. Por ejemplo, considere la siguiente expresión.
3n 3 + 6n 2 + 6000 = Θ(n 3 )
Eliminar términos de orden inferior siempre está bien porque siempre habrá un número (n) después del cual Θ(n 3 ) tiene valores más altos que Θ(n 2 ) independientemente de las constantes involucrado.
Para una función g(n) dada, denotamos que Θ(g(n)) es el siguiente conjunto de funciones.
Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such
that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}
La definición anterior significa que si f(n) es theta de g(n), entonces el valor f(n) siempre está entre c1*g(n) y c2*g(n) para valores grandes de n (n >= n0). La definición de theta también requiere que f(n) no sea negativa para valores de n mayores que n0.
Ejemplos:
{ 100 , log (2000) , 10^4 } pertenece a Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } pertenece a Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} pertenece a Θ( n^2)
Θ proporciona límites exactos.
2) Notación Big O: La notación Big O define un límite superior de un algoritmo, limita una función solo desde arriba. Por ejemplo, considere el caso de Ordenación por inserción. Toma tiempo lineal en el mejor de los casos y tiempo cuadrático en el peor de los casos. Podemos decir con seguridad que la complejidad temporal del ordenamiento por inserción es O(n^2). Tenga en cuenta que O (n ^ 2) también cubre el tiempo lineal.
Si usamos la notación Θ para representar la complejidad temporal de la ordenación por inserción, tenemos que usar dos declaraciones para el mejor y el peor de los casos:
1. La complejidad temporal del peor caso de la ordenación por inserción es Θ(n^2).
2. La complejidad de tiempo del mejor caso de clasificación por inserción es Θ(n).
La notación Big O es útil cuando solo tenemos un límite superior en la complejidad temporal de un algoritmo. Muchas veces encontramos fácilmente un límite superior simplemente mirando el algoritmo.
O(g(n)) = { f(n): there exist positive constants c and
n0 such that 0 <= f(n) <= c*g(n) for
all n >= n0}
Ejemplos:
{ 100 , log (2000) , 10^4 } pertenece a O(1)
U { (n/4) , (2n+3) , (n/100 + log(n)) } pertenece a O(n)
U { (n^2+n) , (2n^2) , (n^2+log(n))} pertenece a O(n^2)
Aquí U representa unión , podemos escribirlo de esta manera porque O proporciona cotas exactas o superiores.
3) Notación Ω: Así como la notación Big O proporciona un límite superior asintótico en una función, la notación Ω proporciona un límite inferior asintótico.
La notación Ω puede ser útil cuando tenemos un límite inferior en la complejidad temporal de un algoritmo. Como se discutió en la publicación anterior, el rendimiento del mejor caso de un algoritmo generalmente no es útil , la notación Omega es la notación menos utilizada entre las tres.
Para una función dada g(n), denotamos por Ω(g(n)) el conjunto de funciones.
Ω (g(n)) = {f(n): there exist positive constants c and
n0 such that 0 <= c*g(n) <= f(n) for
all n >= n0}.
Consideremos aquí el mismo ejemplo de clasificación por inserción. La complejidad temporal de la ordenación por inserción se puede escribir como Ω(n), pero no es una información muy útil sobre la ordenación por inserción, ya que generalmente nos interesa el peor de los casos y, a veces, el caso promedio.
Ejemplos:
{ (n^2+n) , (2n^2) , (n^2+log(n))} pertenece a Ω( n^2)
U { (n/4) , (2n+3) , (n/100 + log(n)) } pertenece a Ω(n)
U { 100 , log (2000) , 10^4 } pertenece a Ω(1)
Aquí U representa la unión, podemos escribirlo de esta manera porque Ω proporciona cotas exactas o inferiores.
Propiedades de las notaciones asintóticas:
ya que hemos analizado la definición de estas tres notaciones, analicemos ahora algunas propiedades importantes de esas notaciones.
1. Propiedades generales:
Si f(n) es O(g(n)) entonces a*f(n) también es O(g(n)) ; donde a es una constante.
Ejemplo: f(n) = 2n²+5 es O(n²)
entonces 7*f(n) = 7(2n²+5) = 14n²+35 también es O(n²) .
De manera similar, esta propiedad satisface tanto la notación Θ como la Ω.
Podemos decir
Si f(n) es Θ(g(n)) entonces a*f(n) también es Θ(g(n)) ; donde a es una constante.
Si f(n) es Ω (g(n)) entonces a*f(n) también es Ω (g(n)) ; donde a es una constante.
2. Propiedades transitivas:
Si f(n) es O(g(n)) y g(n) es O(h(n)) entonces f(n) = O(h(n)) .
Ejemplo: si f(n) = n, g(n) = n² y h(n)=n³
n es O(n²) y n² es O(n³)
entonces n es O(n³)
De manera similar, esta propiedad satisface tanto la notación Θ como la Ω.
Podemos decir
Si f(n) es Θ(g(n)) y g(n) es Θ(h(n)) entonces f(n) = Θ(h(n)) .
Si f(n) es Ω (g(n)) y g(n) es Ω (h(n)) entonces f(n) = Ω (h(n))
3. Propiedades reflexivas :
Las propiedades reflexivas siempre son fáciles de entender después de las transitivas.
Si se da f(n), entonces f(n) es O(f(n)). ¡ Puesto que el VALOR MÁXIMO DE f(n) será f(n) MISMO!
Por lo tanto, x = f(n) e y = O(f(n) se vinculan siempre en relación reflexiva.
Ejemplo: f(n) = n² ; O(n²) es decir, O(f(n))
De manera similar, esta propiedad satisface tanto la notación Θ como la Ω.
Podemos decir eso:
Si se da f(n), entonces f(n) es Θ(f(n)).
Si se da f(n), entonces f(n) es Ω (f(n)).
4. Propiedades simétricas:
Si f(n) es Θ(g(n)) entonces g(n) es Θ(f(n)) .
Ejemplo: f(n) = n² y g(n) = n²
luego f(n) = Θ(n²) y g(n) = Θ(n²)
Esta propiedad solo se cumple para la notación Θ.
5. Transponer propiedades simétricas:
Si f(n) es O(g(n)), entonces g(n) es Ω (f(n)).
Ejemplo: f(n) = n , g(n) = n²
entonces n es O(n²) y n² es Ω (n)
Esta propiedad solo satisface las notaciones O y Ω .
6. Algunas propiedades más:
1.) Si f(n) = O(g(n)) y f(n) = Ω(g(n)) entonces f(n) = Θ(g(n))
2.) Si f(n) = O(g(n)) y d(n)=O(e(n))
entonces f(n) + d(n) = O( max( g(n), e (n) ))
Ejemplo: f(n) = n ie O(n)
d(n) = n² ie O(n²)
luego f(n) + d(n) = n + n² ie O(n²)
3.) Si f(n)=O(g(n)) y d(n)=O(e(n))
entonces f(n) * d(n) = O( g(n) * e(n ) )
Ejemplo: f(n) = n ie O(n)
d(n) = n² ie O(n²)
entonces f(n) * d(n) = n * n² = n³ ie O(n³)
_______________________________________________________________________________
Note : If f(n) = O(g(n)) then g(n) = Ω(f(n))
Ejercicio:
¿Cuál de las siguientes afirmaciones es/son válidas?
1. La complejidad temporal de QuickSort es Θ(n^2)
2. La complejidad temporal de QuickSort es O(n^2)
3. Para dos funciones cualesquiera f(n) y g(n), tenemos f(n) = Θ(g(n)) si y solo si f(n) = O(g(n)) y f(n ) = Ω(g(n)).
4. La complejidad temporal de todos los algoritmos informáticos se puede escribir como Ω(1)
Links importantes :
- Hay dos notaciones más llamadas o minúscula y omega minúscula . Little o proporciona un límite superior estricto (la condición de igualdad se elimina de Big O) y little omega proporciona un límite inferior estricto (la condición de igualdad se elimina de big omega)
- Análisis de Algoritmos | Conjunto 4 (Análisis de bucles)
- Artículos recientes sobre análisis de algoritmos.
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .
Este artículo es una contribución de Abhay Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA