Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

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

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

1. AO (O grande)
2. Bo (o pequeña)
3. CΘ (Theta grande)
4. DΩ (Omega grande)

Un bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

1. AUnas n
2. BUnas n²
3. CUnas log₂ n
4. DUnas n / 2

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AEjecuta una búsqueda en anchura y se queda con el árbol BFS
2. BOrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque
3. CHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
4. DElimina la arista más cara hasta que no quedan ciclos

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

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

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

¿Cómo detecta el algoritmo de Bellman-Ford un ciclo de peso negativo alcanzable desde el origen?

1. ACuenta los ciclos con una búsqueda en profundidad
2. BEjecuta dos veces el algoritmo de Dijkstra y compara los dos resultados de distancias
3. CTras V − 1 rondas, comprueba si alguna arista todavía puede relajarse
4. DComprueba si alguna arista tiene peso negativo

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

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