Hoja de ejercicios de Algoritmos y complejidad con soluciones

La complejidad espacial mide:

1. ALa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
2. BEl tamaño físico del ordenador
3. CEl espacio en disco del archivo del programa una vez compilado
4. DEl número de líneas de código

¿Qué exige la búsqueda binaria de su entrada?

1. AEl array debe estar ordenado
2. BLa longitud del array debe ser una potencia de dos
3. CEl array solo debe contener números positivos
4. DEl array no debe tener más de 1000 elementos

Acceder a un elemento de un array por su índice requiere:

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

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

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

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

1. AAlgoritmo de Dijkstra
2. BAlgoritmo de Kruskal
3. CBúsqueda en profundidad (DFS)
4. DBellman-Ford es necesario en todos los casos

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

¿Cuál es la solución de la recurrencia T(n) = 2T(n/2) + n log n?

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

¿Está 2²ⁿ en O(2ⁿ)?

1. ASí, porque los factores constantes del exponente se ignoran siempre en la notación O grande
2. BNo, porque 2²ⁿ = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite
3. CSí, porque ambos son exponenciales
4. DNo, porque 2²ⁿ crece más despacio que 2ⁿ