Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

1. ATheta grande (Big Theta)
2. BOmega grande (Big Omega)
3. CO grande (Big O)
4. DOmega pequeña (little omega)

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

1. AExponencial
2. BLineal
3. CLogarítmico
4. DPolinómico

¿Cuál es el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

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

¿Cuál es la solución de la recurrencia T(n) = 2T(n/2) + O(1)?

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

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AOrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque
2. BEjecuta una búsqueda en anchura y se queda con el árbol BFS
3. CElimina la arista más cara hasta que no quedan ciclos
4. DHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol

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

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

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 el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
2. BW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
3. CPorque n siempre es pequeño
4. DPorque solo funciona para W = 0

¿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 log n)
2. BO(n √n)
3. CO(n²)
4. DO(n)