Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿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(k log n)
2. BO(n log n)
3. CO(n + k)
4. DO(n²)

¿Cuál es la complejidad temporal de hallar el valor más grande de un array no ordenado de n números?

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

¿Qué es un algoritmo de fuerza bruta?

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

La recurrencia T(n) = 2T(n/2) + O(n) tiene como solución:

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

¿Cuál es el tiempo de ejecución del radix sort LSD sobre n enteros de d dígitos en base k?

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

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

1. ALineal
2. BLogarítmica
3. CConstante
4. DExponencial

¿Cómo detecta el algoritmo de Bellman-Ford un ciclo de peso negativo alcanzable desde el origen?

1. ACuenta los ciclos con una búsqueda en profundidad
2. BComprueba si alguna arista tiene peso negativo
3. CTras V − 1 rondas, comprueba si alguna arista todavía puede relajarse
4. DEjecuta dos veces el algoritmo de Dijkstra y compara los dos resultados de distancias

¿En qué variante del problema de la mochila la regla voraz «tomar los objetos por orden de valor por unidad de peso» da siempre una respuesta óptima?

1. ALa mochila 0/1, en la que los objetos deben tomarse siempre enteros
2. BEn ninguna de las dos
3. CEn ambas variantes
4. DLa mochila fraccionaria, en la que los objetos pueden dividirse