読者です 読者をやめる 読者になる 読者になる

第4回SICP勉強会

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

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

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


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


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

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