日々の破片

_ 「アルゴリズムを学ぼう」で質問！

日曜に達人出版会からアルゴリズムを学ぼうを購入して読み進めていたんだけど、ふと、どこで見かけたか忘れたが、「数式を飛ばさずちゃんと読むべし」みたいなことが書いてあったのを思い出して、まじめに読んでみた。

アルゴリズムを学ぼう(川中真耶)

すると、困ったことにさっぱりわからない自分に気付いた。77ページの先頭。

マージソートの計算量としてT(N)=2T(N/2)+cNが出ていて、一応、ここまではわかるつもり。T(N/2)は分割した配列をマージソートするのに必要な計算量で、分割しているから2T(N/2)で2つ分の2×がつく。T(0)はreturnするだけだから、0というのも良い。

で、おとぼけ役の女の子が

えーと、N= 2^k なので、まず T(2^k) = 2T(2^(k-1)) + c2^k と書き直して、2^kで両辺を割る。

で、ここまでも問題ない。2T(N/2)は、2T(N * 2^-1)なので、N=2^kで書き直すと2T(2^(k-1))。

すると、T(2^k)/2^k = T(2^(k-1))/2^(k-1) + cなので、S(k) = T(2^k)/2^k と置けば、S(k) = S(k-1) + cと書き直すことができる。

ここまでも問題ない。

でも、次で引っ掛かった。

T(0)=0だったから、S(0)=0だから、S(k) = ckになる。

なぜ？ T(0)=0はそういう前提だから問題ないけど、なんでS(0)=0になるの？ 初項だから？ S(k) = T(2^k)/2^k で k=0の時ならばS(0) = T(2^0)/2^0で、これはS(0) = T(1) で、T(1)は0じゃないじゃん（と、読んだ時点で、根本的に読み方が間違っているのだろうと判断するわけだが、ではどう読むのが正しいのだろうか？）

で、そこは目をつむって（多分、数式の読み方としては正しくない態度だとは思うが）S(0)=0を受け入れたとしても、なぜS(k) = ck となるんだろう？ （実はここはわからなくはない。Sも漸化式だから、S(k) = S(k - 1) + cということは、SiとSi+1の差はc、したがって、S(k) = ck だと思うのだが、本当にそういう読み方で合っているのかなぁ）

というわけで、漸化式と単なる関数をごたまぜにして読んでいるようでもあり、つまるところはこのあたりをまじめに勉強しなかったうえに忘れきっているのでさっぱりわからない。S(0) = 0のところは、k=0と代入するのではなく、T(0) / 2^k の分子が0なので、Sの初項も0と読むのかな？ とか、考えれば考えるほどむしろわからなくなる状態です。

よろしければ、教えてください、よろしくお願いします。