Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

1. AAdivinar, comprobar, repetir
2. BOrdenar, buscar, devolver
3. CLeer, calcular, escribir
4. DDividir, vencer, combinar

¿Qué complejidad suele tener un algoritmo con dos bucles anidados que se ejecutan n veces cada uno?

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

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

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

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

1. ALogarítmica
2. BConstante
3. CLineal
4. DExponencial

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para j = 1 hasta i: hacer trabajo O(1)?

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

¿Qué definición de la clase P es correcta?

1. AProblemas de decisión resolubles por un algoritmo determinista en tiempo polinómico
2. BProblemas que pueden resolverse en paralelo
3. CProblemas cuyas soluciones pueden comprobarse, pero nunca hallarse, en tiempo polinómico
4. DProblemas que necesitan tiempo exponencial en cualquier ordenador

¿Qué afirmación sobre seleccionar el k-ésimo elemento más pequeño de un array no ordenado es correcta?

1. AQuickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
2. BQuickselect se ejecuta en O(log n) en el peor caso, porque solo hace recursión en un lado del pivote
3. CLa selección siempre necesita Ω(n log n) porque requiere ordenar
4. DLa selección solo es posible en O(n²)