SICP: Exercise 1.14

問題 1.14

1.2.2 節の count-change 手続きが 11 セントの両替の場合に生成するプロセスを示す木構造を描け。両替の金額の増加につれ、このプロセスが使うスペースとステップ数の増加の程度は何か。

「計算機プログラムの構造と解釈 第二版 1.2.3 増加の程度」より

木の図示

(count-change 11) の木を図示する。面倒くさい。

色をつけた部分でカウントされるので、答えは 4。段階数は 57。

一応 graphviz で使った DOT ソースを示しておきます。適当ですが。

digraph ex_1_14 {
    "count-change 11" -> "cc 11 5";
 
    "cc 11 5" -> "cc 11 4";
    "cc 11 5" -> "cc -39 5";
 
    "cc 11 4" -> "cc 11 3";
    "cc 11 4" -> "cc -14 4";
 
    "cc 11 3" -> "cc 11 2";
    "cc 11 3" -> "cc 1 3";
 
    cc_1_2_1[label="cc 1 2"];
    "cc 1 3" -> cc_1_2_1;
    "cc 1 3" -> "cc -9 3";
 
    cc_1_1_1[label="cc 1 1"];
    cc_m4_2_1[label="cc -4 2"];
    cc_1_2_1 -> cc_1_1_1;
    cc_1_2_1 -> cc_m4_2_1;
 
    cc_1_0_1[label="cc 1 0"];
    cc_0_1_1[label="cc 0 1" style=filled fillcolor="#F0BA32"];
    cc_1_1_1 -> cc_1_0_1;
    cc_1_1_1 -> cc_0_1_1;
 
    "cc 11 2" -> "cc 11 1";
    "cc 11 2" -> "cc 6 2";
 
    cc_6_1_1[label="cc 6 1"];
    cc_1_2_2[label="cc 1 2"];
    "cc 6 2" -> cc_6_1_1;
    "cc 6 2" -> cc_1_2_2;
 
    cc_6_0_1[label="cc 6 0"];
    cc_5_1_1[label="cc 5 1"];
    cc_6_1_1 -> cc_6_0_1;
    cc_6_1_1 -> cc_5_1_1;
 
    cc_5_0_1[label="cc 5 0"];
    cc_4_1_1[label="cc 4 1"];
    cc_5_1_1 -> cc_5_0_1;
    cc_5_1_1 -> cc_4_1_1;
 
    cc_4_0_1[label="cc 4 0"];
    cc_3_1_1[label="cc 3 1"];
    cc_4_1_1 -> cc_4_0_1;
    cc_4_1_1 -> cc_3_1_1;
 
    cc_3_0_1[label="cc 3 0"];
    cc_2_1_1[label="cc 2 1"];
    cc_3_1_1 -> cc_3_0_1;
    cc_3_1_1 -> cc_2_1_1;
 
    cc_2_0_1[label="cc 2 0"];
    cc_1_1_2[label="cc 1 1"];
    cc_2_1_1 -> cc_2_0_1;
    cc_2_1_1 -> cc_1_1_2;
 
    cc_1_0_2[label="cc 1 0"];
    cc_0_1_2[label="cc 0 1" style=filled fillcolor="#F0BA32"];
    cc_1_1_2 -> cc_1_0_2;
    cc_1_1_2 -> cc_0_1_2;
 
    cc_1_1_3[label="cc 1 1"];
    cc_m4_2_2[label="cc -4 2"];
    cc_1_2_2 -> cc_1_1_3;
    cc_1_2_2 -> cc_m4_2_2;
 
    cc_1_0_3[label="cc 1 0"];
    cc_0_1_3[label="cc 0 1" style=filled fillcolor="#F0BA32"];
    cc_1_1_3 -> cc_1_0_3;
    cc_1_1_3 -> cc_0_1_3;
 
    "cc 11 1" -> "cc 11 0";
    "cc 11 1" -> "cc 10 1";
 
    "cc 10 1" -> "cc 10 0";
    "cc 10 1" -> "cc 9 1";
 
    "cc 9 1" -> "cc 9 0";
    "cc 9 1" -> "cc 8 1";
 
    "cc 8 1" -> "cc 8 0";
    "cc 8 1" -> "cc 7 1";
 
    cc_6_1_2[label="cc 6 1"];
    "cc 7 1" -> "cc 7 0";
    "cc 7 1" -> cc_6_1_2;
 
    cc_6_0_2[label="cc 6 0"];
    cc_5_1_2[label="cc 5 1"];
    cc_6_1_2 -> cc_6_0_2;
    cc_6_1_2 -> cc_5_1_2;
 
    cc_5_0_2[label="cc 5 0"];
    cc_4_1_2[label="cc 4 1"];
    cc_5_1_2 -> cc_5_0_2;
    cc_5_1_2 -> cc_4_1_2;
 
    cc_4_0_2[label="cc 4 0"];
    cc_3_1_2[label="cc 3 1"];
    cc_4_1_2 -> cc_4_0_2;
    cc_4_1_2 -> cc_3_1_2;
 
    cc_3_0_2[label="cc 3 0"];
    cc_2_1_2[label="cc 2 1"];
    cc_3_1_2 -> cc_3_0_2;
    cc_3_1_2 -> cc_2_1_2;
 
    cc_2_0_2[label="cc 2 0"];
    cc_1_1_4[label="cc 1 1"];
    cc_2_1_2 -> cc_2_0_2;
    cc_2_1_2 -> cc_1_1_4;
 
    cc_1_0_4[label="cc 1 0"];
    cc_0_1_4[label="cc 0 1" style=filled fillcolor="#F0BA32"];
    cc_1_1_4 -> cc_1_0_4;
    cc_1_1_4 -> cc_0_1_4;
}

増加の程度

増加の程度は、空間については木の最大の深さより \( \Theta(n) \)。

段階数についてはよく分からなかったので、「SICP exercise 1.14 - Drewiki」を参考にした。

(cc n m) の段階数を \( N(n, m) \) とする。ボトムアップで考えて

$$ \begin{align*} N(n, 1) &= 1 + N(n, 0) + N(n - 1, 1) \\ N(n, 2) &= 1 + N(n, 1) + N(n - 5, 2) \\ N(n, 3) &= 1 + N(n, 2) + N(n - 10, 3) \\ N(n, 4) &= 1 + N(n, 3) + N(n - 25, 4) \\ N(n, 5) &= 1 + N(n, 4) + N(n - 50, 5) \end{align*} $$

\( N(n, 1) \) について、\( N(n, 0) = 1 \) であるから、\( N(n, 1) = 2 + N(n - 1, 1) \)。これは初項 1（\( n = 0 \) のとき）の等差数列であるから、\( N(n, 1) = 2n + 1 \)。

\( N(n, 2) \) について、\( n - 5 \) が 0 になるまで約 \( \frac{n}{5} \) 回。\( N(n, 1) = \Theta(n) \) なので

$$ \begin{align*} N(n, 2) = \Theta \left( n \cdot \frac{n}{5} \right) = \Theta(n^2) \end{align*} $$

同様に考えて、\( N(n, 3) = \Theta(n^3) \), \( N(n, 4) = \Theta(n^4) \), \( N(n, 5) = \Theta(n^5) \) となる。(count-change n) では (cc n 5) を呼び出すので、増加指数は \( \Theta(n^5) \) である。