创建和求解正弦近似的递推关系

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) 不仅仅是 "intuitively true"。互联网上似乎没有任何教程涵盖此分析，我唯一看到的结论是非线性递归几乎无法解决。

有人能帮忙吗？

谢谢！

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θ)。（我省略了将最后一个递归与其他递归区分开来的小常数因子，因为它没有区别。）

创建和求解正弦近似的递推关系

Creating and solving a recurrence relation for sine approximation

algorithm

complexity-theory

recurrence

scheme

time-complexity