Complejidad computacional de problemas y el análisis y diseño de algoritmos Flashcards
¿Cuál es el objetivo principal del análisis de algoritmos?
Determinar qué algoritmo es más eficiente dentro de una familia de algoritmos que resuelven el mismo problema, evaluando la cantidad de recursos requeridos (tiempo, memoria).
¿Por qué es problemático medir el tiempo de ejecución de un algoritmo usando el reloj del sistema operativo?
Porque la medida es dependiente del hardware, sistema operativo, compilador y carga del sistema. También puede variar según el tipo de sistema (multiprocesadores, distribución, etc.).
¿Qué es la complejidad temporal en el análisis de algoritmos?
Es el tiempo requerido por un algoritmo para ejecutarse y proporcionar un resultado a partir de los datos de entrada.
¿Cómo se define la complejidad espacial de un algoritmo?
Como la cantidad de memoria requerida (espacio total ocupado por las variables) antes, durante y después de la ejecución del algoritmo.
¿Qué factores externos pueden afectar la medida de la eficiencia de un algoritmo?
El lenguaje de programación, la máquina en la que se ejecuta, el compilador utilizado, la experiencia del programador y los datos de entrada.
¿Por qué es importante estimar el coste de los algoritmos independientemente de su implementación específica?
Para evitar la influencia de factores externos específicos y obtener una comparación más general y precisa entre diferentes algoritmos.
¿Qué representa el tamaño de la entrada (N) en el análisis de algoritmos
Es una medida del tamaño del problema que el algoritmo debe resolver, como el rango de un array, el número de elementos en una matriz, o el número de nodos en un grafo.
¿Cuál es el peor caso en el análisis de algoritmos?
El escenario más desfavorable en el que el algoritmo tiene el mayor tiempo de ejecución o consumo de recursos.
¿Cómo se define un problema de decisión?
Es un problema donde la respuesta es siempre “sí” o “no” sobre una propiedad de la instancia del problema.
¿Qué diferencia hay entre problemas de optimización y problemas de decisión?
En los problemas de optimización, se busca la mejor configuración o valor posible dentro de las restricciones dadas, mientras que en los problemas de decisión, se responde si una instancia cumple con una propiedad específica.
