Voir la source de Master theorem

{{titre en italique|en}}
{{confusion|Master theorem de Ramanujan}}
En [[informatique]], et plus particulièrement en [[analyse de la complexité des algorithmes]], le '''''master theorem''''' ou théorème sur les '''récurrences de partition'''<ref>Terminologie utilisée dans le [http://www.lsv.ens-cachan.fr/~gastin/Algo/Algo-14-4up.pdf cours d'algorithmique] de Paul Gastin.</ref> permet d'obtenir une solution en termes [[Asymptote|asymptotiques]] (en utilisant les [[Comparaison asymptotique|notations en O]]) pour des [[Suite définie par récurrence|relations de récurrence]] d'un certain type rencontrées dans l'[[Analyse de la complexité des algorithmes|analyse de complexité]] d'algorithmes qui sont régis par le paradigme [[Diviser pour régner (informatique)|diviser pour régner]].

L'énoncé sur les expressions asymptotiques de ces récurrences a été nommé « master theorem » dans la version anglaise du manuel ''Introduction to Algorithms'' de Cormen, Leiserson, Rivest et Stein<ref>{{harvsp|id=CLRS|texte= Cormen ''et. al.''}}.</ref>; dans sa traduction française<ref>{{harvsp|id=Cormen2fr|texte= Cormen ''et. al.'', ''Introduction à l'algorithmique''}}.</ref>, le théorème est appelé le « théorème général ». L'approche a été présentée notamment en 1980 par [[Jon Louis Bentley|Jon Bentley]], [[Dorothea Haken]], et [[James B. Saxe]]<ref name="BentleyHaken1980">
{{article|nom1=Bentley|prénom1=Jon Louis|nom2=Haken|prénom2=Dorothea|nom3=Saxe|prénom3=James B.|titre=A general method for solving divide-and-conquer recurrences|journal=ACM SIGACT News|volume=12|numéro=3|année=1980|pages=36-44|issn=0163-5700|doi=10.1145/1008861.1008865}}.</ref>. Le théorème couvre un certain nombre de types de récurrences ; une extension à d'autres expressions est fournie par ce que l’on appelle la [[Théorème d'Akra-Bazzi|méthode d'Akra-Bazzi]].

== Introduction ==
Considérons un problème qui peut être résolu par un [[algorithme récursif]] de la famille [[Diviser pour régner (informatique)|diviser pour régner]] qui opère comme suit : on partage une instance de taille ''n'' en sous-problèmes. Il y a ''a'' sous-problèmes et chacun est de taille ''n/b''. On résout ces sous-problèmes puis on recombine les solutions partielles en une solution du problème initial. On peut imaginer cette approche comme la construction d'un arbre, où chaque nœud est un appel récursif, et les enfants sont les instances appelées. Dans le cas décrit ci-dessus, chaque nœud possède ''a'' enfants. Chaque nœud répartit les données entre ses enfants et récupère les résultats partiels pour les synthétiser et obtenir la solution globale. La répartition des données entre enfants et l'intégration des résultats ont bien entendu également un coût qui, pour un problème de taille ''n'', est noté par <math>f(n)</math>.

La [[complexité en temps]] des algorithmes de cette nature est exprimée par une relation de récurrence de type :
:<math>T(n) = a \; T\left(\frac{n}{b}\right) + f(n)</math>.
On peut développer cette relation, en substituant la définition dans la partie droite de l'équation pour obtenir une expression pour le coût total au cas par cas<ref>[http://www.cs.duke.edu/~ola/ap/recurrence.html Big-Oh for « Recursive Functions: Recurrence Relations »] sur le site de la Duke University</ref>. Mais une expression comme celle fournie par le « master theorem », permet d'exprimer la complexité [[Comparaison asymptotique|asymptotique]] sans passer par un développement explicite.

== Forme générale ==
Les relations de récurrence concernées ont la forme suivante :

:<math>T(n) = a \; T\left(\frac{n}{b}\right) + f(n)</math>, avec <math>a \geq 1, b > 1</math>.

Dans les applications à l'analyse d'algorithmes récursifs, les paramètres ont la signification suivante :

