Dans ce didacticiel, vous apprendrez ce qu'est le théorème maître et comment il est utilisé pour résoudre les relations de récurrence.
La méthode principale est une formule pour résoudre les relations de récurrence de la forme:
T (n) = aT (n / b) + f (n), où, n = taille de l'entrée a = nombre de sous-problèmes dans la récursivité n / b = taille de chaque sous-problème. Tous les sous-problèmes sont supposés avoir la même taille. f (n) = coût du travail effectué en dehors de l'appel récursif, qui comprend le coût de la division du problème et le coût de la fusion des solutions Ici, a ≧ 1 et b> 1 sont des constantes, et f (n) est une asymptotiquement positive fonction.
Une fonction asymptotiquement positive signifie que pour une valeur suffisamment grande de n, nous avons f(n)> 0.
Le théorème maître est utilisé pour calculer la complexité temporelle des relations de récurrence (algorithmes de division et de conquête) d'une manière simple et rapide.
Théorème maître
Si a ≧ 1et b> 1sont des constantes et f(n)est une fonction asymptotiquement positive, alors la complexité temporelle d'une relation récursive est donnée par
T (n) = aT (n / b) + f (n) où, T (n) a les limites asymptotiques suivantes: 1. Si f (n) = O (n log b a-ϵ ), alors T (n ) = Θ (n log b a ). 2. Si f (n) = Θ (n log b a ), alors T (n) = Θ (n log b a * log n). 3. Si f (n) = Ω (n log b a + ϵ ), alors T (n) = Θ (f (n)). ϵ> 0 est une constante.
Chacune des conditions ci-dessus peut être interprétée comme:
- Si le coût de résolution des sous-problèmes à chaque niveau augmente d'un certain facteur, la valeur de
f(n)deviendra polynomialement inférieure à . Ainsi, la complexité temporelle est opprimée par le coût du dernier niveau ie.nlogb anlogb a - Si le coût de résolution du sous-problème à chaque niveau est presque égal, alors la valeur de
f(n)sera . Ainsi, la complexité temporelle sera multipliée par le nombre total de niveaux ie.nlogb af(n)nlogb a * log n - Si le coût de résolution des sous-problèmes à chaque niveau diminue d'un certain facteur, la valeur de
f(n)deviendra polynomialement plus grande que . Ainsi, la complexité temporelle est opprimée par le coût de .nlogb af(n)
Exemple résolu du théorème maître
T (n) = 3T (n / 2) + n2 Ici, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ie. f (n) <n log b a + ϵ , où, ϵ est une constante. Le cas 3 implique ici. Ainsi, T (n) = f (n) = Θ (n 2 )
Limitations du théorème maître
Le théorème maître ne peut pas être utilisé si:
- T (n) n'est pas monotone. par exemple.
T(n) = sin n f(n)n'est pas un polynôme. par exemple.f(n) = 2n- a n'est pas une constante. par exemple.
a = 2n a < 1
