Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

1. A8 segundos
2. B1 segundo
3. C4 segundos
4. D2 segundos

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

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

El tiempo de ejecución de un algoritmo es O(n). ¿Cómo se llama este crecimiento?

1. ALogarítmico
2. BConstante
3. CCuadrático
4. DLineal

¿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 20
2. BUnas 1,000
3. CUnas 500,000
4. DUnas 100

Un algoritmo voraz (greedy):

1. APrueba todas las soluciones posibles
2. BToma la mejor decisión local en cada paso
3. CSiempre da la solución óptima
4. DSolo usa recursión

¿Cuál es el tiempo de ejecución del radix sort LSD sobre n enteros de d dígitos en base k?

1. AO(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

Un problema es NP-completo si:

1. AEstá en NP y todo problema NP se reduce a él en tiempo polinómico
2. BEstá fuera de NP pero es más difícil que todos los problemas NP, como el problema de la parada
3. CSe puede resolver en tiempo polinómico
4. DEs imposible de resolver

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

1. ALas claves deben ordenarse primero
2. BMuchas claves pueden colisionar en el mismo bucket
3. CLas funciones hash son lentas
4. DLos arrays tienen acceso O(n)