Scheme - 手続きとその生成するプロセス(プロセスが使うスペースとステップ数の増加の程度)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.3(増加の程度)、問題 1.14.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.14.

スペースの増加の程度はΦ(n)。

ステップ数の増加の程度について。

f(n, 5) = 1 + f(n, 4) + f(n -50, 5)

f(n, 4) = 1 + f(n, 3) + f(n - 25, 4)

f(n, 3) = 1 + f(n, 2) + f(n - 10, 3)

f(n, 2) = 1 + f(n, 1) + f(n - 5, 2)

f(n, 1) = 1 + f(n, 0) + f(n - 1, 1) = 1 + 1 + f(n - 1, 1) = 2 + f(n - 1, 1)

f(n, 1) = 1 + 2n

f(n, 1)のステップ数の増加の程度はΦ(n)。

f(n, 2) = 1 + f(n, 1) + f(n - 5, 2) = 1 + 1 + 2n + f(n - 5, 2) = 2 + 2n + f(n - 5, 2) = 2 + 2n + f(n - 5, 1) + f(n - 10, 1) = …

n - 5が0になるまで約n / 5回で、f(n, 1)のステップ数の増加の程度はΦ(n)ということから、f(n, 2)のステップ数の増加の程度はΦ(n・n / 5) = Φ(n^2 / 5) = Φ(n^2)。

f(n, 3) = 1 + f(n, 2) + f(n - 10, 3) = 1 + f(n, 2) + f(n - 10, 2) + f(n - 20, 3) = …

n - 10が0になるまで約n / 10回で、f(n, 2)のステップ数の増加の程度は Φ(n^2 / 5)なので、f(n, 3)のステップ数の増加の程度はΦ(n^2 * n / 10) = Φ(n^3)。

f(n, 4) = … + f(n, 3) + f(n - 25, 4) = … + f(n, 3) + f(n - 25, 3) + f(n - 50, 4) = …

…

上記を繰り返していき、求めるf(n, 5)、すなわち両替の金額の増加につれ、プロセスが使うステップの増加の程度はΦ(n^5)である。