Hoja de ejercicios de Algoritmos y complejidad con soluciones

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

1. A4 segundos
2. B8 segundos
3. C1 segundo
4. D2 segundos

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

1. AQuicksort
2. BOrdenamiento por mezcla (merge sort)
3. COrdenamiento por montículos (heap sort)
4. DOrdenamiento de burbuja (bubble sort)

¿Qué clase de complejidad crece más rápido para n grande?

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

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

1. AElegir primero la actividad más corta
2. BElegir la actividad que empieza antes
3. CElegir la actividad que termina antes y repetir con las compatibles
4. DElegir primero la actividad con menos solapamientos y repetir con las compatibles

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

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

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

1. AΩ(n²)
2. BΩ(log n)
3. CΩ(n log n)
4. DΩ(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. ANo, la cota inferior se aplica al peor caso entre todas las entradas, no a cada entrada
2. BNo, porque el ordenamiento por inserción no es una ordenación por comparaciones
3. CSí, así que la cota inferior es errónea
4. DSí, pero solo para arrays de menos de 100 elementos

¿Cuál es la complejidad temporal de construir un montículo binario a partir de n elementos sin ordenar con el método ascendente (bottom-up)?

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