Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué notación describe una cota inferior del crecimiento?

1. AO (O grande)
2. BΩ (Omega grande)
3. CΘ (Theta grande)
4. Do (o pequeña)

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

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

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

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

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

1. ALineal
2. BLogarítmica
3. CExponencial
4. DConstante

Un quicksort usa siempre el primer elemento como pivote. ¿Con qué entrada muestra su comportamiento de peor caso?

1. AUn array en orden aleatorio
2. BUn array de longitud 2
3. CUn array con todos sus elementos distintos
4. DUn array que ya está ordenado

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

1. AO(m + n)
2. BO(mn)
3. CO(2^m+n)
4. DO(mn log n)

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

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

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

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