05/07/29 04:53:54
>>639 レスありがとうございます。やっと SICP の1.2.4節に辿り着きました
URLﾘﾝｸ(mitpress.mit.edu)
後半の改善策が >>589 と同じ例題で、
;nが偶数なら b^n = (b^(n/2))^2
;nが奇数なら b^n = b*b^(n-1)
解答も >>607 と似てました。これを使った乗算回数は、たとえば
3^20 = (3^10)^2 = ((3^5)^2)^2 = ((3*3^4)^2)^2 = ((3*((3^2)^2))^2)^2
で理屈上は>>636と同じ５回(でも実は末尾で余計に1掛けたりとかで、少し多そう)。
オーダーとしてはどちらも log2(n) で、>>634の話が実は正しいような気がしました
Orders of Growth を理解するための頭の体操とはいえ、疲れた…
まだ木構造リストの演算をきちんと勉強してないので、勘違いしてたらすみません