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. A4 segundos
2. B2 segundos
3. C1 segundo
4. D8 segundos

¿Qué significa f(n) = Θ(g(n))?

1. Af es siempre menor que g para todo n, así que g la acota por arriba pero nunca por abajo
2. Bf crece estrictamente más deprisa que g
3. Cf crece al mismo ritmo que g, acotada por arriba y por abajo por múltiplos constantes de g
4. Df crece estrictamente más despacio que g

El tiempo de ejecución de un algoritmo es O(n). ¿Cómo se llama este crecimiento?

1. AConstante
2. BCuadrático
3. CLineal
4. DLogarítmico

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

1. AElegir primero la actividad más corta
2. BElegir la actividad que empieza antes
3. CElegir primero la actividad con menos solapamientos y repetir con las compatibles
4. DElegir la actividad que termina antes y repetir con las compatibles

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

1. AEl ordenamiento por inserción es O(n log n) en el peor caso
2. BLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
3. CEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
4. DEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
2. BElimina la arista más cara hasta que no quedan ciclos
3. CEjecuta una búsqueda en anchura y se queda con el árbol BFS
4. DOrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque

¿Qué dos cosas hay que demostrar para probar que un problema de decisión X es NP-completo?

1. AQue X no tiene algoritmo polinómico y que X es decidible
2. BQue X está en P y que X se reduce a SAT
3. CQue X está en NP y que un problema NP-completo conocido se reduce a X en tiempo polinómico
4. DQue X se reduce a un problema de P y que X está en NP

¿Cuál de estos problemas de satisfacibilidad se sabe que es resoluble en tiempo polinómico?

1. A2-SAT, donde cada cláusula tiene como mucho dos literales
2. BSAT general sobre fórmulas en forma normal conjuntiva
3. CLa satisfacibilidad de circuitos
4. D3-SAT, donde cada cláusula tiene exactamente tres literales