Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por mezcla (merge sort)?

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

¿Cuál de estas crece más despacio a medida que n se hace grande?

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

¿Cómo se llama un crecimiento O(2ⁿ)?

1. AExponencial
2. BLogarítmico
3. CPolinómico
4. DLineal

¿Cuál es la complejidad temporal de quicksort en el peor caso?

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

¿Es correcto decir que un algoritmo O(n²) también es O(n³)?

1. ANo, porque n³ es menor que n² para n grande
2. BSí, pero solo si n es menor que 100
3. CSí, porque O grande es una cota superior y n² no crece más deprisa que n³
4. DNo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función

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

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

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n^{log₂ 7}), aproximadamente n^2,81
4. DΘ(n²)

¿Qué se deduciría si alguien hallara un algoritmo de tiempo polinómico para un problema NP-completo?

1. ATodo problema de NP podría resolverse en tiempo polinómico, así que P = NP
2. BEl problema de la parada se volvería decidible
3. CSolo ese problema pasaría a P
4. DTodos los algoritmos de tiempo exponencial pasarían de inmediato a ejecutarse en tiempo lineal