53284


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

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

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

[![画像の説明をここに入力](https://i.stack.imgur.com/zlTNE.jpg)](https://i.stack.imgur.com/zlTNE.jpg)


CC BY-SA 4.0
2019-03-07T18:17:30.630
53283
2019-03-07T19:57:31.567
32396
question
アルゴリズム 数学
分割統治法を利用した数式についてです。


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

この計算過程では `T(n) = 4 T(n/2)` という等式を `T(n)`
に対して代入するという操作を繰り返し（再帰的に）行っています。ここでこの等式は任意の `n` について成り立つので、たとえば `T(n/2) = 4
T(n/4)` という風にも使えます。

[code]

    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)
         = ...
    
[/code]

また、ある正の整数 `k` を使って `n = 2^k` と表せるとき、つまり `k = log_2(n)` のとき、この代入操作はぴったり `T(1)`
になるまで続けることができます。では `T(1)` になるまで何回代入が必要でしょうか？ 上の具体例をもとに考えると、ぴったり `log_2(n)`
回だということが分かります。つまり、以下のようになります。

[code]

    T(n) = 4 T(n/2)
         = 4^2 T(n/4)
         = 4^3 T(n/8)
         = ...
         = 4^(log_2(n)) T(1)
    
[/code]

最後に、`4 = 2^2` なので `4^(log_2(n))` はもっと簡単な式にできます。たとえば教科書の例と違う変形の仕方をすると、下のようにできます

[code]

    4^(log_2(n)) = (2^2)^(log_2(n))
                 = 2^(2 log_2(n))
                 = 2^(log_2(n^2))
                 = n^2
    
[/code]

よって、`T(n) = n^2 T(1)` になります。

※`n` がちょうど `2^k`
のようにあらわせないときはこんな綺麗にはなりませんが、今求めたいのは計算量の漸近的な挙動（オーダー）であり、上か下かどちらかから抑えられれば問題ありません。本当はそこも厳密に議論すべきです。


CC BY-SA 4.0
2019-03-07T19:57:31.567
53284
2019-03-07T19:57:31.567
19110
53283
answer