Master theorem

Considérons un problème qui peut être résolu par un algorithme récursif de la famille 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 ${\displaystyle f(n)}$.

La complexité en temps des algorithmes de cette nature est exprimée par une relation de récurrence de type :

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$.

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[5]. Mais une expression comme celle fournie par le « master theorem », permet d'exprimer la complexité asymptotique sans passer par un développement explicite.

Les relations de récurrence concernées ont la forme suivante :

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$, avec ${\displaystyle a\geq 1,b>1}$.

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

• ${\displaystyle n}$ est la taille du problème ;
• ${\displaystyle a}$ est le nombre de sous-problèmes dans lesquels il est divisé ; c'est un entier supérieur ou égal à 1 ;
• ${\displaystyle n/b}$ est la taille de chaque sous-problème. Si ${\displaystyle n/b}$ n'est pas un entier, on le remplace par sa 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 ;
• ${\displaystyle f(n)}$ 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 ${\displaystyle f(n)}$. Pour cela, on exprime sa croissance par l'ordre de grandeur ${\displaystyle n^{c}}$, où ${\displaystyle c}$ mesure le rapport entre ${\displaystyle a}$ et ${\displaystyle b^{c}}$. Ce rapport est exprimé en prenant le logarithme en base ${\displaystyle b}$, donc en comparant ${\displaystyle c}$ à ${\displaystyle \log _{b}a}$. Les trois cas couverts par le théorème sont :

1. - ${\displaystyle f(n)=O\left(n^{c}\right)}$ où ${\displaystyle c<\log _{b}a}$
2. - ${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$ où ${\displaystyle k}$ est une constante et ${\displaystyle c=\log _{b}a}$
3. - ${\displaystyle f(n)=\Omega \left(n^{c}\right)}$ où ${\displaystyle c>\log _{b}a}$ et de plus ${\displaystyle af(n/b)\leq kf(n)}$ pour une constante ${\displaystyle k<1}$ et ${\displaystyle n}$ assez grand.

On suppose donnée la relation de récurrence de la forme :

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$, avec ${\displaystyle a\geq 1,b>1}$.

où ${\displaystyle f}$ est une fonction à valeurs entières positives. Le « master theorem » s'énonce comme suit :

1.- Si ${\displaystyle f(n)=O\left(n^{c}\right)}$ avec ${\displaystyle c<\log _{b}a}$, alors

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}$.

2.- Si ${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$ avec ${\displaystyle c=\log _{b}a}$ et une constante ${\displaystyle k\geq 0}$, alors

${\displaystyle T(n)=\Theta \left(n^{c}\log ^{k+1}n\right)}$.

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

${\displaystyle T(n)=\Theta \left(f(n)\right)}$

Supposons la relation de récurrence suivante :

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+O(n^{d})}$

Le « master theorem » permet d'obtenir une expression de la complexité de ${\displaystyle T(n)}$ comme suit :

1.- Si ${\displaystyle d<\log _{b}a}$ alors ${\displaystyle T(n)=O(n^{\log _{b}a})}$.

2.- Si ${\displaystyle d=\log _{b}a}$ alors ${\displaystyle T(n)=O(n^{d}\log _{b}n)}$.

3.- Si ${\displaystyle d>\log _{b}a}$ alors ${\displaystyle T(n)=O(n^{d})}$.

Les équations suivantes sont des exemples de relations qui n'entrent pas de le cadre des trois cas du « master theorem »[6] :

• ${\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n.\quad }$ Ici, le paramètre a n'est pas une constante ; le nombre de sous-problèmes devrait ne pas varier.
• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}.\quad }$ Ici, la différence entre ${\displaystyle f(n)}$ et ${\displaystyle n^{\log _{b}a}}$ n'est pas polynomialement bornée (voir plus bas).
• ${\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n.\quad }$ Ici, le paramètre a est plus petit que 1; cela n'a pas de sens d'avoir moins d'un sous-problème.
• ${\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n.\quad }$ Ici, f(n) qui est le coût de la décomposition-recombinaison est négatif.
• ${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n).\quad }$ 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 ${\displaystyle f(n)=n/\log n}$ et ${\displaystyle n^{\log _{b}a}=n}$ peut être étudiée à l'aide du quotient

${\displaystyle {\dfrac {f(n)}{n^{\log _{b}a}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}$.

On voit que ${\displaystyle 1/\log n<n^{\epsilon }}$ pour toute constante ${\displaystyle \epsilon >0}$. La différence n'est donc pas polynomialement bornée, et le « master theorem » ne s'applique pas.

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

${\displaystyle T(n)=\sum _{i=1}^{m}T\left(\alpha _{i}n\right)+f(n)}$,

où les nombres ${\displaystyle \alpha _{i}}$ vérifient ${\displaystyle 0<\alpha _{i}<1}$, et ${\displaystyle m\geq 1}$. Ici, on ne suppose donc pas que les sous-problèmes ont la même taille. On étend la fonction T aux nombres réels en posant ${\displaystyle T(x)=T(\lfloor x\rfloor )}$ ou ${\displaystyle T(\lceil x\rceil )}$ si ${\displaystyle x}$ n'est pas entier.

On a alors l’énoncé suivant. Si ${\displaystyle f(n)\in \Theta (n^{c})}$ pour un entier ${\displaystyle c>0}$, alors

${\displaystyle 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}}}$

L’énoncé du « master theorem » couvre également des situations comme par exemple la récurrence

${\displaystyle T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n}$

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[7].

• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press and McGraw-Hill, 2001, 2^e éd., 1180 p. (ISBN 0-262-03293-7), « Sections 4.3 (The master method) et 4.4 (Proof of the master theorem) », p. 73-90.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition]
• Michael T. Goodrich et Roberto Tamassia, Algorithm Design : Foundation, Analysis, and Internet Examples, Wiley, 2002, 708 p. (ISBN 0-471-38365-1), p. 268-270. — Le « master theorem » énoncé dans ce livre est plus général que celui de Cormen et. al.
• Michael Drmota et Wojciech Szpankowski, « A Master Theorem for Discrete Divide and Conquer Recurrences », Journal of the ACM, vol. 60, n^o 3,‎ 2013, p. 1-49 (DOI 10.1145/2487241.2487242, lire en ligne)