Master theorem

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 permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme 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; dans sa traduction française, 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 Bentley, Dorothea Haken, et James B. Saxe. 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 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 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 $f(n)$.

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

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

Forme générale

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

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

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

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

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

Énoncé général

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

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

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

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

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

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

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

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

$T(n)=\Theta \left(f(n)\right)$

Énoncé avec la notation de Landau

Supposons la relation de récurrence suivante :

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

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

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

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

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

Exemples

Cas 1

C'est le cas où $f(n)=O\left(n^{c}\right)$ avec $c<\log _{b}a$. Le théorème affirme qu'alors $T(n)=\Theta \left(n^{\log _{b}a}\right)$.

Exemple

La relation

$T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$

entre dans ce cas avec $a=8,\,b=2,\,c=2$, et l'hypothèse sur $c$ est bien vérifiée puisque $\log _{b}a=\log _{2}8=3>c$. Par l'énoncé, on a

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

On peut vérifier directement que, si $T(1)=1$, alors

$T(n)=1001n^{3}-1000n^{2}$.

Cas 2

Dans ce cas, $f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ pour une constante $k\geq 0$ et $c=\log _{b}a$. Le théorème affirme qu'alors $T(n)=\Theta \left(n^{c}\log ^{k+1}n\right)$.

Exemple

La relation

$T(n)=2T\left({\frac {n}{2}}\right)+10n$

entre dans ce cas avec $a=2,\,b=2,\,c=1,\,k=0,\,f(n)=10n=\Theta \left(n^{c}\log ^{k}n\right)$. Comme $\log _{b}a=\log _{2}2=1$, on a bien $c=\log _{b}a$ et par l'énoncé, on a

$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)$ .

À nouveau, la solution exacte de la récurrence (avec $T(1)=1$) qui est

$T(n)=n+10n\log _{2}n$

confirme les conclusions.

Cas 3

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

Exemple La relation

$T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$

entre dans ce cas avec $a=2,\,b=2,\,c=2,\,f(n)=n^{2}=\Omega \left(n^{c}\right)$. On a bien $2=c>\log _{b}a=\log _{2}2=1$ et, en choisissant $k=1/2$, la condition de régularité s'écrit

$2{\frac {n^{2}}{4}}\leq kn^{2}$

et est bien vérifiée. L'énoncé assure donc que

$T(n)=\Theta (f(n))=\Theta (n^{2}).$.

Ici encore, le résultat est confirmé par la solution exacte de la relation de récurrence qui est $T(n)=2n^{2}-n$, en supposant $T(1)=1$.

Équations non couvertes

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

• $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.
• $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}.\quad$ Ici, la différence entre $f(n)$ et $n^{\log _{b}a}$ n'est pas polynomialement bornée (voir plus bas).
• $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.
• $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.
• $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 $f(n)=n/\log n$ et $n^{\log _{b}a}=n$ peut être étudiée à l'aide du quotient

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

On voit que $1/\log n<n^{\epsilon }$ pour toute constante $\epsilon >0$. 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

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

où les nombres $\alpha _{i}$ vérifient $0<\alpha _{i}<1$, et $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 $T(x)=T(\lfloor x\rfloor )$ ou $T(\lceil x\rceil )$ si $x$ n'est pas entier.

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

$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}}$

Application à des algorithmes courants

Algorithme	Relation de récurrence	Complexité en temps	Commentaire
Recherche dichotomique	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Appliquer le « master theorem » avec $c=\log _{b}a$, et $a=1,b=2,c=0,k=0$
Parcours d'arbre binaire	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Appliquer le « master theorem » avec $c<\log _{b}a$ et $a=2,b=2,c=0$
Trouver la valeur médiane	$T(n)=T\left({\frac {n}{2}}\right)+O(n)$	$O(n)$
Tri fusion	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Appliquer le « master theorem » avec $c=\log _{b}a$, où $a=2,b=2,c=1,k=0$.

Commentaire

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

$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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Master theorem » (voir la liste des auteurs).

Bibliographie

• (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)