Hoja de ejercicios de Algoritmos y complejidad con soluciones

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

1. A8 segundos
2. B1 segundo
3. C2 segundos
4. D4 segundos

¿Qué significa que una operación se ejecute en tiempo O(1)?

1. ASu tiempo de ejecución no crece con el tamaño de la entrada
2. BSiempre tarda exactamente un segundo
3. CProcesa exactamente un elemento por segundo de tiempo de ejecución
4. DSolo puede ejecutarse una vez

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

1. ADividir, vencer, combinar
2. BOrdenar, buscar, devolver
3. CAdivinar, comprobar, repetir
4. DLeer, calcular, escribir

¿Qué afirmación sobre una función recursiva sin un caso base alcanzable es correcta?

1. ASigue llamándose a sí misma hasta que se desborda la pila de llamadas
2. BSe ejecuta en tiempo O(1)
3. CEl compilador siempre la convierte en un bucle que termina sin problemas
4. DDevuelve 0 automáticamente

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. AMerge sort ya es O(n)
2. BSus subproblemas no se solapan, así que no hay nada que reutilizar
3. CMerge sort no tiene estructura recursiva
4. DLa programación dinámica solo funciona con problemas de grafos, no con arreglos

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

1. AΩ(n²)
2. BΩ(n)
3. CΩ(log n)
4. DΩ(n log n)

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n log n)

¿Qué definición de la clase NP es correcta?

1. AProblemas de decisión cuyas respuestas afirmativas pueden verificarse en tiempo polinómico dado un certificado
2. BProblemas que no pueden resolverse en tiempo polinómico
3. CProblemas que no son polinómicos
4. DProblemas que ningún algoritmo puede resolver