Master theorem

théorème d'analyse de complexité d'algorithmes

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[1] 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[2]; dans sa traduction française[3], 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[4]. 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

modifier

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  .

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

 .

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.

Forme générale

modifier

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

 , avec  .

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

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

  1. -   
  2. -    est une constante et  
  3. -    et de plus   pour une constante   et   assez grand.

Énoncé général

modifier

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

 , avec  .

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

1.- Si   avec  , alors

 .

2.- Si   avec   et une constante  , alors

 .

3.- Si   avec   et s'il existe une constante   telle que, pour   assez grand, on a :   (cette condition est appelée parfois la « condition de régularité »), alors on a :

 

Supposons la relation de récurrence suivante :

 

Le « master theorem » permet d'obtenir une expression de la complexité de   comme suit :

1.- Si   alors  .

2.- Si   alors  .

3.- Si   alors  .

Exemples

modifier

C'est le cas où   avec  . Le théorème affirme qu'alors  .

Exemple

La relation

 

entre dans ce cas avec  , et l'hypothèse sur   est bien vérifiée puisque  . Par l'énoncé, on a

 .

On peut vérifier directement que, si  , alors

 .

Dans ce cas,   pour une constante   et  . Le théorème affirme qu'alors  .

Exemple

La relation

 

entre dans ce cas avec  . Comme  , on a bien   et par l'énoncé, on a

  .

À nouveau, la solution exacte de la récurrence (avec  ) qui est

 

confirme les conclusions.

C'est le cas où   avec   et où il existe une constante   telle que, pour   assez grand, on a  . Le théorème affirme qu'alors on a :  .

Exemple La relation

 

entre dans ce cas avec  . On a bien   et, en choisissant  , la condition de régularité s'écrit

 

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

 .

Ici encore, le résultat est confirmé par la solution exacte de la relation de récurrence qui est  , en supposant  .

Équations non couvertes

modifier

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

  •   Ici, le paramètre a n'est pas une constante ; le nombre de sous-problèmes devrait ne pas varier.
  •   Ici, la différence entre   et   n'est pas polynomialement bornée (voir plus bas).
  •   Ici, f(n) qui est le coût de la décomposition-recombinaison est négatif.
  •   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   et   peut être étudiée à l'aide du quotient

 .

On voit que   pour toute constante  . La différence n'est donc pas polynomialement bornée, et le « master theorem » ne s'applique pas.

Extension

modifier

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

 ,

où les nombres   vérifient  , et  . 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   ou   si   n'est pas entier.

On a alors l’énoncé suivant. Si   pour un entier  , alors

 

Application à des algorithmes courants

modifier
Algorithme Relation de récurrence Complexité en temps Commentaire
Recherche dichotomique     Appliquer le « master theorem » avec  , et  [7]
Parcours d'arbre binaire     Appliquer le « master theorem » avec   et  [7]
Trouver la valeur médiane    
Tri fusion     Appliquer le « master theorem » avec  , où  .

Commentaire

modifier

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

 

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

Notes et références

modifier
  1. Terminologie utilisée dans le cours d'algorithmique de Paul Gastin.
  2. Cormen et. al..
  3. Cormen et. al., Introduction à l'algorithmique.
  4. Jon Louis Bentley, Dorothea Haken et James B. Saxe, « A general method for solving divide-and-conquer recurrences », ACM SIGACT News, vol. 12, no 3,‎ , p. 36-44 (ISSN 0163-5700, DOI 10.1145/1008861.1008865).
  5. Big-Oh for « Recursive Functions: Recurrence Relations » sur le site de la Duke University
  6. « Master Theorem: Practice Problems and Solutions »(Archive.orgWikiwixArchive.isGoogleQue faire ?), Massachusetts Institute of Technology (MIT).
  7. a b et c Section 5.2 The Master Theorem, Dartmouth College.
(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

modifier