Le théorème principal est un outil utilisé pour résoudre les relations de récurrence qui surviennent dans l'analyse des algorithmes diviser pour régner. Le théorème principal fournit une manière systématique de résoudre des relations de récurrence de la forme :

T(n) = aT(n/b) + f(n)

1. où a, b et f(n) sont des fonctions positives et n est la taille du problème. Le théorème principal fournit des conditions pour que la solution de la récurrence soit sous la forme de O(n^k) pour une constante k, et donne une formule pour déterminer la valeur de k.
2. La version avancée du théorème principal fournit une forme plus générale du théorème qui peut gérer des relations de récurrence plus complexes que la forme de base. La version avancée du Master Theorem peut gérer les récurrences avec plusieurs termes et des fonctions plus complexes.
3. Il est important de noter que le théorème principal n’est pas applicable à toutes les relations de récurrence et qu’il ne fournit pas toujours une solution exacte à une récurrence donnée. Cependant, il s’agit d’un outil utile pour analyser la complexité temporelle des algorithmes diviser pour régner et constitue un bon point de départ pour résoudre des récurrences plus complexes.

Le théorème principal est utilisé pour déterminer le temps d'exécution des algorithmes (algorithmes diviser pour régner) en termes de notations asymptotiques.
Considérons un problème résolu par récursion.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

L'algorithme ci-dessus divise le problème en un sous-problèmes, chacun de taille n/b et résolvez-les de manière récursive pour calculer le problème et le travail supplémentaire effectué pour le problème est donné par f(n), c'est-à-dire le temps nécessaire pour créer les sous-problèmes et combiner leurs résultats dans la procédure ci-dessus.

Ainsi, selon le théorème principal, le temps d’exécution de l’algorithme ci-dessus peut être exprimé comme suit :

 T(n) = aT(n/b) + f(n)>

où n = taille du problème
a = nombre de sous-problèmes dans la récursion et a>= 1
n/b = taille de chaque sous-problème
f(n) = coût du travail effectué en dehors des appels récursifs comme la division en sous-problèmes et le coût de leur combinaison pour obtenir la solution.

Toutes les relations de récurrence ne peuvent pas être résolues avec l'utilisation du théorème principal, c'est-à-dire si

• T(n) n'est pas monotone, ex : T(n) = sin n
• f(n) n'est pas un polynôme, ex : T(n) = 2T(n/2) + 2ⁿ

Ce théorème est une version avancée du théorème principal qui peut être utilisé pour déterminer le temps d'exécution des algorithmes diviser pour régner si la récurrence est de la forme suivante : -

où n = taille du problème
a = nombre de sous-problèmes dans la récursion et a>= 1
n/b = taille de chaque sous-problème
b> 1, k>= 0 et p est un nombre réel.

Alors,

1. si a> b^k, alors T(n) = θ(n^{enregistrer_bun})
2. si a = b^k, alors
   (a) si p> -1, alors T(n) = θ(n^{enregistrer_bun}enregistrer^p+1n)
   (b) si p = -1, alors T(n) = θ(n^{enregistrer_bun}journal de connexion)
   (c) si p <-1, alors T(n) = θ(n^{enregistrer_bun})
   
3. si un k, alors
   (a) si p>= 0, alors T(n) = θ(n^kenregistrer^pn)
   (b) si p <0, alors T(n) = θ(n^k)
   

Analyse de la complexité temporelle –

Exemple 1 : Recherche binaire – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 et p = 0
b^k= 1. Donc, a = b^ket p> -1 [Cas 2.(a)]
T(n) = θ(n^{enregistrer_bun}enregistrer^p+1n)
T(n) = θ(logn) Exemple 2 : Tri par fusion – T(n) = 2T(n/2) + O(n)
une = 2, b = 2, k = 1, p = 0
b^k= 2. Donc, a = b^ket p> -1 [Cas 2.(a)]
T(n) = θ(n^{enregistrer_bun}enregistrer^p+1n)
T(n) = θ(nlogn) Exemple-3 : T(n) = 3T(n/2) + n²
une = 3, b = 2, k = 2, p = 0
b^k= 4. Donc, un k et p = 0 [Cas 3.(a)]
T(n) = θ(n^kenregistrer^pn)
T(n) = θ(n²)

Exemple-4 : T(n) = 3T(n/2) + log²n
une = 3, b = 2, k = 0, p = 2
b^k= 1. Donc, a> b^k[Cas 1]
T(n) = θ(n^{enregistrer_bun})
T(n) = θ(n^{enregistrer₂3})

Exemple-5 : T(n) = 2T(n/2) + nlog²n
une = 2, b = 2, k = 1, p = 2
b^k= 2. Donc, a = b^k[Cas 2.(a)]
T(n) = θ(n^{enregistrer_bun}enregistrer^p+1n)
T(n) = θ(n^{enregistrer₂2}enregistrer³n)
T(n) = θ(nlog³n)

Exemple-6 : T(n) = 2ⁿT(n/2) + nⁿ
Cette récurrence ne peut pas être résolue en utilisant la méthode ci-dessus puisque la fonction n'est pas de la forme T(n) = aT(n/b) + θ(n^kenregistrer^pn)

Questions pratiques GATE –

• PORTE-CS-2017 (Ensemble 2) | Question 56
• PORTE-LE 2008 | Question 42
• PORTE CS 2009 | Question 35

Voici quelques points importants à garder à l’esprit concernant le théorème principal :

1. Récurrences diviser pour régner : le théorème principal est spécifiquement conçu pour résoudre les relations de récurrence qui surviennent lors de l'analyse des algorithmes diviser pour régner.
2. Forme de la récurrence : Le théorème principal s'applique aux relations de récurrence de la forme T(n) = aT(n/b) + f(n), où a, b et f(n) sont des fonctions positives et n est la taille du problème.
3. Complexité temporelle : le théorème principal fournit des conditions pour que la solution de la récurrence soit sous la forme de O(n^k) pour une constante k, et il donne une formule pour déterminer la valeur de k.
4. Version avancée : La version avancée du théorème principal fournit une forme plus générale du théorème qui peut gérer des relations de récurrence plus complexes que la forme de base.
5. Limites : Le théorème principal n'est pas applicable à toutes les relations de récurrence et il ne fournit pas toujours une solution exacte à une récurrence donnée.
6. Outil utile : malgré ses limites, le théorème principal est un outil utile pour analyser la complexité temporelle des algorithmes diviser pour régner et constitue un bon point de départ pour résoudre des récurrences plus complexes.
7. Complété par d'autres techniques : Dans certains cas, le théorème principal peut devoir être complété par d'autres techniques, telles que la méthode de substitution ou la méthode d'itération, pour résoudre complètement une relation de récurrence donnée.