La résolution d'une relation de récurrence en utilisant la méthode d'itération

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

  •  20-09-2019
  •  | 
  •  

Question

Prenons cet exemple: 

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

I supposé T (1) = 0

et a essayé de le résoudre de la manière suivante 

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)

mais je ne pouvais pas arriver à une conclusion à ce sujet. Je suis confus au sujet de ce que dois-je faire à l'étape suivante.

Était-ce utile?

La solution

Votre approche est saine, mais vous verrez ce qu'il faut faire si vous repassez légèrement différente: 

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

Maintenant, laissez-k ont tendance à l'infini et de voir ce qui se passe. Il serait utile si vous êtes familier avec série géométrique .

Autres conseils

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

Le seul truc est de trouver Z. Je parie un journal vous aidera. Désolé, il est tard, et je ne pense pas directement, mais ... vous ne devriez pas avoir besoin d'ajouter plusieurs 2n.

Edit:. Z est combien de temps vous devez multiplier par n 7/8 jusqu'à ce que vous obtenez 1

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

(8/7) ^ Z = 1 / n

(8/7) ^ Z = n

Vous voulez résoudre Z.

Qu'est-ce que vous y êtes arrivé dans la dernière ligne est un série géométrique et il y a un < a href = "http://en.wikipedia.org/wiki/Geometric_series#Formula" rel = "nofollow noreferrer"> formule de simplifier une telle somme.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top