* <math>n</math> est la taille du problème ;
* <math>a</math> est le nombre de sous-problèmes dans lesquels il est divisé ; c'est un entier supérieur ou égal à 1 ;
* <math>n/b</math> est la taille de chaque sous-problème. Si <math>n/b</math> n'est pas un entier, on le remplace par sa [[Partie entière et partie fractionnaire|partie entière]] inférieure ou supérieure. On peut prouver que cela ne change pas l'expression asymptotique, et les sous-problèmes ont tous pratiquement la même taille ;
* <math>f(n)</math> est le coût de gestion en dehors des appels récursifs, ce qui inclut le partage en sous-problèmes et la recombinaison des solutions des sous-problèmes.

On peut déterminer des bornes asymptotiques exactes dans trois cas, selon l'importance du surcoût mesuré par la croissance de la fonction <math>f(n)</math>. Pour cela, on exprime sa croissance par l'ordre de grandeur <math>n^c</math>, où <math>c</math> mesure le rapport entre <math>a</math> et <math>b^c</math>. Ce rapport est exprimé en prenant le logarithme en base <math>b</math>, donc en comparant <math>c</math> à <math>\log_b a</math>. Les trois cas couverts par le théorème sont :
 
# - <math>f(n) = O\left( n^{c} \right)</math> où <math>c < \log_b a</math>
# - <math>f(n) = \Theta\left( n^{c} \log^{k} n \right)</math> où <math>k</math> est une constante et <math>c = \log_b a</math>
# - <math>f(n) = \Omega\left( n^{c} \right)</math> où <math>c > \log_b a</math> et de plus <math>a f(n/b) \le k f(n)</math> pour une constante <math>k < 1</math> et <math>n</math> assez grand.

== Énoncé général ==
On suppose donnée la relation de récurrence de la forme :
:<math>T(n) = a \; T\left(\frac{n}{b}\right) + f(n)</math>, avec <math>a \geq 1, b > 1</math>.
où <math>f</math> est une fonction à valeurs entières positives. Le « master theorem » s'énonce comme suit :

1.- Si <math>f(n) = O\left( n^{c} \right)</math> avec <math>c < \log_b a</math>, alors
:<math>T(n) = \Theta\left( n^{\log_b a} \right)</math>.

2.- Si <math>f(n) = \Theta\left( n^{c} \log^{k} n\right)</math>
avec <math>c = \log_b a</math> et une constante <math>k\ge0</math>, alors
:<math>T(n) = \Theta\left( n^{c} \log^{k+1} n \right)</math>.

3.- Si <math>f(n) = \Omega\left( n^{c} \right)</math> avec <math>c > \log_b a</math>
et s'il existe une constante <math>k < 1</math> telle que, pour <math>n</math> assez grand, on a : <math>a f\left( \frac{n}{b} \right) \le k f(n)</math>
(cette condition est appelée parfois la « condition de régularité »), alors on a :
:<math>T(n) = \Theta\left(f(n) \right)</math>

== Énoncé avec [[Comparaison asymptotique|la notation de Landau]] ==
Supposons la relation de récurrence suivante :

<math>T(n) = a \; T\left(\frac{n}{b}\right) + O(n^d)</math>

Le « master theorem » permet d'obtenir une expression de la complexité de <math>T(n)</math> comme suit :

1.- Si <math>d<\log_ba</math> alors <math>T(n) = O(n^{\log_ba})</math>.

2.- Si <math>d=\log_ba</math> alors <math>T(n) = O(n^d\log_b n)</math>.

3.- Si <math>d>\log_ba</math> alors <math>T(n) = O(n^d)</math>.

== Exemples ==
=== Cas 1 ===
C'est le cas où <math>f(n) = O\left( n^{c} \right)</math> avec <math>c < \log_b a</math>. Le théorème affirme qu'alors
<math>T(n) = \Theta\left( n^{\log_b a} \right)</math>.

'''Exemple'''

La relation
:<math>T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2</math>
entre dans ce cas avec <math>a = 8, \, b = 2, \, c = 2</math>,
et l'hypothèse sur <math>c</math> est bien vérifiée puisque <math>\log_b a = \log_2 8 = 3>c</math>.
Par l'énoncé, on a
:<math>T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)</math>.
On peut vérifier directement que, si <math>T(1) = 1</math>, alors
:<math>T(n) = 1001 n^3 - 1000 n^2</math>.

