Notación O y análisis Flashcards
¿Qué es orden de complejidad O?
El “orden de complejidad O” o “notación O” es una forma de describir el comportamiento asintótico de un algoritmo, en términos de su tiempo de ejecución o uso de memoria a medida que el tamaño de la entrada crece. En esencia, te dice cómo se comporta el rendimiento de un algoritmo en función del tamaño de los datos con los que trabaja.
¿Qué es Conjunto O(g(x))?
La notación O(g(x)) se refiere a un conjunto de funciones que representan límites superiores para el crecimiento de la complejidad de un algoritmo.
En otras palabras, si decimos que un algoritmo tiene una complejidad en O(g(x)), estamos diciendo que la complejidad del algoritmo (f(x)) no crece más rápido que una función g(x).
¿Cómo es el crecimiento de una función f(x) que pertenece a O(g(x))?
Sea f(x) la función que expresa la complejidad de un algoritmo, entonces la expresión f(x) pertenece a O(g(x)), significa que f(x) crece, a lo sumo, tan rápido como cualquiera de las funciones g del conjunto O.
¿Qué se denota con Ω(g(x))?
Describe una cota inferior asintótica, es decir, f(x)crece al menos tan rápido (o más rápido) como g(x) para valores grandes de x.
¿Qué representa la notación Θ(g(x)) en el análisis de algoritmos?
La notación Θ(g(x)) describe una cota asintótica exacta para el crecimiento de una función f(x). Indica que f(x) crece exactamente al mismo ritmo que g(x) para valores grandes de la entrada x. Formalmente, f(x) pertenece a Θ(g(x)) si existen constantes c1, c2 y x0 tales que c1⋅g(x)≤f(x)≤c2⋅g(x) para todo x≥x0.
(x0 es “x sub 0”)
¿dónde póner el foco en un programa que se va a ejecutar muy pocas veces?
Nuestro foco debe estar en la codificación y la depuración del algoritmo, donde la complejidad no es el factor crítico a considerar.
¿Qué considerar en un programa que se utilizará por mucho tiempo, seguramente, será mantenido por varias personas en el curso de su vida útil?
Esto hace que los factores que debemos considerar sean los que se relacionan con su legibilidad; incluso, si la mejora de ella impacta en la complejidad de los algoritmos empleados.
¿Es relevante el orden de complejidad del algoritmo en un programa que solo trabajará con datos pequeños?
Generalmente, no es relevante. Cuando un programa trabaja con datos pequeños (valores bajos de N), las diferencias en tiempo de ejecución entre algoritmos de diferentes órdenes de complejidad suelen ser mínimas. En estos casos, es más importante centrarse en aspectos como la legibilidad, la facilidad de implementación y la corrección del código, ya que la optimización algorítmica no tendrá un impacto significativo.
¿Existe una relación entre la complejidad en tiempo de ejecución y el consumo de memoria en los algoritmos? ¿Cómo se debe evaluar esto?
Sí, a menudo existe un trade-off entre la complejidad en tiempo de ejecución y el consumo de memoria en los algoritmos. Mejorar la eficiencia temporal a veces requiere más memoria (por ejemplo, utilizando cachés o almacenamiento adicional de datos), y reducir el uso de memoria puede aumentar el tiempo de ejecución (por ejemplo, mediante cálculos repetitivos). Sin embargo, esta no es una regla universal; algunos algoritmos pueden ser eficientes en ambos aspectos. Es importante evaluar cómo estas mejoras impactan el rendimiento general del programa en función de las limitaciones del sistema y los requisitos del problema.
En programas orientados al cálculo numérico, ¿qué factores deben considerarse además de la complejidad y el tiempo de ejecución?
Además de la complejidad y el tiempo de ejecución, en programas de cálculo numérico es crucial considerar:
- Precisión del cálculo: Exactitud de los resultados calculados.
- Error introducido en cálculos intermedios: Minimización y control de errores acumulados durante el cálculo.
- Estabilidad del algoritmo: Capacidad del algoritmo para manejar errores y perturbaciones sin amplificarlos excesivamente.
Estos factores son fundamentales para garantizar que el programa sea fiable y produzca resultados precisos y útiles.
