Quand puis-je utiliser le théorème maître ?

Le théorème maître s'applique aux récurrences de la forme T(n) = aT(n/b) + f(n) avec a >= 1 et b > 1, où chaque niveau divise le problème en a sous-problèmes de taille n/b. Les récurrences avec des divisions inégales, des tailles de sous-problèmes variables ou des coûts de combinaison non polynomiaux peuvent nécessiter l'utilisation des méthodes de l'arbre de récursion, de substitution ou d'Akra-Bazzi à la place.

Pourquoi la récurrence du tri fusion (mergesort) donne-t-elle O(n log n) ?

Le tri fusion (mergesort) donne T(n) = 2T(n/2) + O(n) : deux sous-problèmes de demi-taille plus une fusion linéaire. Ici, le travail par niveau est le même sur tous les log n niveaux de l'arbre de récursion, donc le total est n fois log n, ce que le théorème maître confirme comme Thêta(n log n).

Relations de récurrence

Les relations de récurrence expriment le temps d'exécution d'un algorithme récursif en fonction de son temps d'exécution sur des entrées plus petites ; leur résolution permet d'obtenir les bornes asymptotiques sous forme fermée utilisées pour analyser les algorithmes de type diviser pour régner et d'autres algorithmes récursifs.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Une relation de récurrence est une équation qui définit la valeur d'une fonction pour une entrée donnée en fonction de ses valeurs pour des entrées plus petites ; dans l'analyse des algorithmes, elle exprime le coût d'un algorithme sur une entrée de taille n en fonction de son coût sur des sous-problèmes plus petits.

Scope

Ce sujet couvre la formulation et la résolution des récurrences rencontrées dans l'analyse des algorithmes : la méthode de substitution, la méthode de l'arbre de récursion et le théorème maître pour les récurrences de type diviser pour régner de la forme T(n) = aT(n/b) + f(n). Il explique comment chaque algorithme récursif induit une récurrence et comment traduire cette récurrence en une borne en grand-Thêta. Il exclut la notation asymptotique elle-même, qui est traitée séparément, ainsi que les méthodes de fonctions génératrices combinatoires issues des mathématiques discrètes.

Core questions

Comment un algorithme récursif donne-t-il lieu à une récurrence pour son temps d'exécution ?
Comment la méthode de substitution est-elle utilisée pour prouver et vérifier une solution supposée ?
Comment la méthode de l'arbre de récursion révèle-t-elle le travail total effectué à travers les niveaux de récursion ?
Quand le théorème maître s'applique-t-il, et que signifient ses trois cas ?
Comment les récurrences qui ne correspondent pas à la forme du théorème maître sont-elles traitées ?

Key concepts

relation de récurrence
méthode de substitution
méthode de l'arbre de récursion
théorème maître
récurrence diviser pour régner
cas de base et cas récursif
solution sous forme fermée
méthode d'Akra-Bazzi

Key theories

Théorème maître: Pour les récurrences de type diviser pour régner T(n) = aT(n/b) + f(n), le théorème maître donne la solution asymptotique en comparant f(n) à n élevé à la puissance log en base b de a, couvrant les trois cas où les feuilles, la racine ou les niveaux équilibrés dominent.
Méthodes de l'arbre de récursion et de substitution: La méthode de l'arbre de récursion somme le travail effectué à chaque niveau de récursion pour suggérer une borne, que la méthode de substitution prouve ensuite rigoureusement par induction ; ensemble, elles traitent les récurrences qui dépassent le champ d'application du théorème maître.

Clinical relevance

La résolution des récurrences est la voie standard pour déterminer le temps d'exécution des algorithmes récursifs, du tri fusion (mergesort) et du tri rapide (quicksort) à la multiplication rapide et à de nombreux programmes dynamiques. Les ingénieurs et les chercheurs utilisent couramment le théorème maître pour dériver et justifier les affirmations de complexité asymptotique associées à de tels algorithmes.

History

L'analyse des récurrences des algorithmes a été systématisée dans The Art of Computer Programming de Knuth. Le théorème maître est devenu un pilier des manuels grâce au CLRS, et la méthode d'Akra-Bazzi (1998) l'a généralisé à une classe plus large de récurrences de type diviser pour régner avec des divisions inégales.

Key figures

Donald Knuth
Mohamad Akra
Louay Bazzi

Seminal works

cormen2009
knuth1997vol1

Frequently asked questions

Quand puis-je utiliser le théorème maître ?: Le théorème maître s'applique aux récurrences de la forme T(n) = aT(n/b) + f(n) avec a >= 1 et b > 1, où chaque niveau divise le problème en a sous-problèmes de taille n/b. Les récurrences avec des divisions inégales, des tailles de sous-problèmes variables ou des coûts de combinaison non polynomiaux peuvent nécessiter l'utilisation des méthodes de l'arbre de récursion, de substitution ou d'Akra-Bazzi à la place.
Pourquoi la récurrence du tri fusion (mergesort) donne-t-elle O(n log n) ?: Le tri fusion (mergesort) donne T(n) = 2T(n/2) + O(n) : deux sous-problèmes de demi-taille plus une fusion linéaire. Ici, le travail par niveau est le même sur tous les log n niveaux de l'arbre de récursion, donc le total est n fois log n, ce que le théorème maître confirme comme Thêta(n log n).