『Merge Sort の計算時間』解答

◆神奈川県　＠ＪＪＪＪＪＪ　さんからの解答。

【問題１】

特に n=2^m のとき、

T(n=2^m)
=T(2^m-1)+T(2^m-1)+2^m-1
=2T(2^m-1)+2^m-1.

T(1)=1,T(2)=T(1)+T(1)+2-1=3,だから、

T(2^m)=m(2^m)+1.

となる。

また、

T(3)=T(1)+T(2)+3-1=6,
T(4)=T(2)+T(2)+4-1=9,
T(5)=T(2)+T(3)+5-1=13,
T(6)=T(3)+T(3)+6-1=17,
T(7)=T(3)+T(4)+7-1=21,
T(8)=T(4)+T(4)+8-1=25.

これより
T(n=2^m+k) (1≦k≦2^m)を推定すると、

T(n=2^m+k)=m(2^m+k)+2k+1. (*)

T([2m-1+k/2])+T(【2m-1+k/2】)+2m+k-1
=(m-1)(2m-1+[k/2])+2[k/2]+1+(m-1)(2m-1+【k/2】)+2【k/2】+1+2m+k-1
=m(2m+k)+2k+1
=T(2m+k).

m〜log(n)　だから、T(n)〜nlog(n).

　『Merge Sort の計算時間』へ

　数学の部屋へもどる