Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿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(1)
3. CO(n)
4. DO(log n)

¿Qué significa que una operación se ejecute en tiempo O(1)?

1. ASu tiempo de ejecución no crece con el tamaño de la entrada
2. BSiempre tarda exactamente un segundo
3. CSolo puede ejecutarse una vez
4. DProcesa exactamente un elemento por segundo de tiempo de ejecución

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

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

¿Cuántos niveles tiene la recursión de merge sort para un array de n elementos?

1. AUnos log₂ n
2. BUnos n / 2
3. CUnos n
4. DUnos √n

La recurrencia T(n) = 2T(n/2) + O(n) tiene como solución:

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

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

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

Tomar los dos extremos de cada arista de un emparejamiento maximal da un recubrimiento de vértices. ¿Cómo de bueno es este recubrimiento?

1. AComo mucho log n veces el mínimo
2. BSiempre es un recubrimiento de vértices mínimo
3. CComo mucho el doble del tamaño de un recubrimiento de vértices mínimo
4. DDe calidad desconocida respecto al óptimo

¿Cuál es la complejidad temporal de construir un montículo binario a partir de n elementos sin ordenar con el método ascendente (bottom-up)?

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