Prerrequisito – Análisis de Algoritmos | Juego 1 , Juego 2 , Juego 3 , Juego 4 , Juego 5
Que-1. ¿Resuelve la siguiente relación de recurrencia?
T(n) = 7T(n/2) + 3n^2 + 2
(a) O(n^2.8)
(b) O(n^3)
(c) θ(n^2.8)
(d) θ(n ^3)
Explicación:
T(n) = 7T(n/2) + 3n^2 + 2
Como se puede ver en la fórmula anterior:
a = 7, b = 2 y f(n) = 3n^2 + 2
Entonces, f (n) = O(n^c), donde c = 2.
Cae en el caso 1 del teorema del maestro
: logb(a) = log2(7) = 2.81 > 2
Del primer caso del teorema del maestro se sigue que T( n) = θ(n^2.8) e implica tanto O(n^2.8) como O(n^3).
Por lo tanto, las opciones (a), (b) y (c) son opciones correctas.
Que-2. Ordene las siguientes funciones en orden decreciente de su complejidad asintótica (O grande):
f1(n) = n^√n , f2(n) = 2^n, f3(n) = (1.000001)^n , f4( n) = n^(10)*2^(n/2)
(a) f2> f4> f1> f3
(b) f2> f4> f3> f1
(c) f1> f2> f3> f4
(d) f2 > f1> f4> f3
Explicación:
f2 > f4 porque podemos escribir f2(n) = 2^(n/2)*2^(n/2), f4(n) = n^(10)*2^(n/2) que claramente muestra que f2 > f4
f4 > f3 porque podemos escribir f4(n) = n^10.〖√2〗^n = n10.(1.414)n , lo que muestra claramente que f4> f3
f3> f1:
f1 (n) = n^√n toma log ambos lados log f1 = √n log n
f3 (n) = (1.000001)^n toma log ambos lados log f3 = n log(1.000001), podemos escribir como log f3 = √n*√n log(1.000001) y √n > log(1.000001).
Entonces, el orden correcto es f2> f4> f3> f1. La opción (b) es correcta.
Que-3. f(n) = 2^(2n)
¿Cuál de las siguientes representa correctamente la función anterior?
(a) O(2^n)
(b) Ω(2^n)
(c) Θ(2^n)
(d) Ninguno de estos
Explicación: f(n) = 2^(2n) = 2^n*2^n
La opción (a) dice f(n)<= c*2n, lo cual no es cierto. La opción (c) dice que c1*2n <= f(n) <= c2*2n, se cumple el límite inferior pero no se cumple el límite superior. La opción (b) dice que c*2n <= f(n) esta condición se cumple, por lo que la opción (b) es correcta.
Que-4. ¿En cuál de las siguientes relaciones de recurrencia se puede aplicar el teorema de Master?
(a) T (n) = 2T (n/2) + 2^n
(b) T (n) = 2T (n/3) + sin(n)
(c) T (n) = T (n-2 ) + 2n^2 + 1
(d) Ninguno de estos
Explicación: el teorema maestro se puede aplicar a la relación de recurrencia del siguiente tipo
T (n) = aT (n/b) + f (n) (función divisoria) & T (n) = aT (nb) + f (n) (Función decreciente)
La opción (a) es incorrecta porque para aplicar el teorema de Master, la función f(n) debe ser polinomial.
La opción (b) es incorrecta porque para aplicar el teorema maestro f(n) debe ser una función monótonamente creciente.
La opción (d) no es del tipo mencionado anteriormente, por lo que la respuesta correcta es (c) porque T (n) = T (n-2) + 2n^2 + 1 se considerará como T (n) = T (n-2) ) + 2n^2 que está en forma de función decreciente.
Que-5. T(n) = 3T(n/2+ 47) + 2n^2 + 10*n – 1/2. T(n) será
(a) O(n^2)
(b) O(n^(3/2))
(c) O(n log n)
(d) Ninguno de estos
Explicación: para valores más altos de n, n/2 >> 47, podemos ignorar 47, ahora T(n) será
T(n) = 3T(n/2)+ 2*n^2 + 10*n – 1/2 = 3T(n/2)+ O(n^2)
Aplicar el teorema maestro, es el caso 3 del teorema maestro T(n) = O(n^2).
La opción (a) es correcta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA