Master theorem (analysis of algorithms) とは

アルゴリズムの解析では、分割・征服再現のマスター定理は、多くの除算アルゴリズムと征服アルゴリズムの解析で発生するタイプの漸化関係に漸近解析(Big O表記を使用)を提供します。このアプローチは、1980年にJon Bentley、Dorothea Haken、James B. Saxeによって最初に発表されました。そこでは、このような再発を解決するための「統一方法」として記述されていました。 「マスター定理」という名前は、Cormen、Leiserson、Rivest、およびSteinのアルゴリズムの紹介で広く使用されているアルゴリズムの教科書によって一般化されました。
この定理の使用によってすべての再帰関係を解くことはできません。その一般化にはAkra-Bazzi法が含まれる。