計算機プログラムの構造と解釈 第二版 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)
という感じかと思う。