=== Cas 2 ===
Dans ce cas, <math>f(n) = \Theta\left( n^{c} \log^{k} n \right)</math>
pour une constante <math>k\ge0</math> et <math>c = \log_b a</math>. Le théorème affirme qu'alors <math>T(n) = \Theta\left( n^{c} \log^{k+1} n \right)</math>.

'''Exemple'''

La relation
:<math>T(n) = 2 T\left(\frac{n}{2}\right) + 10n</math>
entre dans ce cas avec <math>a = 2, \, b = 2, \, c = 1, \, k = 0, \, f(n) = 10n= \Theta\left(n^{c} \log^{k} n\right)</math>.
Comme <math>\log_b a = \log_2 2 = 1</math>, on a bien <math>c = \log_b a</math> et par l'énoncé, on a
:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math> .

À nouveau, la solution exacte de la récurrence (avec <math>T(1) = 1</math>) qui est
:<math>T(n) = n + 10 n\log_2 n</math>
confirme les conclusions.

=== Cas 3 ===
C'est le cas où <math>f(n) = \Omega\left( n^{c} \right)</math> avec <math>c > \log_b a</math>
et où il existe une constante <math>k < 1</math> telle que, pour <math>n</math> assez grand, on a <math>a f\left( \frac{n}{b} \right) \le k f(n)</math>. Le théorème affirme qu'alors on a :
<math>T(n) = \Theta\left(f(n) \right)</math>.

'''Exemple'''
La relation
:<math>T(n) = 2 T\left(\frac{n}{2}\right) + n^2</math>
entre dans ce cas avec <math>a = 2, \, b = 2, \, c=2, \, f(n) = n^2=\Omega\left(n^c\right) </math>.
On a bien <math>2=c > \log_b a=\log_2 2 = 1</math> et, en choisissant <math> k = 1/2 </math>, la condition de régularité s'écrit
:<math> 2\frac{n^2}{4} \le k n^2 </math>
et est bien vérifiée. L'énoncé assure donc que
:<math>T (n) = \Theta(f(n)) = \Theta (n^2).</math>.
Ici encore, le résultat est confirmé par la solution exacte de la relation de récurrence qui est <math>T(n) = 2 n^2 - n</math>, en supposant <math>T(1) = 1</math>.

== Équations non couvertes ==
Les équations suivantes sont des exemples de relations qui n'entrent pas de le cadre des trois cas du « master theorem »<ref>
    {{lien brisé|url=http://www.csail.mit.edu/~thies/6.046-web/master.pdf |titre=« Master Theorem: Practice Problems and Solutions » }},   
    Massachusetts Institute of Technology (MIT).
</ref> :

* <math>T(n) = 2^nT\left (\frac{n}{2}\right )+n.\quad</math> Ici, le paramètre ''a'' n'est pas une constante ; le nombre de sous-problèmes devrait ne pas varier.
* <math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}.\quad</math> Ici, la différence entre <math>f(n)</math> et <math>n^{\log_b a}</math> n'est pas polynomialement bornée (voir plus bas).
* <math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n.\quad</math> Ici, ''f(n)'' qui est le coût de la décomposition-recombinaison est négatif.
* <math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n).\quad</math> Ici, on est bien dans le cas 3 mais la condition de régularité n'est pas satisfaite.

Dans le deuxième exemple ci-dessus, la différence entre <math>f(n)=n/\log n</math> et <math>n^{\log_b a}=n</math> peut être étudiée à l'aide du quotient
:<math>\dfrac{f(n)}{n^{\log_b a}} = \frac{n}{n \log n} = \frac{1}{\log n}</math>.
On voit que <math>1/\log n < n^\epsilon</math> pour toute constante <math>\epsilon > 0</math>. La différence n'est donc pas polynomialement bornée, et le « master theorem » ne s'applique pas.

== Extension ==
Une forme de récurrence plus générale est

:<math>T(n) = \sum_{i=1}^{m} T\left(\alpha_i n\right) + f(n)</math>,

où les nombres <math>\alpha_i</math> vérifient <math>0 < \alpha_i < 1</math>, et <math>m \ge 1</math>. Ici, on ne suppose donc pas que les sous-problèmes ont la même taille. On étend la fonction T aux [[Nombre réel|nombres réels]] en posant <math>T(x)=T(\lfloor x \rfloor)</math> ou <math>T(\lceil x \rceil)</math> si <math>x</math> n'est pas entier.

