質問: 2進アルゴリズムの時間計算量 ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは k<=(2*log(n))-1 となっていました。
回答: 指数が n である場合の乗算の回数を t(n) とします. 計算方法から, すぐに t(2n) = t(n) + 1, t(2n+1) = t(n) + 2 であることがわかります. この式は「n が 2倍になると 乗算の回数がたかだか 2回増える」という意味です. なので, t(n) = 2 log n + c (c は定数) という形だろうと想像がつきます. そこでこの c を決めるために n = 2, 3 で考えると t(2) = 2 log 2 + c = 2 + c = 1, t(3) = 2 log 3 + c = 3.1... + c = 2 となります. ということで, c = -1 とおくと n = 2, 3 に対して t(n) ≦ 2 log n - 1 がいえます. あとは帰納法でがんばる.