第4回SICP勉強会

今回は1.2.2 木構造再帰と1.2.3 増加の程度について。ようやく勉強会らしくなってきた感じ。

問題1.14のcount-changeのステップ数のオーダを求めるのでかなりてこずってたけど、id:banjunの解法により、どうやらＯ(n^5)らしいということで解決ということに。

ちなみに、700までのステップ数を数えて、適当にＯ(n^5)な関数と並べて見たのが下のグラフ。

もちろん、こんなことやっても数学的にはあんまり意味のないことだけど。

ところで、count-changeの空間計算量は「ステップ数に比例するはず」ということでＯ(n^5)としていたけれど、すべてのステップが同時に計算されるわけではなくて、(プロセスを示す木でいうところの)根から1つの葉までの深さに比例した量のメモリが消費されるのだからＯ(n)だということらしい。ボロボロですね…。

んー、これはそろそろ院試の勉強をまじめにやれということか。