Salut ,
J'ai quelque ambigüité sur la formule de la résolution de la récurrence "Deviser pour régner", on a:
T(n)= aT(n/b)+ f(n);
A quoi ça sert exactement les deux variables a et b?
Veillez m'expliquer plus sur des exemples pour mieux comprendre:
- Multiplication de deux matrices (a=8, b=2).
- Tri d'une table par fusion (a=2, b=2).
- Recherche dichotomique dans une table ordonnée (a=1, b=2).
Au début, j'ai imaginer a est le nombre des sous-problèmes (deviser), et b est toujours b=2 parce que on devise toujours sur 2, mais j'ai trouvé qlq contradictions comme la recherche dichotomie (a=1), alors, j'ai déduit que j'ai mal compris que je vous demande de me clarifier les choses SVP.
Merci d'avance.
Salutations .
Partager