Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es la memoización?

1. ALiberar memoria cuando una función termina
2. BEscribir comentarios junto a cada línea de código
3. CConvertir automáticamente la recursión en un bucle equivalente para que no haga falta pila de llamadas
4. DGuardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas

¿Cuál es el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

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

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

1. AQuicksort
2. BOrdenamiento por montículos (heap sort)
3. COrdenamiento de burbuja (bubble sort)
4. DOrdenamiento por mezcla (merge sort)

Un algoritmo voraz (greedy):

1. ASolo usa recursión
2. BToma la mejor decisión local en cada paso
3. CPrueba todas las soluciones posibles
4. DSiempre da la solución óptima

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 2 monedas; el óptimo es 2
2. BEl voraz usa 4 monedas; el óptimo es 3
3. CEl voraz usa 3 monedas; el óptimo es 2
4. DEl voraz usa 3 monedas; el óptimo es 3

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

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

¿Qué cota es correcta para log(n!)?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(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)