Solución de una relación de recurrencia utilizando método de iteración

StackOverflow https://stackoverflow.com/questions/2053459

  •  20-09-2019
  •  | 
  •  

Pregunta

Considere este ejemplo: 

T(n) = T(7n/8) + 2n

asumí T (1) = 0

y trató de resolverlo de la siguiente manera 

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)

pero no podía llegar a ninguna conclusión acerca de esto. Estoy confundido acerca de lo que debería hacer en el siguiente paso.

¿Fue útil?

Solución

Su enfoque es sonido, pero se podrán ver qué hacer si se vuelve a escribir un poco diferente: 

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

Ahora, vamos k tienden al infinito y ver lo que sucede. Sería de gran ayuda si usted está familiarizado con serie geométrica .

Otros consejos

T (n) = T (7n / 8) + 2n = 2n * (1 + 7/8 + (7/8) ^ 2 + ... (7/8) ^ Z) + T (1) donde Z =?

El único truco es encontrar Z. apuesto a un registro ayudará. En este momento ya es tarde, y no estoy pensando bien, pero ... que no es necesario añadir múltiples 2n.

Editar:. Z es la cantidad de tiempo que necesita para multiplicar n por 7/8 hasta obtener 1

Así, n * 7 ^ Z / 8 ^ Z = 1

(7/8) ^ Z = 1 / n

(8/7) ^ Z = n

Se desea resolver Z.

¿Qué tienes ahí en la última línea es un serie geométrica y hay un < a href = "http://en.wikipedia.org/wiki/Geometric_series#Formula" rel = "nofollow noreferrer"> fórmula para simplificar tal suma.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top