Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

1. AEl tiempo que tarda en un ordenador lento
2. BEl tiempo que tarda con la entrada más pequeña
3. CEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
4. DEl tiempo máximo que tarda entre todas las entradas de tamaño n

¿Cuál es la O grande de 3n² + 5n + 2?

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

¿Qué es un algoritmo de fuerza bruta?

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

Una función ejecuta un bucle de n iteraciones y después, por separado, otro bucle de n iteraciones. ¿Cuál es su complejidad temporal?

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

¿Cuál es la complejidad temporal del algoritmo de Bellman-Ford en un grafo con V vértices y E aristas?

1. AO(V³ × E)
2. BO(V + E)
3. CO(V × E)
4. DO(E log V)

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

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

¿Cuál es la diferencia entre un problema indecidible y uno intratable?

1. ALos problemas indecidibles están en NP, mientras que los intratables están en P
2. BAmbos significan que el problema no tiene ningún algoritmo
3. CLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
4. DUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento

¿Cómo se comparan n! y 2ⁿ para n grande?

1. An! es O(n²)
2. B2ⁿ crece más deprisa que n!
3. Cn! crece más deprisa que 2ⁿ
4. DCrecen al mismo ritmo