Master Theorem
マスター定理は分割統治型漸化式 T(n)=aT(n/b)+f(n) の漸近的な限界を与える。f と n^(log_b a) を比較して 3 つの場合に分ける。
目的
漸化式を展開せずに分割統治アルゴリズムの計算量を素早く解析する。
メカニズム
c=log_b a とおく。場合 1：f=O(n^(c-ε)) なら T=Θ(n^c)。場合 2：f=Θ(n^c log^k n) なら T=Θ(n^c log^(k+1) n)。場合 3：f=Ω(n^(c+ε)) かつ正則条件を満たせば T=Θ(f) である。
ユースケース
- アルゴリズムの計算量解析
- 分割統治アルゴリズム
- 漸化式（recurrence）の求解