On a alors l’énoncé suivant. Si <math>f(n) \in \Theta(n^c)</math> pour un entier <math>c>0</math>, alors

:<math>T(n) \in
\begin{cases} \Theta(n^c) & \mbox{si } \sum_{i=1}^{m}(\alpha_i^c) < 1 \\
\Theta(n^c \log n) & \mbox{si } \sum_{i=1}^{m}(\alpha_i^c) = 1 \\
\Theta(n^\gamma) \mbox{ avec } \gamma \mbox{ défini par }\sum_{i=1}^{m}(\alpha_i^\gamma) = 1 & \mbox{si } \sum_{i=1}^{m}(\alpha_i^c) > 1.
\end{cases}</math>

== Application à des algorithmes courants ==
{| class="wikitable"
|-
! Algorithme
! Relation de récurrence
! Complexité en temps
! Commentaire
|-
| [[Recherche dichotomique]]
| <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math>
| <math>O(\log n)</math>
| Appliquer le « master theorem » avec <math>c = \log_b a</math>, et <math>a = 1, b = 2, c = 0, k = 0</math><ref name="dartmouth">[http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Section 5.2 The Master Theorem], Dartmouth College.
</ref>
|-
| Parcours d'arbre binaire
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
| <math>O(n)</math>
| Appliquer le « master theorem » avec <math>c < \log_b a</math> et <math>a = 2, b = 2, c = 0</math><ref name="dartmouth" />
|-
|[[Médiane des médianes|Trouver la valeur médiane]]
|<math>T(n) = T\left(\frac{n}{2}\right) + O(n)</math>
|<math>O(n)</math>
|
|-
| [[Tri fusion]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math>
| <math>O(n \log n)</math>
| Appliquer le « master theorem » avec <math>c = \log_b a</math>, où <math>a = 2, b = 2, c = 1, k = 0</math>.
|}

== Commentaire ==

L’énoncé du « master theorem » couvre également des situations comme par exemple la récurrence
:<math>T(n)=T(\lfloor n/2 \rfloor)+ T(\lceil n/2 \rceil) +n</math>
telle qu'elle se présente dans le tri fusion. Nous avons vu que l’on obtient les mêmes bornes asymptotiques en enlevant simplement les parties entières dans les formules de récurrence. Ainsi, la formule pour le tri fusion est équivalente à celle de la table<ref name="dartmouth" />.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Master theorem|638128804|type=note}}

== Bibliographie ==
* {{Ouvrage|langue=en|auteur1=Thomas H. Cormen|auteur2=Charles E. Leiserson|auteur3=Ronald L. Rivest|auteur4=Clifford Stein|titre=Introduction to Algorithms|lieu=Cambridge (Mass.)|éditeur=MIT Press and McGraw-Hill|année=2001|numéro d'édition=2|pages totales=1180|passage=73-90|isbn=0-262-03293-7|titre chapitre=Sections 4.3 (The master method) et 4.4 (Proof of the master theorem)|id=CLRS}}.
* {{Cormen2fr}}
* {{Ouvrage|auteur1=Michael T. Goodrich|auteur2=Roberto Tamassia|titre=Algorithm Design : Foundation, Analysis, and Internet Examples|éditeur=[[John Wiley & Sons|Wiley]]|année=2002|pages totales=708|passage=268-270|isbn=0-471-38365-1|id=CLRS}}. {{commentaire biblio SRL| Le « master theorem » énoncé dans ce livre est plus général que celui de Cormen ''et. al.''}}
* {{article
|nom1=Drmota|prénom1=Michael
|nom2=Szpankowski|prénom2=Wojciech
|titre=A Master Theorem for Discrete Divide and Conquer Recurrences
|journal=Journal of the ACM|volume=60|numéro=3|année=2013|pages=1-49
|url=http://www.dmg.tuwien.ac.at/drmota/jacm-final.pdf|doi=10.1145/2487241.2487242}}

{{Portail|Informatique théorique}}

[[Catégorie:Algorithmique]]
[[Catégorie:Théorème d'informatique]]