Para los parámetros a y b, ambos de los cuales son ω(1), T(n)=T(n 1/a )+1, y T(b)=1. Entonces T(n) es
(A) Θ(log a log b n)
(B) Θ(log ab n)
(C) Θ(log b log a n)
(D) Θ(log 2 log 2 n)
Respuesta: (A)
Explicación: Dado,
T(n) = T(n1/a)+1, T(b) = 1
Ahora, usando el método iterativo,
= T(n) = [T(n1/a2)+1] + 1 = [T(n1/a3)+1] + 2 = [T(n1/a4)+1] + 3 . . . = [T(n1/ak)+1] + (k-1) = T(n1/ak) + k
Dejar,
→ n1/ak = b → log(n1/ak) = log(b) → ak = log(n) / log (b) = logb(n) → k = logalogb(n)
Por lo tanto,
= T(n1/ak) + k = T(b) + logalogb(n) = 1 + logalogb(n) = Θ(logalogb(n))
La opción (A) es correcta.
Cuestionario de esta pregunta
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