Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?

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

¿Qué algoritmo de ordenación elige un pivote y divide el array en elementos menores y mayores?

1. AOrdenamiento por inserción
2. BOrdenamiento de burbuja
3. CQuicksort
4. DMerge sort

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

1. AExponencial
2. BLogarítmico
3. CPolinómico
4. DLineal

La programación dinámica es útil cuando un problema tiene:

1. AUn único bucle
2. BNingún subproblema en absoluto, así que puede resolverse en un solo paso
3. CSolo entradas aleatorias
4. DSubproblemas superpuestos y subestructura óptima

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

1. AO(n + k)
2. BO(nk)
3. CO(k n log n)
4. DO(n log n + k log n)

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

1. AElegir primero la actividad más corta
2. BElegir la actividad que empieza antes
3. CElegir primero la actividad con menos solapamientos y repetir con las compatibles
4. DElegir la actividad que termina antes y repetir con las compatibles

¿Por qué la búsqueda binaria no da un tiempo O(log n) en una lista simplemente enlazada?

1. ALas comparaciones entre nodos de una lista enlazada son más lentas
2. BLa búsqueda binaria necesita al menos el doble de memoria
3. CLlegar al elemento central lleva O(n) pasos, porque no hay acceso directo por índice
4. DLas listas enlazadas no pueden ordenarse

¿Qué estableció el teorema de Cook-Levin?

1. AP no es igual a NP
2. BTodo problema NP puede resolverse en tiempo exponencial
3. CEl problema de la parada es indecidible
4. DEl problema de satisfacibilidad booleana (SAT) es NP-completo