Mat. Discretas - Actividad en clase - 03 Abril 2025

¿Qué es la tratabilidad de un problema en computación?

• La posibilidad de resolver un problema en tiempo razonable con un algoritmo
• La facilidad de representar un problema gráficamente
• La capacidad de resolver un problema sin errores
• La dificultad de traducir un algoritmo a código

¿Qué se entiende por la complejidad temporal de un algoritmo?

• El número de líneas de código
• El tiempo que tarda en compilar
• La cantidad de memoria que usa
• La cantidad de tiempo que consume al ejecutarse en función del tamaño de la entrada

¿Qué representa O(n) en la notación Big-O?

• Tiempo constante
• Tiempo cuadrático
• Tiempo lineal
• Tiempo exponencial

¿Cuál es la complejidad temporal de un algoritmo que compara todos los pares posibles en una lista?

• O(1)
• O(n)
• O(log n)
• O(n²)

¿Cuál es la complejidad de un algoritmo que ejecuta una instrucción única, sin importar el tamaño de la entrada?

• O(n)
• O(1)
• O(n²)
• O(log n)

Si un algoritmo tiene complejidad O(n²), ¿cómo crecerá su tiempo de ejecución si se duplica el tamaño de la entrada?

• Se cuadruplicará
• Se duplicará
• Se mantendrá igual
• Se reducirá a la mitad

¿Qué ocurre con el tiempo de ejecución de un algoritmo de complejidad O(n!) al aumentar ligeramente el tamaño de entrada?

• Aumenta de forma extrema
• No cambia
• Aumenta de forma moderada
• Disminuye debido al factorial

¿Qué describe mejor un algoritmo con complejidad O(log n)?

• Su tiempo de ejecución crece linealmente con la entrada
• Su tiempo de ejecución se reduce con entradas más grandes
• Su tiempo de ejecución crece muy lentamente incluso si la entrada aumenta
• Su tiempo de ejecución es constante sin importar la entrada

¿Cuál de las siguientes opciones es un ejemplo de complejidad polinómica?

• O(2ⁿ)
• O(n!)
• O(n³)
• O(log n)

¿Qué tipo de complejidad tiene un algoritmo cuya ejecución se duplica por cada incremento en el tamaño de entrada?

• Lineal
• Polinómica
• Exponencial
• Constante