2013年3月30日土曜日

SICP: Exercise 1.14

木の図示

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

(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;
}

増加指数

増加指数は、空間については木の最大の深さより Θ(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) = Θ(n) なので

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

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

0 件のコメント :

コメントを投稿