Risolvendo una relazione di ricorrenza utilizzando metodo di iterazione

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

  •  20-09-2019
  •  | 
  •  

Domanda

Si consideri questo esempio: 

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

ho pensato T (1) = 0

e cercato di risolvere nel modo seguente 

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)

, ma non ho potuto giungere ad una conclusione su questo. Sono confuso su cosa devo fare nella fase successiva.

È stato utile?

Soluzione

Il tuo approccio è il suono, ma vedrete che cosa fare se si riscrive in modo leggermente diverso: 

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

Ora, lasciate k tendono verso l'infinito e vedere cosa succede. Sarebbe utile se si ha familiarità con geometrica serie .

Altri suggerimenti

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

L'unico trucco è trovare Z. Scommetto un registro sarà di aiuto. Ci dispiace è tardi, e non sto pensando dritto, ma ... non dovrebbe essere necessario aggiungere 2n multipla.

Modifica:. Z è quanto tempo è necessario moltiplicare n per 7/8 fino ad ottenere 1

Quindi, n * 7 ^ Z / 8 ^ Z = 1

(7/8) ^ Z = 1 / n

(8/7) ^ Z = n

Si vuole risolvere per Z.

Che cosa hai lì nell'ultima riga è un geometrica serie e v'è un < a href = "http://en.wikipedia.org/wiki/Geometric_series#Formula" rel = "nofollow noreferrer"> formula di semplificare tale somma.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top