Notaciones Asintóticas
1. Qué son las Notaciones Asintóticas? #
Las notaciones asintóticas nos ayudan a describir cómo crece el tiempo de ejecución o el uso de memoria de un algoritmo a medida que aumenta el tamaño de la entrada (n).
✅ Nos permiten comparar algoritmos sin depender de la velocidad del hardware o del lenguaje de programación.
📌 Ejemplo:
Si un algoritmo toma 1 segundo para n = 1000 y 4 segundos para n = 2000, significa que su tiempo de ejecución no es constante, sino que crece con n.
Para describir la eficiencia de un algoritmo usamos tres tipos de notaciones:
- O(n) → Límite superior (el peor caso).
- Ω(n) → Límite inferior (el mejor caso).
- Θ(n) → Caso ajustado (cuando el peor y el mejor caso son iguales).
2. 2. O(n) - Notación O grande (cota superior) #
La notación O (O grande) representa el peor caso de un algoritmo. Nos dice cómo crece el tiempo de ejecución en función de n.
Ejemplo: Búsqueda Lineal (O(n)) #
Si tenemos un array de n elementos y buscamos un número, en el peor caso recorremos todo el array.
📌 Conclusión: En el peor caso, debemos recorrer los n elementos, por lo que O(n) significa que el tiempo de ejecución crece linealmente.
3. 3. Ω(n) Notación Omega (cota inferior) #
La notación Ω (Omega) representa el mejor caso de un algoritmo. Nos dice el mínimo tiempo posible que puede tomar.
Ejemplo: Búsqueda Lineal (Ω(1)) #
Si el elemento buscado está en la primera posición, lo encontramos de inmediato.
📌 Conclusión: En el mejor caso, encontramos el elemento en la primera posición, lo que nos da Ω(1).
4. 4. Θ(n) Notación Theta (cota ajustada) #
La notación Θ (Theta) indica que el tiempo de ejecución siempre crece al mismo ritmo, sin importar el caso.
- Ejemplo: Sumar los elementos de un array
- Siempre recorremos todos los elementos.
- El peor y mejor caso son iguales.
📌 Conclusión: En este caso, siempre recorremos todo el array, por lo que el mejor y peor caso son iguales, lo que da Θ(n).
5. 5. Comparación de Notaciones #
| Notación | Significado | Ejemplo |
|---|---|---|
| O(n) | Peor caso (cota superior) | Buscar en un array sin orden |
| Ω(n) | Mejor caso (cota inferior) | Encontrar el primer elemento |
| Θ(n) | Caso ajustado (misma ejecución en todos los casos) | Recorrer un array |
Resumen del tema
Conceptos clave #
- Notación Asintótica: lenguaje matemático para describir la tasa de crecimiento del tiempo o espacio de ejecución respecto al tamaño de entrada ().
- Notación Big-O (): cota superior asintótica que modela el peor escenario de ejecución (ej. búsqueda lineal en el peor caso es ).
- Notación Big-Omega (): cota inferior asintótica que modela el mejor escenario posible (ej. elemento encontrado en el primer índice es ).
- Notación Big-Theta (): cota ajustada exacta cuando el mejor y peor caso crecen con el mismo orden asintótico (ej. suma de todos los elementos de un array es ).
Qué debes recordar #
Big-O () garantiza el límite superior de coste, Big-Omega () el mínimo teórico, y Big-Theta () define el comportamiento exacto y ajustado del algoritmo.