Help us understand the problem. What is going on with this article?

SICP読書録 #6 1.2.3 増加オーダー

More than 1 year has passed since last update.

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

1.2.3 増加オーダー

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

参考:ランダウの記号

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

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

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

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

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

  \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)$。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした