Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

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

¿Qué exige la búsqueda binaria de su entrada?

1. AEl array solo debe contener números positivos
2. BLa longitud del array debe ser una potencia de dos
3. CEl array no debe tener más de 1000 elementos
4. DEl array debe estar ordenado

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

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

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

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

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

1. ABellman-Ford es necesario en todos los casos
2. BAlgoritmo de Kruskal
3. CBúsqueda en profundidad (DFS)
4. DAlgoritmo de Dijkstra

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

El ordenamiento por inserción se ejecuta en O(n) con una entrada ordenada. ¿Contradice esto la cota inferior Ω(n log n) de la ordenación por comparaciones?

1. ASí, pero solo para arrays de menos de 100 elementos
2. BNo, la cota inferior se aplica al peor caso entre todas las entradas, no a cada entrada
3. CSí, así que la cota inferior es errónea
4. DNo, porque el ordenamiento por inserción no es una ordenación por comparaciones

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

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