Semana 4 - leosaq/AnalisisDeAlgoritmos GitHub Wiki
¿Qué es la Notación Asintótica?
La notación asintótica nos ayuda a entender cómo se comporta un algoritmo cuando crece la cantidad de datos que recibe como entrada. En lugar de medir tiempos exactos, usamos símbolos matemáticos que representan el rendimiento en diferentes escenarios:
- O (orden) → caso más lento (peor escenario)
- Ω (omega) → caso más rápido (mejor escenario)
- Θ (theta) → comportamiento promedio o exacto
Esta notación es útil para comparar algoritmos en cuanto a eficiencia sin importar la máquina donde se ejecuten.
Factores que influyen
El tiempo que toma un algoritmo puede variar según:
- La potencia de la computadora que lo ejecuta
- El lenguaje de programación, el compilador, y otras herramientas de desarrollo utilizadas
Tiempo de Ejecución
Para analizar el tiempo de ejecución de un algoritmo, se deben considerar dos aspectos importantes:
- ¿Cuánto se demora en completarse dependiendo del tamaño de los datos de entrada?
- ¿Con qué rapidez crece el número de operaciones a medida que aumenta la entrada?
Este análisis nos permite entender la tasa de crecimiento del algoritmo, lo cual es clave al trabajar con grandes volúmenes de datos.
Aplicación
Estudiar la notación asintótica permite tomar mejores decisiones al elegir estructuras de datos y métodos que resuelvan problemas de manera más eficiente, especialmente cuando los recursos son limitados.
Ejemplo visto en Clases
¿Qué es la Notación "Para el Orden de"?
La notación "para el orden de" se refiere a la notación Big O (también llamada "O-grande"), que se escribe así:
O(f(n))
¿Qué representa?
Cuando decimos que un algoritmo tiene un tiempo de ejecución de orden O(n²), estamos diciendo que, como máximo, su tiempo de ejecución crece proporcionalmente al cuadrado del tamaño de la entrada n.
Es una forma de medir y comparar la eficiencia de los algoritmos, especialmente en el peor de los casos.
¿Para qué sirve?
- Para describir el rendimiento de un algoritmo sin importar el lenguaje de programación o la computadora.
- Para entender cómo crece el tiempo o el uso de recursos a medida que aumenta el tamaño de los datos.
- Para comparar algoritmos y elegir el más eficiente según el caso.
Ejemplos de Notaciones Comunes
| Notación | Se dice | Significado breve |
|---|---|---|
| O(1) | Orden constante | El tiempo es igual sin importar el tamaño |
| O(n) | Orden lineal | El tiempo crece proporcional a la entrada |
| O(n²) | Orden cuadrático | Tiempo crece como n al cuadrado |
| O(log n) | Orden logarítmico | Crece muy lentamente |
| O(n log n) | Orden lineal-log | Más rápido que cuadrático, común en algoritmos de ordenamiento eficientes |
Ejemplo simple
- Un algoritmo que recorre un arreglo una vez (como buscar un valor) tiene orden O(n)
- Un algoritmo que compara todos los pares de elementos (como bubble sort) tiene orden O(n²)
Conclusión
La notación "para el orden de" es una herramienta fundamental en la ciencia de la computación. Nos permite analizar, predecir y mejorar el comportamiento de los algoritmos en términos de tiempo o memoria, y es esencial para diseñar programas eficientes.