La solución de la relación de recurrencia
T(m) = T(3m / 4) + 1 es :
(A) θ (lg m)
(B) θ (m)
(C) θ (mlg m)
(D) θ (lglg m)
Respuesta: (A)
Explicación: Dado,
T(m) = T(3m/4) + 1 = T(m/(4/3)) + 1
En este problema usamos el Teorema de Master :
T(m) = aT(m/b) + n^k logn
Compara ambas ecuaciones,
we get a = 1 and b = 4/3 and k=0
Ahora encuentre (log a base b), es decir, (log 1 base 4/3), que es mayor que (4/3) 0
Y siempre que, (log b (a)) y b k sea mayor que la respuesta es f( m)* log(m)
Aquí, f(m) = 1
Por lo tanto, la respuesta correcta 1*log(m) = log(m)
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