Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

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

Un algoritmo O(n) tarda 3 segundos para n = 1 millón. ¿Aproximadamente cuánto tarda para n = 2 millones?

1. A3 segundos
2. B9 segundos
3. C12 segundos
4. D6 segundos

Acceder a un elemento de un array por su índice requiere:

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

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

¿Cuál es la complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

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

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

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

¿Cómo se clasifica el problema del viajante?

1. AEstá en P porque el algoritmo de Dijkstra lo resuelve visitando cada ciudad una vez
2. BLa versión de decisión está en P, pero la de optimización es NP-completa
3. CLa versión de decisión es NP-completa y la de optimización es NP-difícil
4. DEs indecidible

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