Théorème Maître pour Récurrences Diviser-pour-Régner

Bonjour,

Dans la leçon précédente, nous avons appris à résoudre des relations de récurrence de la forme $T (n) = T (n - 1) + f (n)$ grâce à la méthode de substitution. Cette méthode, bien que fondamentale et rigoureuse, peut s'avérer laborieuse.

Aujourd'hui, nous abordons une nouvelle classe de récurrences, celles qui émanent des algorithmes "diviser pour régner". Ces algorithmes, comme le tri fusion ou la recherche dichotomique, découpent un problème en sous-problèmes plus petits, les résolvent récursivement, puis combinent les résultats. Leur complexité suit typiquement un schéma de la forme $T (n) = a T (n / b) + f (n)$ .

L'objectif de cette leçon est de maîtriser un outil exceptionnellement efficace pour résoudre ce type de récurrence : le théorème maître (ou Master Theorem). Il agit comme une "recette" qui, sous certaines conditions, donne directement la complexité asymptotique d'un algorithme sans nécessiter une preuve par récurrence complète à chaque fois. Pour un candidat à l'Agrégation, la maîtrise de cet outil est non négociable.

1. La structure des récurrences "Diviser pour Régner"

Une récurrence de type "diviser pour régner" est donc de la forme :
$T (n) = a T (n / b) + f (n)$
Il est essentiel de comprendre la signification de chaque paramètre :

$a \geq 1$ est le nombre d'appels récursifs (le nombre de sous-problèmes).
$b > 1$ est le facteur de réduction de la taille de l'entrée. On passe d'un problème de taille $n$ à des sous-problèmes de taille $n / b$ .
$f (n)$ est le coût du travail effectué hors des appels récursifs : le coût pour "diviser" le problème et/ou pour "régner" en combinant les solutions des sous-problèmes.

Visualisons cela avec l'arbre des appels récursifs :

Recursion Tree View for Divide-and-Conquer Algorithms — Arbre de récurrence illustrant la décomposition d'un problème. À chaque niveau, le problème est divisé en `a` sous-problèmes, et le coût de la division/combinaison est `f(n)` (ou `f(n/b^i)` au niveau `i`). La complexité totale `T(n)` est la somme des coûts de tous les nœuds de l'arbre.

Le théorème maître analyse la "compétition" entre le coût généré par la prolifération des appels récursifs (qui dépend de $a$ et $b$ ) et le coût du travail à chaque étape ( $f (n)$ ).

2. Énoncé du Théorème Maître

Pour commencer, nous allons utiliser une version simplifiée mais très courante du théorème.

Analyse de programmes récursifs - Anthony Lick

Le document suivant, un extrait de cours de niveau CPGE, présente de manière claire et concise le paradigme "diviser pour régner" et l'énoncé du théorème maître. Il vous servira de référence principale pour cette leçon.

