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!)

¿Qué notación describe una cota superior del crecimiento?

1. AO grande (Big O)
2. BOmega pequeña (little omega)
3. COmega grande (Big Omega)
4. DTheta grande (Big Theta)

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

1. A4 segundos
2. B8 segundos
3. C1 segundo
4. D2 segundos

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

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

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

1. AEl voraz usa 3 monedas; el óptimo es 2
2. BEl voraz usa 3 monedas; el óptimo es 3
3. CEl voraz usa 4 monedas; el óptimo es 3
4. DEl voraz usa 2 monedas; el óptimo es 2

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

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

La multiplicación de Karatsuba cumple T(n) = 3T(n/2) + O(n). ¿Cuál es la solución?

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

¿Cuál es el tiempo de ejecución del algoritmo de Dijkstra con un montículo binario en un grafo con V vértices y E aristas?

1. AO(V³)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V × E)