Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué complejidad suele tener un algoritmo con dos bucles anidados que se ejecutan n veces cada uno?

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

¿Qué es la memoización?

1. AEscribir comentarios junto a cada línea de código
2. BGuardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
3. CLiberar memoria cuando una función termina
4. DConvertir automáticamente la recursión en un bucle equivalente para que no haga falta pila de llamadas

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

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

¿Qué algoritmo de ordenación es estable?

1. AQuicksort (versión in situ habitual)
2. BOrdenamiento por selección (versión habitual)
3. CHeap sort
4. DMerge sort

¿Qué calcula el algoritmo de Floyd-Warshall y con qué rapidez?

1. AUn orden topológico en O(V²)
2. BLos caminos más cortos desde un vértice origen hasta todos los demás en O(V + E)
3. CLos caminos más cortos entre todos los pares de vértices en O(V³)
4. DUn árbol de expansión mínima en O(E log V)

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 primero la actividad con menos solapamientos y repetir con las compatibles
3. CElegir la actividad que empieza antes
4. DElegir la actividad que termina antes y repetir con las compatibles

El problema de la mochila 0/1 resuelto con programación dinámica requiere un tiempo O(nW). ¿Por qué se llama pseudopolinómico?

1. APorque n siempre es pequeño
2. BPorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
3. CW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
4. DPorque solo funciona para W = 0

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² log n)
4. DΘ(n³)