[complexité] Résoudre les récurences

[kegilko]

Bonjour tout l'monde !

Je m'attaque aux révisions pour un examen de Complexité ce mardi et attaquant les révisions, je tombe sur une espèce de problème que je sais qu'il y a 4 mois même en m'y forçant je ne comprenais pas, et dû coup, je ne comprend guère plus maintenant !
L'énoncé est très simple :

Résoudre la récurrence suivante :
T(n) = 4T(n/2)+n avec T(1)=1

- Alors d'une voila ou j'en arrive sans trop de difficulté :
T(1)=1
T(2)=4T(1)+2=6
T(4)=28
T(8)=120

on commence toujours par se débarrasser du T(n/X) , ici X =2.
Pour ce faire, "changement de variable !", T(n) = T(2^n)
Et donc T(2^n) = 4T(2^(n-1))+2^n

À partir de là, je bloque, et le pire et qui me rend vraiment fou, c'est que j'ai la correction.... et je comprend chibre de rien xD
D'après la correction, la suite " " " logique " " " serait :

On pose tn = 4^n . yn
//tn , c'est t indice n, et yn, c'est y indice n
Mais....WTF ? d'où on le sort ça et pourquoi ? xD

La solution finale de l'exercice est la suivante : T(N) = 2N²-N


J'ai d'autres exercices, avec aussi la correction, mais toujours cet endroit précis où on sort ce changement de valeur qui s'échappe complètement de ma logique.
Donc est qu'une âme charitable pourrait me venir en aide ? existe-t-il un cours , une méthodologie pour apprendre à faire ces récurrences ? celui que j'ai entre les mains ne donne pas assez d'explication...


En vous remerciant !
Bonne journée

[b_reda31]

Bonjour,
En supposant qu'il existe un entier m tel que n = 2^m :

Code :

1
2
3
4
5
6
T(n) = 4T(2^m-1)+2^m
= 4^2 * T(2^m-2)  + (4 * 2^m-1) + 2^m
=4^3 * T(2^m-3) + (4^2 * 2^m-2) + (4 * 2^m-1) + 2^m
=...
=4^m * T(2^0)  + (4^m-1 * 2^1) + (4^m-2 * 2^2)+...+2^m

En remplaçant 4^x par 2^x * 2^x on obtient facilement :

Code :

1
2
3
T(n) = n²+ n²/2 + n²/4 + n²/8 + ... + n²/n
= n² (1+ 1/2 + 1/4 + ...1/n)

Ce qui représente la somme des termes d'une suite géométrique :