Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

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

¿Cuánto vale log₂ 1024?

1. A512
2. B32
3. C12
4. D10

¿Qué significa que una operación se ejecute en tiempo O(1)?

1. AProcesa exactamente un elemento por segundo de tiempo de ejecución
2. BSu tiempo de ejecución no crece con el tamaño de la entrada
3. CSolo puede ejecutarse una vez
4. DSiempre tarda exactamente un segundo

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

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

¿Qué mide el análisis amortizado?

1. AEl coste esperado con entradas aleatorias
2. BEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso
3. CEl coste de un algoritmo con la mejor entrada
4. DEl coste de la única operación más cara de toda la secuencia

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

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

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² log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), aproximadamente n^2,81
4. DΘ(n³)

¿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ⁿ