漸化式の練習問題セット｜マスター定理の使い方を例題で解説

漸化式（リカレンス関係）とは

漸化式とは、数列の各項をそれ以前の項を用いて再帰的に定義する方程式のことです。アルゴリズムの計算量を解析する際には、T(n) で表される漸化式を解く場面が数多くあります。

この記事では、マスター定理（Master Theorem）を用いた漸化式の演習問題を、具体例とともにわかりやすく解説します。

例題1：マスター定理のケース1を適用

次の漸化式を解いてみましょう。

T(n) = 12T(n/2) + 9n2 + 2

この式では、a = 12、b = 2、f(n) = 9n² + 2 です。f(n) は O(n^c)（c = 2）の形で表せるため、マスター定理の適用条件を満たします。

log_b(a) = log₂12 ≈ 3.58
c = 2 ＜ 3.58 なのでケース1より、
T(n) = Θ(n3.58)

例題2：定数の無視とオーダー近似

次の漸化式を解いてみましょう。

T(n) = 5T(n/2 + 23) + 5n2 + 7n − 5/3

n が十分大きい場合、n/2 ≫ 23 となるため、定数項「+23」は無視できます。

T(n) = 5T(n/2) + 5n2 + 7n − 5/3
さらに、5n2 + 7n − 5/3 ≈ O(n2) と近似できるので、
T(n) = 5T(n/2) + O(n2)

ここで a = 5、b = 2 より log₂5 ≈ 2.32 となり、c = 2 はこれより小さいため、ケース1が適用され、T(n) = Θ(n^2.32) と求められます。

マスター定理が適用できるかの判定練習

続いて、与えられた漸化式がマスター定理のいずれかのケースに当てはまるかを判定してみましょう。

問題1

T(n) = 2T(n/3) + 5n

いいえ。マスター定理を適用するには、f(n) が多項式関数 O(n^c) の形である必要があります。5ⁿ は指数関数なので適用できません。

問題2

T(n) = 2T(n/5) + tan(n)

いいえ。tan(n) のような三角関数はマスター定理の対象外です。

問題3

T(n) = 5T(n+1) + log(n)

いいえ。T(n+1) は n/b による分割の形ではなく、対数関数も多項式ではないため適用できません。

問題4

T(n) = T(n−7) + en

いいえ。T(n−7) は減算の形であり、eⁿ も指数関数なので適用できません。

問題5

T(n) = 9T(n/2 + 1) + 4n2 − 17

はい。例題2と同様の方法で解くことができます。

まとめ

マスター定理を正しく活用するためのポイントは次の3つです。

• 漸化式が T(n) = aT(n/b) + f(n) の標準形になっているか確認する
• f(n) が多項式関数 O(n^c) で表せるか確認する
• log_b(a) と c の大小を比較し、対応するケースを適用する