理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題1.15

sin(x)の近似計算について,その計算回数を求める問題.

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))
(sine 12.15)

については、
12.15/3^x \lt 0.1を満たす最小のx回だけpが作用するので,その回数は5回。


この計算においては、空間計算量、時間計算量ともにオーダーは等しい。そしてそのオーダーは上の回答からもわかるようにO(log a)である。