Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es un algoritmo de fuerza bruta?

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

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

1. ALeer, calcular, escribir
2. BDividir, vencer, combinar
3. COrdenar, buscar, devolver
4. DAdivinar, comprobar, repetir

¿Cómo funciona el ordenamiento por selección?

1. ADivide el array en mitades y las mezcla
2. BIntercambia repetidamente elementos vecinos que están en el orden incorrecto
3. CInserta cada elemento en una parte ordenada creciente mediante desplazamientos
4. DBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio

¿Cuál es la complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

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

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

1. ATodos los logaritmos en informática tienen base 10, así que va implícita
2. BLa base solo importa para n pequeño
3. CLos logaritmos en distintas bases solo difieren en un factor constante
4. DLos logaritmos siempre se redondean a enteros

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

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

El problema de la parada demuestra que:

1. ATodo programa acaba deteniéndose
2. BNingún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
3. CAlgunos programas se ejecutan más rápido en ordenadores más rápidos, así que la parada depende del hardware
4. DHay que evitar los bucles

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

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