SICP 全笔记

Exercise 1.14. Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

树形结构

count-change 程序产生出的树型结构如下:

process tree of count-change procedure

算法复杂度分析

count-change 和 Fibonacci 数的递归是类似的,在空间上是 $\theta(n)$ 在时间上是指数增长的。