Hoja de ejercicios de Algoritmos y complejidad con soluciones

Un problema suele llamarse tratable si:

1. APuede resolverse en tiempo polinómico
2. BNo tiene solución
3. CSolo puede resolverse probando todas las posibilidades
4. DPuede resolverse en tiempo constante

¿Qué es un algoritmo de fuerza bruta?

1. AUno que se ejecuta en muchos procesadores
2. BUno que prueba todas las soluciones candidatas posibles
3. CUno que adivina una respuesta al azar
4. DUno que siempre usa recursión

¿Cuál es la complejidad temporal de la búsqueda lineal en un array no ordenado de n elementos (peor caso)?

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

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

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

¿Cuál es la solución de la recurrencia T(n) = T(n − 1) + O(n)?

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

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log n)

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

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

El ordenamiento por inserción se ejecuta en O(n) con una entrada ordenada. ¿Contradice esto la cota inferior Ω(n log n) de la ordenación por comparaciones?

1. ASí, pero solo para arrays de menos de 100 elementos
2. BSí, así que la cota inferior es errónea
3. CNo, porque el ordenamiento por inserción no es una ordenación por comparaciones
4. DNo, la cota inferior se aplica al peor caso entre todas las entradas, no a cada entrada