SICP по-русски

При вычислении sine процедура p вызывается с аргументом sine от угла деленного на три. Это повторяется до тех пор, пока угол не станет меньше 0.1 по модулю. То есть, если x - начальный угол, то количество вызовов процедуры p (обозначим его n) будет удовлетворять следующему двойному неравенству:

x / 3ⁿ ≤ 0.1 ≤ x / 3^n-1.

При x = 12.15 нетрудно видеть, что

• при n=4 получаем 12.15/3⁴ = 12.15/81 > 0.1,
• при n=5 получаем 12.15/3⁵ = 12.15/243 < 0.1.

Таким образом при вычислении (sine 12.15) процедура p вызывается 5 раз.

Перейдем к оценкам порядка роста количества шагов и используемой памяти для процедуры sine как функции от угла α. На каждой итерации происходит рекурсивный вызов функции sine с аргументом, деленным на три. То есть через n итераций аргумент уменьшится в 3ⁿ раз, а стало быть, так как процесс останавливается тогда, когда аргумент становится меньше 0.1 по модулю, из выведенного ранее неравенства

α / 3ⁿ ≤ 0.1

получаем

n ≥ log₃(10α).

Таким образом число шагов растет логарифмически с ростом угла (Θ(log α)).

Также логарифмически (Θ(log α)) растет и объем памяти, что легко объясняетася тем, что память растет пропорционально числу шагов.