Mat. Discretas - Actividad en clase - 03 Abril 2025

Front

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

Back

La posibilidad de resolver un problema en tiempo razonable con un algoritmo.

Front

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

Back

La cantidad de tiempo que consume al ejecutarse en función del tamaño de la entrada

Front

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

Back

Tiempo lineal

Front

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

Back

O(n²)

Front

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

Back

O(1)

Front

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

Back

Se cuadruplicará

Front

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

Back

Aumenta de forma extrema

Front

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

Back

Su tiempo de ejecución crece muy lentamente incluso si la entrada aumenta

Front

¿Cuál de las siguientes opciones es un ejemplo de complejidad polinómica? O(2ⁿ), O(n!), O(n³), O(log n)

Back

O(n³)

Front

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

Back

Exponencial