0

分割統治法についてです。
下記画像の再帰的に代入すると4^2 T(n/2)=....4^log2^n T(1)=n^log2^4 T(1)と数式が変化する過程、理由がわかりません。

数学に弱く数学的な知見が不足しているかもしれません。
噛み砕き解説いただけると幸いです。

参照:データ構造とアルゴリズム

画像の説明をここに入力

2

1 件の回答 1

0

「再帰的に代入」という部分が肝です。

この計算過程では 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 のようにあらわせないときはこんな綺麗にはなりませんが、今求めたいのは計算量の漸近的な挙動(オーダー)であり、上か下かどちらかから抑えられれば問題ありません。本当はそこも厳密に議論すべきです。

2
  • 非常にわかりやすい解説ありがとうございます。 ただ2^(log_2(n^2)) = n^2になる理由がわかりませんでした。 これは対数のどのような性質から変形しているのでしょうか。
    – sample
    Commented 2019年3月9日 18:03
  • @sample さん、それは対数の(素朴な)定義です。たとえば高校数学の教科書では、ある数 q であって、2^q = p となるようなものを log_2(p) と定めているはずです。
    – nekketsuuu
    Commented 2019年3月11日 0:57

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。