私はアルゴリズムクラスのスライドを見ていて、以下に出くわしました.
T(n) = 2T(n^(1/2)) + lg n
名前の変更: m = lg n => n = 2^m T (2^m) = 2T(2^(m/2)) + m
名前の変更: S(m) = T(2^m) S(m) = 2S(m/2) + m
最後の方程式がどのようにして得られたのか、誰か説明できますか? S(m/2) がどのようにして得られたのか理解できません。ありがとうございました。
私はアルゴリズムクラスのスライドを見ていて、以下に出くわしました.
T(n) = 2T(n^(1/2)) + lg n
名前の変更: m = lg n => n = 2^m T (2^m) = 2T(2^(m/2)) + m
名前の変更: S(m) = T(2^m) S(m) = 2S(m/2) + m
最後の方程式がどのようにして得られたのか、誰か説明できますか? S(m/2) がどのようにして得られたのか理解できません。ありがとうございました。