SICP問題1.14
プログラムの木構造は以下のとおりとなる。
(11 5) ┌─┴─┐ (-39 5) (11 4) ┌─┴─┐ (-14 4) (11 3) ┌───┴────────┐ (1 3) (11 2) ┌─┴┐ ┌───┴─────────┐ (-9 3) (1 2) (6 2) (11 1) ┌─┴─┐ ┌┴───────┐ ┌┴┐ (-4 2) (1 1) (1 2) (6 1) (10 1) (11 0) ┌─┴─┐ ┌┴──┐ ┌┴┐ ┌┴┐ (0 1) (1 0) (-4 2) (1 2) (5 1) (6 0) (9 1) (10 0) ┌┴─┐ ┌┴┐ ┌┴┐ (0 1) (1 0) (4 1) (5 0) (8 1) (9 0) ┌┴┐ ┌┴┐ (3 1) (4 0) (7 1) (8 0) ┌┴┐ ┌┴┐ (2 1) (3 0) (6 1) (7 0) ┌┴┐ ┌┴┐ (1 1) (2 0) (5 1) (6 0) ┌┴┐ ┌┴┐ (0 1) (1 0) (4 1) (5 0) ┌┴┐ (3 1) (4 0) ┌┴┐ (2 1) (3 0) ┌┴┐ (1 1) (2 0) ┌┴┐ (0 1) (1 0)
プロセスのステップ数とスペース量の増加の程度は以下のようになる。
ステップ数はccを呼び出す回数(コインの数分呼び出しが指数的に増加する)→指数的に増加 必要なスペース量は計算中どの節が上方に残っているかを覚えておく量→入力に対して線形にしか増加しない。 よってステップ数の増加の程度はΘ(n^5) スペース量の増加の程度はΘ(n)
だと思うけど、さっぱり自信なし…。