分割統治法についてです。
下記画像の再帰的に代入すると4^2 T(n/2)=....4^log2^n T(1)=n^log2^4 T(1)と数式が変化する過程、理由がわかりません。
数学に弱く数学的な知見が不足しているかもしれません。
噛み砕き解説いただけると幸いです。
参照:データ構造とアルゴリズム
分割統治法についてです。
下記画像の再帰的に代入すると4^2 T(n/2)=....4^log2^n T(1)=n^log2^4 T(1)と数式が変化する過程、理由がわかりません。
数学に弱く数学的な知見が不足しているかもしれません。
噛み砕き解説いただけると幸いです。
参照:データ構造とアルゴリズム
「再帰的に代入」という部分が肝です。
この計算過程では T(n) = 4 T(n/2)
という等式を T(n)
に対して代入するという操作を繰り返し(再帰的に)行っています。ここでこの等式は任意の n
について成り立つので、たとえば T(n/2) = 4 T(n/4)
という風にも使えます。
T(n) = 4 T(n/2)
= 4 × 4 T(n/4) = 4^2 T(n/4)
= 4^2 × 4 T(n/8) = 4^3 T(n/8)
= ...
また、ある正の整数 k
を使って n = 2^k
と表せるとき、つまり k = log_2(n)
のとき、この代入操作はぴったり T(1)
になるまで続けることができます。では T(1)
になるまで何回代入が必要でしょうか? 上の具体例をもとに考えると、ぴったり log_2(n)
回だということが分かります。つまり、以下のようになります。
T(n) = 4 T(n/2)
= 4^2 T(n/4)
= 4^3 T(n/8)
= ...
= 4^(log_2(n)) T(1)
最後に、4 = 2^2
なので 4^(log_2(n))
はもっと簡単な式にできます。たとえば教科書の例と違う変形の仕方をすると、下のようにできます
4^(log_2(n)) = (2^2)^(log_2(n))
= 2^(2 log_2(n))
= 2^(log_2(n^2))
= n^2
よって、T(n) = n^2 T(1)
になります。
※n
がちょうど 2^k
のようにあらわせないときはこんな綺麗にはなりませんが、今求めたいのは計算量の漸近的な挙動(オーダー)であり、上か下かどちらかから抑えられれば問題ありません。本当はそこも厳密に議論すべきです。