Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿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(n²)
4. DO(log n)

¿Qué estrategia de diseño usa merge sort?

1. AProgramación dinámica
2. BDivide y vencerás
3. CElección voraz
4. DFuerza bruta

¿Qué notación describe una cota superior del crecimiento?

1. AOmega grande (Big Omega)
2. BTheta grande (Big Theta)
3. CO grande (Big O)
4. DOmega pequeña (little omega)

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

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

¿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 usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
3. CLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
4. DEl ordenamiento por inserción es O(n log n) en el peor caso

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(log n)
2. BO(n)
3. CO(n²)
4. DO(2ⁿ)

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)

Los caminos simples más cortos pueden hallarse en tiempo polinómico. ¿Qué se sabe de hallar el camino simple más largo entre dos vértices en un grafo general?

1. AEs indecidible
2. BPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo
3. CSiempre puede resolverse en O(V + E)
4. DEs NP-difícil