Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál de estos tiempos de ejecución es polinómico?

1. AO(n!)
2. BO(nⁿ)
3. CO(2ⁿ)
4. DO(n³)

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

1. AEl tiempo máximo que tarda entre todas las entradas de tamaño n
2. BEl tiempo que tarda en un ordenador lento
3. CEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
4. DEl tiempo que tarda con la entrada más pequeña

¿Qué es la recursión?

1. AUn método de ordenación
2. BUn bucle que nunca termina
3. CUn tipo de estructura de datos
4. DUna función que se llama a sí misma con entradas más pequeñas

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

1. ALogarítmica
2. BConstante
3. CLineal
4. DExponencial

¿Qué algoritmo de ordenación es estable?

1. AHeap sort
2. BOrdenamiento por selección (versión habitual)
3. CMerge sort
4. DQuicksort (versión in situ habitual)

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. AMerge sort ya es O(n)
2. BMerge sort no tiene estructura recursiva
3. CSus subproblemas no se solapan, así que no hay nada que reutilizar
4. DLa programación dinámica solo funciona con problemas de grafos, no con arreglos

¿Cuál es el tiempo de ejecución del algoritmo de Dijkstra con un montículo binario en un grafo con V vértices y E aristas?

1. AO(V³)
2. BO(V × E)
3. CO((V + E) log V)
4. DO(V + E)

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para (j = i; j ≤ n; j = j + i) hacer trabajo O(1)?

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