Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?

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

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

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

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

¿Qué algoritmo de ordenación es estable?

1. AOrdenamiento por selección (versión habitual)
2. BHeap sort
3. CQuicksort (versión in situ habitual)
4. DMerge sort

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

1. AEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
2. BEl ordenamiento por inserción es O(n log n) en el peor caso
3. CLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
4. DEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. AMerge sort ya es O(n)
2. BMerge sort no tiene estructura recursiva
3. CSus subproblemas no se solapan, así que no hay nada que reutilizar
4. DLa programación dinámica solo funciona con problemas de grafos, no con arreglos

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

Un problema es NP-completo si:

1. ASe puede resolver en tiempo polinómico
2. BEs imposible de resolver
3. CEstá en NP y todo problema NP se reduce a él en tiempo polinómico
4. DEstá fuera de NP pero es más difícil que todos los problemas NP, como el problema de la parada