Relación de recurrencia Tallas de tareas
-
27-10-2019 - |
Pregunta
Aquí está la pregunta:
Resuelva la recurrencia obteniendo un theta unido para t (n) dado que t (1) = theta (1).
T(n) = n + T(n-3)
Intento de solución:
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
Cuando verifico dos veces para ver si la solución se ajusta a la recurrencia, no funciona.
Solución
El problema era que estaba obteniendo la suma equivocada. No comienza en 0, ya que su última función T fue t (n-(n-1)), lo que significa que la anterior era t (n-4)). Entonces la suma comienza a las 4 y sube hasta n.
Si no sabe cómo encontrar la suma de esto, le sugiero que vea algunas de las pruebas de la fórmula de suma. Así es como se ve la solución.
T(n) = T(n-3) + n
= T(n-6) + (n-3) + n
= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]
= T(1) + [4 + 7 + ... + n]
= theta(1) + (4 + n) * (n - 1)/6
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow