Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

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

¿Cuál es la complejidad temporal de la búsqueda lineal en un array no ordenado de n elementos (peor caso)?

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

¿Qué algoritmo de ordenación elige un pivote y divide el array en elementos menores y mayores?

1. AQuicksort
2. BOrdenamiento de burbuja
3. COrdenamiento por inserción
4. DMerge sort

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

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

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

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

¿Cuál es la complejidad temporal de multiplicar dos matrices n × n con el triple bucle estándar?

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

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³)

¿Cuáles son los costes de tiempo y espacio de calcular el n-ésimo número de Fibonacci con un bucle que guarda solo los dos últimos valores?

1. ATiempo O(n) y espacio O(n)
2. BTiempo O(log n) y espacio O(n)
3. CTiempo O(2ⁿ) y espacio O(1)
4. DTiempo O(n) y espacio O(1)