Master theorem
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 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; dans sa traduction française, 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. 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. 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.