algorithm - 创建和求解正弦近似的递归关系

Question

在 SICP 中，有一个问题(练习 1.15)说

Exercise 1.15.  The sine of an angle (specified in radians) can be 
computed by making use of the approximation sin x x if x is 
sufficiently small, and the trigonometric identity

sin(r) = 3sin(r/3) - 4sin^3(r/3)

to reduce the size of the argument of sin. (For purposes of this 
exercise an angle is considered ``sufficiently small'' if its 
magnitude is not greater than 0.1 radians.) These ideas are incorporated 
in the following procedures:

(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)))))

a.  How many times is the procedure p applied when (sine 12.15) is evaluated?

b.  What is the order of growth in space and number of steps 
    (as a function of a) used by the process generated by the 
    sine procedure when (sine a) is evaluated?

您可以通过运行它来分析它，看到它变成了 O(loga)，其中 a 是以弧度为单位的输入角度。

但是，这还不够。这应该可以通过递归关系证明。我可以这样设置递归关系:

T(a) = 3T(a/3) - 4T(a/3)^3

哪个是同质的:

3T(a/3) - 4T(a/3)^3 - T(a) = 0

但是，它是非线性的。我不确定如何得到这个特征方程，以便我可以解决它并向自己证明 O(loga) 不仅仅是“直觉上正确”。互联网上似乎没有任何教程涵盖此分析，我唯一看到的结论是非线性递归几乎无法解决。

谁能帮忙？

谢谢!

Answer 1

您将计算与计算所花费的时间混淆了。

如果θ≤0.1，则T(θ)为1。否则为T(θ/3)+k，其中k是做四次乘法的时间，一个减法，以及一些杂项簿记。

很明显，第 i^th 次递归的参数将为 θ/3ⁱ，因此递归将一直持续到 θ/3ⁱ ≤0.1。由于不等式为真的 i 的最小值是 ⌈log₃(θ/0.1)⌉，我们可以看到 T(θ) = k*⌈log₃(θ/0.1)⌉，即 O(logθ)。 (我省略了将最后一个递归与其他递归区分开来的小常数因子，因为它没有区别。)