Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es la complejidad temporal de la búsqueda en profundidad en un grafo almacenado como listas de adyacencia?

1. AO(V + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V²)

¿Cómo se llama un crecimiento O(2ⁿ)?

1. ALogarítmico
2. BPolinómico
3. CLineal
4. DExponencial

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

1. A8 segundos
2. B1 segundo
3. C2 segundos
4. D4 segundos

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

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

¿Aproximadamente cuántas comparaciones necesita la búsqueda binaria en el peor caso en un array ordenado de 1,000,000 de elementos?

1. AUnas 1,000
2. BUnas 100
3. CUnas 500,000
4. DUnas 20

¿Qué significa que un problema tenga subestructura óptima?

1. AEl problema puede resolverse en tiempo constante
2. BUna solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas
3. CTodos los subproblemas tienen el mismo tamaño
4. DEl problema tiene exactamente una solución óptima, que comparten todos sus subproblemas

¿Por qué cualquier búsqueda basada en comparaciones en un array ordenado necesita Ω(log n) comparaciones en el peor caso?

1. AUn árbol de decisión con n resultados posibles debe tener una profundidad de al menos log₂ n
2. BCada elemento debe compararse al menos una vez
3. CCada comparación tarda un tiempo logarítmico
4. DLa búsqueda binaria es el único algoritmo posible, y necesita log₂ n comparaciones

¿Qué algoritmo encuentra un árbol de expansión mínima añadiendo repetidamente la arista más barata que no forme un ciclo?

1. AAlgoritmo de Prim empezando desde un nodo
2. BAlgoritmo de Dijkstra
3. CFloyd-Warshall
4. DAlgoritmo de Kruskal