SICP 読み (29)

今回は微妙な検討。

問題 2.43

問題のナニ (Louis が作ったヤツ) は末端側からリストの値が決まっていく形、と言えば良いのか。例えば (1 1 1 1 1) みたいな形は本来であればリストの要素数が 2 つ位の時点でアウト判定して、後は却下なんですが Louis のパターンだと、きっちり先頭から検討をしてしまう形になる。
要は枝刈りがされない、という事でこれが実行速度が極端に遅くなる原因となる。

可能性分の手続き呼び出しになるんで、例えば 5 マスな盤だと

5 ^ 5 + 5 ^ 4 + 5 ^ 3 + 5 ^ 2 + 5 ^ 1

回の手続き呼び出しになってしまうのではないか、と。

計算量で言えば O(n ^ n) になるの?? これはヒドいな。

対して枝刈りなケースは

(())

((1) (2) (3) (4) (5))

((11) (12) (13) (14) (15) ... (51) (52) (53) (54) (55))

くらいから枝刈りが始まるので最大 n ^ 2 か。なんか検討がざっくりすぎな気がするんですが、どうなのだろうか。以前から考えているのですが、そろそろ解答例をチェックしないと駄目だな。