Discussion :

[mamioop]

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 .

[Franck Dernoncourt]

http://en.wikipedia.org/wiki/Master_theorem ?

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

[mamioop]

Rien à dire, c'est compris, merci d'avoir m'aidé Franck . Malgré c'est mon habitude, je n'ai pas pensé de rechercher en Anglais cette fois, de plus, je ne savais pas que c'est nommé "Master theorem" .

[Franck Dernoncourt]

Tu es le bienvenu ! Bizarrement il y a peu de ressources en français effectivement sur le Master theorem.

Si tu veux en lire davantage sur le sujet, regarde du côté du livre de référence "Introduction to Algorithms" de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein. C'est le livre qui a popularisé la méthode du Master theorem. [ame="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844"]Amazon.com: Introduction to Algorithms (9780262033848): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Books@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41kXXE4mAKL.@@AMEPARAM@@41kXXE4mAKL[/ame]