1.2.3 増加オーダー

問題の大きさ（処理すべきデータの量など）が増えたときに、計算に必要な記憶空間及び時間(ステップ数)がどれだけ増えるかの指標について。

参考：ランダウの記号

例えば問題の大きさが$n$の場合に、以下のリソースを必要とするアルゴリズムがあったとして。

R(n)=3n^2+10n+17

このアルゴリズムの増加オーダーは？
この式から最も影響の大きい項($3n^2$)だけを採用し、係数($3$)も取り除いて、以下のように表す。

  R(n) = \Theta(n^2)

つまり、$n$が増えるとその２乗のオーダーで必要なリソースが増えるということだけに注目する。
例えば、以下のリソースを必要とするアルゴリズムも、

  \begin{align}
  R(n) &= n^2 \\
  R(n) &= 1000n^2 \\
  R(n) &= 0.1n^2 + 1000n
  \end{align}

全て増加オーダーとしては $R(n)=\Theta(n^2)$ となる。
こんな大雑把でいいのか？いいんです。アルゴリズムの性能を評価しようというとき、この指標が頼りになることは多い。

$\Theta(\log{n})$となる例が後ほど出てくる。
ステップのたびに処理すべき範囲が一定の割合で狭まっていくというパターンのアルゴリズムはこれ。
ソート済み数列に対する二分探索なんかがそう。ステップのたびに探索領域が半分、半分・・・になっていく。

大抵、$\Theta(\log{n})$なアルゴリズムは$\Theta(n)$なものより性能が良い。
例えば、$100000$個の数列に対する二分探索の場合、そのステップ数は $\log_2{100000} = 16.6096...$ 程度ですむ。

練習問題 1.14

前節のcount-change手続き。

1.2.2.scm

(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount (- kinds-of-coins 1))
                 (cc (- amount (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

これで11セントを両替する際に生成されるプロセスを図示せよ。
手続きccの呼び出し履歴を書いてみる。

(11 5)-(-39 5)
|
(11 4)-(-14 5)
|
(11 3)-(1 3)-(-9 3)
|      |
|      (1 2)-(-4 2)
|      |
|      (1 1)-(0 1) => 1
|      |
|      (1 0)
|
(11 2)-(6 2)-(1 2)-(-4 2)
|      |     |
|      |     (1 1)-(0 1) => 1
|      |     |
|      |     (1 0)
|      | 
|      (6 1)-(5 1)-(4 1)-(3 1)-(2 1)-(1 1)-(0 1) => 1
|      |     |     |     |     |     |
|      (6 0) (5 0) (4 0) (3 0) (2 0) (1 0)
|
(11 1)-(10 1)-(9 1)-(8 1)-(7 1)-(6 1)-(5 1)-(4 1)-(3 1)-(2 1)-(1 1)-(0 1) => 1
|      |      |     |     |     |     |     |     |     |     |
(11 0) (10 0) (9 0) (8 0) (7 0) (6 0) (5 0) (4 0) (3 0) (2 0) (1 0)

以下の4通りの組み合わせで両替できることがわかる。

[3 1]
[2 2 1]
[2 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]

一応、実行結果。

gosh> (count-change 11)
4

両替する金額を$n$とすると、このプロセスが使う空間とステップ数はどのような増加オーダーになるか。

空間の増加オーダーは $\Theta(n)$。
ネストの深さを考えればいい。直感的には、さっきの図でどれだけ右に伸びるか。

ステップ数の増加オーダーは、コインの種類が1種類ならば$\Theta(n)$。
2種類ならば、2種類のコインの組み合わせを捜索することになるので$\Theta(n^2)$。
同様に、5種類ならば $\Theta(n^5)$。

練習問題 1.15

正弦(sin)は、$x$が十分小さいとき(ここでは$|x|\leq0.1$の場合とする)には、$\sin x \approx x$の近似式で計算できる。

$x$が大きかったら？次の恒等式で十分小さくなるまで変換すればいい。

\sin x=3\sin \frac{x}{3}-4\sin^3 \frac{x}{3}

というわけで、以下のsine手続きを定義した。

ex1_15.scm

(define (cube x) (* x x x))
(define (p x)
  (print "p:" x) ; 呼び出し回数調査のために追加しました
  (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(sine 12.15)を評価する際に、手続きpは何回適用されるか？

ex1_15_a.scm

gosh> (sine 12.15)
p:0.049999999999999996
p:0.1495
p:0.4351345505
p:0.9758465331678772
p:-0.7895631144708228
-0.39980345741334

pは5回呼ばれた。

(sine a)が評価された際の、空間とステップ数の増加オーダーは？

aが十分小さくなるまで、$1/3$を何回かける必要があるか？ということなので $\Theta(\log a)$。