Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál de estas crece más despacio a medida que n se hace grande?

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

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

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

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

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

La búsqueda en anchura (BFS) en un grafo no ponderado encuentra:

1. AEl árbol de expansión mínima
2. BUn orden topológico en todos los grafos
3. CLos caminos más cortos en grafos que contienen aristas con pesos negativos
4. DLos caminos más cortos en número de aristas desde el nodo inicial

La programación dinámica es útil cuando un problema tiene:

1. ANingún subproblema en absoluto, así que puede resolverse en un solo paso
2. BSubproblemas superpuestos y subestructura óptima
3. CSolo entradas aleatorias
4. DUn único bucle

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

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

¿Cuál de estos problemas de satisfacibilidad se sabe que es resoluble en tiempo polinómico?

1. ASAT general sobre fórmulas en forma normal conjuntiva
2. B2-SAT, donde cada cláusula tiene como mucho dos literales
3. CLa satisfacibilidad de circuitos
4. D3-SAT, donde cada cláusula tiene exactamente tres literales

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

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