No pude encontrar una solución a mi pregunta, ya que generalmente la solución (en términos grandes de Os) es lo que se pregunta, pero no la recurrencia desenrollada. Si eso ya fue preguntado solo dímelo y lo eliminaré.

Tenía esta pregunta en mi prueba Algorithms and Data Structures en uni, y he estado golpeándome la cabeza con esto por un tiempo. Principalmente porque no entiendo cómo había llegado a la respuesta correcta.

Tengo la siguiente relación:

T(1)=2
T(n)=2T(n-1)+2 for n>=2 

Las respuestas son:

1. T(n)= 2^n+1 -2
2. T(n)= none of the answers are correct 
3. T(n)= 1/2n(n+1)-1 
4. T(n)= 2^n+1 -2-n
5. T(n)= n+ (-1)^n

Esto es lo que intenté:

T(1)=2
T(n)=2T(n-1)+2 -> T(n-1) = T(n-2)+2 
    =2T(n-2)+2+2 
    =2T(n-2)+4 -> T(n-2) = T(n-3)+3 
    =2T(n-3)+2+4 
    =2T(n-3)+6 so then -> 2T(n-k)+2k and if n=k 2T(n-n)+2n -> 2T(0)+2n 

PERO no tengo el caso T (0). Además, este método finalmente me llevaría a conocer la gran solución O, aunque no es lo que estoy tratando de encontrar ahora.

¿Alguien sería tan amable de explicarme el método correcto para llegar a la respuesta correcta?

Gracias.

0
Tommaso Pellegrini 20 jul. 2020 a las 17:14

4 respuestas

La mejor respuesta

No desenrolle las respuestas, solo verifíquelas.

Entonces, para cada una de las posibles respuestas, verifique si T(1)=2, y si la sustitución de T(n) da igualdad para T(n)=2T(n-1)+2. Entonces, para la primera respuesta T(1)=2^(n+1)-2=4-2=2 (como debería ser) y:

T(n) =?= 2*T(n)+2
2^(n+1)-2 =?= 2*(2^(n)-2)+2

Usando simplemente =? = Para significar la igualdad a verificar. Simplificar ambos lados conduce a:

2^(n+1)-2 =?= 2*2^(n)-2

El resto te lo dejo a ti

1
Hans Olsson 20 jul. 2020 a las 14:36

La manera fácil es notar que es exponencial, y luego simplemente verifique las dos respuestas exponenciales ...

Pero si quieres desenrollarlo, obtienes:

T(n) = 2 + 2T(n-1)
     = 2 + 4 + 4T(n-2)
     = 2 + 4 + 8 + 8T(n-3)
     = 2 + 4 + 8 + ... + 2^(n-1)T(1)
     = 2 + 4 + 8 + ... + 2^n

Y luego reconoces la progresión y haces:

T(n) = 2T(n) - T(n)
     = 2^(n+1) - 2
0
Matt Timmermans 20 jul. 2020 a las 15:40

T (n) = 2T (n-1) +2 es equivalente a T (n) +2 = 2 (T (n-1) +2).

Entonces T (n) +2 = 2 ^ (n-1) (T (1) +2) = 2 ^ (n-1) * 4 = 2 ^ (n + 1). Por lo tanto, T (n) = 2 ^ (n + 1) -2.

1
Paul Hankin 20 jul. 2020 a las 19:00

Este problema es similar a https://cs.stackexchange.com/questions/18900/how-do-i-show-tn-2tn-1-k-is-o2n

Quizás también entiendas cómo resolver esto ...

0
Yash Shah 20 jul. 2020 a las 14:21