計算機プログラムの構造と解釈 第二版 P29 問題1.26
そもそも、
(* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
なんてことをやると、ここで計算が二系統に分かれる。しかも同じ計算を倍々にし続けることになる。
これはめちゃくちゃスペースをくう。整数の平方を求めるのに比べて大きく遅くなる。
せっかく偶数の時の線形の計算量と比較した場合の
計算量の減り方は、こんな感じになりそう。
(この一回をスナップショット的に切り取ると、、、)
n^(1/2) + 1
↑乗算を二分の一にしたで ↑平方を求めるの計算量
これを以下のように台無しに。。。。
(n^(1/2)) * (n^(1/2))
= (n^(1/2))^2
=n
つまり、expに偶数がくるたびに、n^(1/2)の計算量の計算が二本ずつ走り出すってコトだ。
んで
このまま計算を続けていくと、
本来、ずっと1/2乗がかかってくるから
結果として、2を底としたθ(log n)になるんだろうが、
この問題では、台無しになっているので計算量は結局、
θ(n)
という感じかと思う。