Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál de estos tiempos de ejecución es polinómico?

1. AO(n³)
2. BO(2ⁿ)
3. CO(n!)
4. DO(nⁿ)

¿Cuál es la complejidad temporal en el mejor caso del ordenamiento por inserción, sobre un array ya ordenado?

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(n log n)

¿Cuál es la complejidad temporal de hallar el valor más grande de un array no ordenado de n números?

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)

¿Cuál es la solución de la recurrencia T(n) = 2T(n − 1) + O(1)?

1. AO(2ⁿ)
2. BO(n²)
3. CO(n log n)
4. DO(n)

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

1. AO(log n)
2. BO(1)
3. CO(n)
4. DO(n²)

Un algoritmo voraz (greedy):

1. APrueba todas las soluciones posibles
2. BSiempre da la solución óptima
3. CSolo usa recursión
4. DToma la mejor decisión local en cada paso

Un problema es NP-completo si:

1. AEs imposible de resolver
2. BEstá fuera de NP pero es más difícil que todos los problemas NP, como el problema de la parada
3. CSe puede resolver en tiempo polinómico
4. DEstá en NP y todo problema NP se reduce a él en tiempo polinómico

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 7}), aproximadamente n^2,81
4. DΘ(n²)