Discussion :

[rvfranck]

Salut,

J'arrive pas à resoudre cette récurrence:
T(n) = 20 * T(n/5) + 4 * T(n/10) + n^2

Il s'agit en fait d'un algo qui reduit un problème de taille n en 20 sous problèmes de taille n/5 et 4 sous problèmes de taille n/10. le cout de diviser et combiner vaut theta(n^2) et je dois determiner l'ordre asymptôtique du temps d'execution de l'algo.

J'ai donc ramené le problème à cette récurrence mais je n'arrive pas à la resoudre parce que 10 n'est pas une puissance de 5.
Et si je découpais la récurrence en 2 (proposition d'un ami):
20 * T(n/5) + n^2 et T(n/10) pour trouver les ordres de chaque récurrence et après j'essayerai de les additionner , c'est raisonnable?

Sinon, je suis ouvert à toutes autres methodes de resolution.

Merci

[PRomu@ld]

En fait tout dépend du calcul de ta complexité, veux tu un calcul grand O, théta, ... ?

Si c'est une résolution grand O, tu peux dire que T(n/5) > T(n/10) pour un grand n et donc négliger T(n/10). Ensuite, il suffira de résoudre T(n) = a T(n/b) + f(n).

[pseudocode]

On peu aussi s'amuser a poser f(a,b) = n / ( 5^a * 10^b ) et calculer les premiers développements de T(n) = T( f(0,0) )

on ne sait jamais...

[rvfranck]

Merci,
donc l'idée de mon copain ne marche pas c'est ça?

[pseudocode]

Merci,
donc l'idée de mon copain ne marche pas c'est ça?

Si tu poses:
A(n) = 20 * A(n/5) + n^2
B(n) = 4 * B(n/10)

alors
S(n)=A(n)+B(n)
S(n)=20 * A(n/5) + n^2 + 4 * B(n/10)

Ce qui est different de
T(n)=20 * T(n/5) + n^2 + 4 * T(n/10)

Donc l'étude de A(n) et B(n) pourra te servir pour trouver la complexité de S(n), mais pas celle de T(n)... A moins de trouver une relation entre S(n) et T(n), ce qui ne semble pas evident.