Back النظرية الرئيسة (تحليل الخوارزميات) Arabic Master theorem Czech Master-Theorem German Μάστερ Θεώρημα Greek Master theorem (analysis of algorithms) English Teorema maestro Spanish قضیه اصلی (تحلیل الگوریتمها) Persian שיטת האב HE Mester-tétel Hungarian Teorema dell'esperto Italian
Ne doit pas être confondu avec Master theorem de Ramanujan.
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[1] 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[2]; dans sa traduction française[3], 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[4]. 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.
- ↑ Terminologie utilisée dans le cours d'algorithmique de Paul Gastin.
- ↑ Cormen et. al..
- ↑ Cormen et. al., Introduction à l'algorithmique.
- ↑ Jon Louis Bentley, Dorothea Haken et James B. Saxe, « A general method for solving divide-and-conquer recurrences », ACM SIGACT News, vol. 12, no 3, , p. 36-44 (ISSN 0163-5700, DOI 10.1145/1008861.1008865).