SICP 1.2.3 Orders of Growth - プログラミング再入門

ノート

成長の次数。あるいは計算量の成長度合い。
入力の大きさとしては引数の値そのものだったり計算の精度だったり。計算量の尺度も計算のステップ数だったり必要なメモリサイズだったり。
$R(n)=\Theta(f(n))$
と表現する。良く見かけるO記法とは実は少し違うらしい。
Θ記法は大雑把な計算量を表しているだけ。 $n^2$ に比例する計算量も $100n^2$ に比例する計算量も $3n^2 + 10n + 17$ に比例する計算量も全て $\Theta(n^2)$ と表現される。

Exercise 1.14

実行すると

> (count-change 11)
4
>

４パターン。

                                                                                                                             (count-change 11)
                                                                                                                                     |
                                                                                                                     ,___________(cc 11 5)_________.
                                                                                                                     |                             |
                                                                                           ,_____________________(cc 11 4)__________________.  (cc -39 5)
                                                                                           |                                                |      |
                                             ,_________________________________________(cc 11 3)___________________________________.    (cc -14 4) 0
                                             |                                                                                     |        |
             ,___________________________(cc 11 2)___________________________.                                               ,_(cc 1 3)__.  0
             |                                                               |                                               |           |
    ,___(cc 11 1)___.                                    ,_______________(cc 6 2)________________.                    ,__(cc 1 2)_.  (cc -9 3)
    |               |                                    |                                       |                    |           |      |
(cc 11 0)  ,___(cc 10 1)___.                     ,___(cc 6 1)__.                           ,_(cc 1 2)_.         ._(cc 1 1)_.  (cc -4 2)  0
    |      |               |                     |             |                           |          |         |          |      |
    0  (cc 10 0)  ,____(cc 9 1)____.        (cc 6 0)    ,__(cc 5 1)__.               ,_(cc 1 1)_. (cc -4 2) (cc 1 0)   (cc 0 1)   0
           |      |                |            |       |            |               |          |     |         |          |
           0  (cc 9 0)   ,____(cc 8 1)____.    0   (cc 5 0)   ,__(cc 4 1)__.     (cc 1 0)   (cc 0 1)  0         0          1
                  |      |                |            |      |            |         |          |
                  0  (cc 8 0)   ,____(cc 7 1)____.    0  (cc 4 0)   ,__(cc 3 1)__.   0          1
                         |      |                |           |      |            |
                         0  (cc 7 0)   ,____(cc 6 1)___.    0  (cc 3 0)   ,__(cc 2 1)_.
                                |      |               |           |      |           |
                                0  (cc 6 0)   ,____(cc 5 1)___.   0  (cc 2 0)   ,_(cc 1 1)_.
                                       |      |               |          |      |          |
                                       0  (cc 5 0)   ,___(cc 4 1)___.   0  (cc 1 0)    (cc 0 1)
                                              |      |              |          |           |
                                              0  (cc 4 0)   ,___(cc 3 1)__.    0           1
                                                     |      |             |
                                                     0  (cc 3 0)   ,__(cc 2 1)__.
                                                            |      |            |
                                                            0  (cc 2 0)   ,_(cc 1 1)_.
                                                                   |      |          |
                                                                   0  (cc 1 0)   (cc 0 1)
                                                                          |          |
                                                                          0          1

両替金額が増えるに従って、メモリ量、計算ステップ数はどの様に増えるのか。

まずスペース。
ツリーの深さに相当。つまり全てを１セントにした時に最もスタックが深くなるので、金種によって若干のオフセットは付くもののnに比例するためΘ(n)と言える。

次にステップ。

まず1 centのみで両替する場合を考える。(cc n 0)をn回、(cc (n-1) 1)をn回、最後に(cc 0 1)を1回呼び出す。なので合計として2n+1回の関数呼び出しとなる。従ってΘ(n)である。(( (cc 11 1)以下を数えれば分かる。)
次に、5 centと1 centの場合を考える。(cc n 2)、(cc (n - 5) 2)、(cc (n - 10) 2)…の呼び出しがn/5回。それぞれが(cc n 1)、(cc (n -5) 1)…を呼び出す。これは上記の1 centのみでの両替に相当するので、Θ(n) × Θ(n)即ち $\Theta(n^2)$ と考える。実際には(cc n 1)、(cc (n - 5) 1)、(cc (n - 10) 1)…とnの部分がどんどん減って行くので全くn^2に比例する訳ではなくそれよりは少ない割合で増える。
10 centも含める場合も同様に考えると、 $\Theta(n^3)$ と言える。
同様に考えて行くと $\Theta(n^5)$ であると予想出来る。

ステップ数の方はnが小さい時にはピンと来ないが、n=100〜1000辺りで計測すると確かに爆発的に増加する事が分かる。ネット上に出ている情報だと $\Theta(n^5)$ との回答が殆どだが、実際に計測して両対数グラフにしてみると $\Theta(n^4)$ 辺りがフィットする感じ。

Exercise 1.15

角度が0.1ラジアン未満であればsin xはxとほぼ一緒。あとは３倍角の公式でxを３分の一に減らして計算。

a. pは何回呼ばれるか。
(sine 12.15)

(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))

で５回。

b)スペースとステップの成長度合いは？
aが0.1より小さくなるまで３で割る回数分pを呼ぶ。pを呼び出す回数をxとすると
$\frac{a}{3^x}<0.1$ となる最小のx。
$3^x>a\times 10$ となる最小のx。
xは $\log_3(a\times 10)$ を超える最小の整数。
a=12.15の場合、 $\log_3(a\times 10)=4.369...$ なので、xは5。
この回数だけpを呼び、その分だけスタックされるので、スペースもステップ数もΘ(log3 a)と表せる。この場合は単にΘ(log a)と書くのかも知れない。