Lisez les sections intitulées "Récurrences 'diviser pour régner'" et "Théorème maître" (jusqu'à la preuve). Focalisez-vous sur la formulation du théorème. Notez bien la définition de α et β et les trois cas qui en découlent.

Synthétisons l'énoncé. Soit une récurrence de la forme $T (n) = a T (n / b) + f (n)$ avec $a \geq 1, b > 1$ . On suppose que $f (n) = Θ (n^{k})$ pour une constante $k \geq 0$ . (Le document utilise $β$ au lieu de $k$ ).

On compare alors deux valeurs :

L'exposant du coût non-récursif : $k$ .
Une valeur qui caractérise la croissance des appels récursifs : $lo g_{b} a$ .

Le théorème maître énonce les trois cas suivants :

Si $lo g_{b} a > k$ : La complexité est dominée par les appels récursifs (le nombre de feuilles dans l'arbre de récursion).
$T (n) = Θ (n^{l o g_{b} a})$
Si $lo g_{b} a = k$ : Le travail est équilibré à chaque niveau de l'arbre de récursion.
$T (n) = Θ (n^{k} lo g n) = Θ (n^{l o g_{b} a} lo g n)$
Si $lo g_{b} a < k$ : La complexité est dominée par le coût de division/combinaison (le travail à la racine de l'arbre).
$T (n) = Θ (n^{k})$

L'intuition est fondamentale : le théorème compare la vitesse à laquelle les sous-problèmes prolifèrent ( $n^{l o g_{b} a}$ ) à la vitesse à laquelle le travail par étape augmente ( $n^{k}$ ). Le terme le plus "lourd" dicte la complexité finale.

3. Application du Théorème Maître : Exemples

La meilleure façon de maîtriser ce théorème est de l'appliquer. La vidéo suivante illustre parfaitement cette démarche sur plusieurs exemples concrets.

Comprendre le "Master Theorem"

Cette vidéo en français décompose l'application du théorème maître de manière très méthodique. Elle vous aidera à solidifier votre compréhension des trois cas.

Regardez la vidéo du début jusqu'à 7:22. Pour chaque exemple, identifiez mentalement les valeurs de a, b, f(n), calculez log_b a, et déterminez dans quel cas du théorème on se trouve avant que la solution ne soit donnée. La vidéo utilise une formulation légèrement différente mais l'esprit est identique : on compare f(n) à n^(log_b a).

Reprenons quelques exemples canoniques en appliquant notre formulaire.

Exemple 1 : Tri fusion (Merge Sort)

Récurrence : $T (n) = 2 T (n /2) + Θ (n)$
Paramètres : $a = 2$ , $b = 2$ , $f (n) = Θ (n^{1}) ⟹ k = 1$ .
Calcul : $lo g_{b} a = lo g_{2} 2 = 1$ .
Comparaison : $lo g_{b} a = 1$ et $k = 1$ . Nous sommes dans le cas 2.
Conclusion : $T (n) = Θ (n^{1} lo g n) = Θ (n lo g n)$ .

Exemple 2 : Recherche dichotomique (Binary Search)

Récurrence : $T (n) = T (n /2) + Θ (1)$
Paramètres : $a = 1$ , $b = 2$ , $f (n) = Θ (n^{0}) ⟹ k = 0$ .
Calcul : $lo g_{b} a = lo g_{2} 1 = 0$ .
Comparaison : $lo g_{b} a = 0$ et $k = 0$ . Nous sommes dans le cas 2.
Conclusion : $T (n) = Θ (n^{0} lo g n) = Θ (lo g n)$ .

Exemple 3 : Algorithme de Strassen (Multiplication de matrices)

Récurrence : $T (n) = 7 T (n /2) + Θ (n^{2})$
Paramètres : $a = 7$ , $b = 2$ , $f (n) = Θ (n^{2}) ⟹ k = 2$ .
Calcul : $lo g_{b} a = lo g_{2} 7 \approx 2.807$ .
Comparaison : $lo g_{b} a \approx 2.807 > k = 2$ . Nous sommes dans le cas 1.
Conclusion : $T (n) = Θ (n^{l o g_{2} 7})$ .

Exemple 4 : Un cas dominé par $f (n)$

Récurrence : $T (n) = 2 T (n /4) + Θ (n)$
Paramètres : $a = 2$ , $b = 4$ , $f (n) = Θ (n^{1}) ⟹ k = 1$ .
Calcul : $lo g_{b} a = lo g_{4} 2 = 1/2$ .
Comparaison : $lo g_{b} a = 0.5 < k = 1$ . Nous sommes dans le cas 3.
Conclusion : $T (n) = Θ (n^{1}) = Θ (n)$ .

4. Fondements et Limites

En tant que futur agrégé, vous ne pouvez vous contenter d'appliquer une formule. Il faut en comprendre les fondements et les limites.

Fondements de la preuve

La preuve du théorème maître, que vous avez aperçue dans le document de A. Lick, repose sur une analyse de l'arbre de récurrence. On calcule la somme des coûts à tous les niveaux. Cette somme se ramène souvent à une série géométrique, dont le comportement dépend de sa raison, qui est liée à $a / b^{k}$ .

Si la raison est $< 1$ ( $⟺ a < b^{k}$ ), la somme converge, et le premier terme ( $f (n)$ ) domine. C'est notre cas 3.
Si la raison est $> 1$ ( $⟺ a > b^{k}$ ), la somme diverge, et le dernier terme (le coût des feuilles) domine. C'est notre cas 1.
Si la raison est $= 1$ ( $⟺ a = b^{k}$ ), tous les termes sont égaux. La somme est le nombre de termes $\times$ la valeur d'un terme. C'est notre cas 2.

Pour une démonstration complète et formelle, du niveau attendu à l'oral de l'Agrégation, vous pouvez consulter le document de référence suivant.

Master Theorem - ENS Rennes

Ce document, issu d'une préparation à l'Agrégation de l'ENS Rennes, présente une preuve formelle du théorème. Il n'est pas nécessaire de la mémoriser entièrement à ce stade, mais il est crucial de vous familiariser avec ce niveau d'exigence mathématique.

Lisez le Théorème 1 et parcourez les deux étapes de la démonstration. Observez comment la preuve est d'abord menée pour les n qui sont des puissances de b, puis généralisée par un argument de monotonie.

Limites du Théorème

Le théorème maître est puissant, mais ne s'applique pas toujours.

La fonction $f (n)$ doit être polynomiale (dans la version que nous avons vue). Si $f (n) = Θ (n^{k} lo g^{p} n)$ , des versions étendues existent, mais la version de base ne suffit plus.
La taille des sous-problèmes doit être uniforme. Il ne s'applique pas à des récurrences comme $T (n) = T (n /3) + T (2 n /3) + n$ .
La division doit être constante. Il ne s'applique pas au cas moyen du tri rapide (Quicksort), dont la récurrence est $T (n) = T (k) + T (n - k - 1) + Θ (n)$ , car $k$ n'est pas une fraction fixe de $n$ .

5. Exercices d'application

Appliquez le théorème maître pour trouver la complexité asymptotique $Θ$ des récurrences suivantes :

$T (n) = 9 T (n /3) + n$
$T (n) = 8 T (n /2) + n^{3}$
$T (n) = T (n /2) + n$
$T (n) = 4 T (n /2) + n$
$T (n) = 7 T (n /3) + n^{2}$

Solutions

$a = 9, b = 3, k = 1$ . $lo g_{3} 9 = 2$ . Cas 1 ( $2 > 1$ ). $T (n) = Θ (n^{2})$ .
$a = 8, b = 2, k = 3$ . $lo g_{2} 8 = 3$ . Cas 2 ( $3 = 3$ ). $T (n) = Θ (n^{3} lo g n)$ .
$a = 1, b = 2, k = 1$ . $lo g_{2} 1 = 0$ . Cas 3 ( $0 < 1$ ). $T (n) = Θ (n)$ .
$a = 4, b = 2, k = 1$ . $lo g_{2} 4 = 2$ . Cas 1 ( $2 > 1$ ). $T (n) = Θ (n^{2})$ .
$a = 7, b = 3, k = 2$ . $lo g_{3} 7 \approx 1.77$ . Cas 3 ( $1.77 < 2$ ). $T (n) = Θ (n^{2})$ .

Conclusion

Aujourd'hui, nous avons ajouté un outil puissant à votre arsenal pour l'analyse d'algorithmes. Le théorème maître offre un raccourci inestimable pour analyser toute la famille des algorithmes basés sur le paradigme "diviser pour régner".

Points clés à retenir :

Les récurrences "diviser pour régner" ont la forme $T (n) = a T (n / b) + f (n)$ .
Le théorème maître compare $lo g_{b} a$ à l'exposant $k$ de $n$ dans $f (n)$ pour déterminer laquelle des trois forces en jeu domine : la prolifération des appels récursifs, le coût de la division/combinaison, ou un équilibre entre les deux.
Connaître les trois cas du théorème et savoir identifier les paramètres $a, b, k$ d'une récurrence est une compétence essentielle.
Un candidat à l'Agrégation doit aussi comprendre l'intuition derrière le théorème (l'arbre de récurrence) et ses limites d'application.

Dans la prochaine leçon, nous mettrons en pratique ces outils d'analyse pour comparer formellement l'efficacité de différents algorithmes. Grâce au théorème maître, nous pouvons maintenant justifier rigoureusement pourquoi un algorithme en $Θ (n lo g n)$ est fondamentalement plus efficace qu'un autre en $Θ (n^{2})$ pour des entrées de grande taille.

Recommended resources