アルゴリズムと計算量

[教科書6.1.1]

同じ処理結果が求まるプログラムはいろいろあり得るが、本質的に違うなやり方としてどのようなものがあるのか、とそれらの計算の大変さの違いを知りたい。そこでプログラムを抽象化してアルゴリズムというものを考える。

アルゴリズム: 問題を解くための手順で、いつか止まることが保証されているもの。プログラムの細い違いは無視してしまう。

アルゴリズムの重要性

アルゴリズムによって性能に大きな違いがある
- 同じ処理結果が求まる複数のアルゴリズムがある
- アルゴリズムによって計算時間が桁違いに変わることがある
アルゴリズムは類型化されている
- 全く違う問題を解くアルゴリズムが同じものになることがある
- 性能に関する考察・プログラミングを共通化することができる

一見簡単そうに見えて大変な問題の例

ハノイの塔のシミュレーターで試してみよ。

ルール

大きさの異なる穴のあいた円盤と3本の杭(左,中央,右)からなる。
最初は全ての円盤が左の杭に積み重なっている。
小さな円盤が大きな円盤の上になるように積み重ねなければならない。
円盤は一回に1枚だけ、異なる杭に移動することができる。
全ての円盤を右の杭に移動するのが目的である。

アルゴリズム: 円盤を杭AからCに移動するには、一番以外をBに移動してから、一番下をCに移動し、Bに移動してあったものをCに移動する。
計算時間: 円盤がn枚あると $2^n-1$ 回かかる。n=100だと大体 $10^{30}$ 回程度になる！

アルゴリズムの例: 平方根

アルゴリズムの実例として平方根を計算するアルゴリズムを3種類示す。 [教科書6.1.2]

問題: 与えられた $x$ の平方根 $\sqrt{x}$ を求める。

コンピュータの制限: 小数の計算は有限の精度で行われるので、近似値しか求められない。(小数点のある数の表現)

問題を具体化したもの: ある正の実数xが与えられた時に、２乗するとxに近くなる正の実数yを精度δで求める。つまり、 $\sqrt{x}\leq y<\sqrt{x}+\delta$ となるyを一つ求める。

反復法: yをδずつ大きくしていき、y²>xとなったら終了する。
y ← 0 ... 初期値 while (y+δ)² < x do ... 小さければ、 y ← y+δ ... δだけ増やしてみる done return y
デモ用のプログラム: algorithm1.rb
アルゴリズムの速度: 繰り返しの回数で比べる
- プログラムの実行速度の非常におおざっぱな近似
- 実際のコンピュータの性能と無関係に検討できる
- 異なる種類の計算の速度差も無視してしまう
反復法の場合の速度:

二分法: 紙の辞書を牽く時のように見当をつけながら絞って行く。

$\sqrt{x}$ が(a,b)の間にあるように探していくと以下のようになる。
a ← 0 ... 下限 b ← x ... 上限 while b-a >δ do c ← (a+b)/2 ... 中点 if c² > x ... 中点では大きすぎ、 then b ← c ... 中点を上限とする else a ← c ... 中点では小さすぎなら、下限とする endif done return a

デモ用のプログラム: algorithm2.rb

二分法の場合の速度: $\log_2(x/\delta)$
(1回ごとに上限と下限の巾が半分になるので、 $x/2^n<\delta$ となるn回繰り返す。)

ニュートン法: f(y)=y²-xのX軸との交点のx座標が $\sqrt{x}$ である。 $\sqrt{x}$ の近似値をyとして、f(y)=y²-xのyでの接線とX軸との交点のx座標をyの次の近似値とする。これを繰り返す。

$next(y)=r-\frac{y^2-x}{2y}$

y ← x ... とりあえずxから始めてみる while |x-y²| > 2yδ do ... |y-next(y)|がδより大きかったら、 y ← (y²+x)/(2y) ... 接線とX軸の交点を計算する。 done return y

デモ用のプログラム: algorithm3.rb

ニュートン法の場合の速度: 誤差eが1より小さくなれば、後のステップは $\log_2(\frac{\log(\delta)}{\log(e)})$
(ニュートン法を1回実行すると、誤差 $e$ が $e^2$ となることから、 $2^n\log(e)\leq \log(\delta)$ なるようなnの回数だけ計算するので)

方法による精度と反復回数の違い

	反復法	二分法	ニュートン法
精度	0.0001	0.0001	0.0001
結果	1.4142	1.414185	1.414216
反復回数	14142	15	3

計算量

[教科書6.1.4]

計算時間の見積りは重要である。

「天気予報」の計算に３日かかっては困る。
「百年後に答えが出る」は解けないのと同じことである。

計算時間はプログラムの細かい違いやCPUの違いに影響されるのでそれを求めるのは大変である。しかし、まずはおおざっぱな見積りが欲しいことが多いので、計算時間を抽象化した「計算量」というものを考える。

計算量: アルゴリズムで見積った計算時間
- CPUの性能の違いやプログラムの作り方を無視する。
- 「問題の大きさ」と「計算時間」の関係で見積ってしまう。

計算量の使い方

アルゴリズムどうしを比べる。
プログラムを作る前に良いアルゴリズムを選べる。
プログラムの計算時間を予想する。
- 悪いアルゴリズムが現実的な時間で終わらないことが分かる。
- 小さな問題の計算時間から大きな問題の時間を予想できる。

計算量の見積り方

問題の大きさを変数で表す。例：n個のデータを処理する
計算の回数を式で表す。例：3n+8回、 $5\log_2(n+1)$ 回
詳細な式ではなくオーダーを使う。例：O(n)回、O(log n)回
ポイント:定数を無視する。各変数について一番変化の大きな項だけ残す。
理由：定数倍の差はCPUの性能の違いやプログラムの作り方ですぐに変わる。

例：平方根の計算の計算量

問題: 精度δでxの平方根を求める。
問題の大きさに影響する変数：xとδ
計算量:
- 反復法: $O(\sqrt{x}/\delta)$
- 二分法: $O(\log_2(x/\delta))$
- ニュートン法: $O(\log_2(\log_2(1/\delta)))$ ( $x$ との関係は不明。初期値によっては収束しないこともある。)

計算量の違いによる実行時間の差(1回の計算に1nsかかるとした場合の計算時間)

計算量 n=1 10 100 1000 10000 100000 1000000 10000000
log n - 1ns 2ns 3ns 4ns 5ns 6ns 7ns
n 1ns 10ns 100ns 1μs 10μs 100μs 1ms 10ms
n² 1ns 100ns 10μs 1ms 0.1s 10s 16分 27時間
n³ 1ns 1μs 1ms 1s 16分 11日 31年 3000年
2ⁿ 2ns 1μs 40兆年 - - - - -

実験データを処理するソフトを買いに行ったらAとBの2つの製品があった。 Aには「O(N²)」、Bには「O(N log₂(N))」と書かれている。試しに1000件のデータを処理させたところ、Aは1秒で終わったが、Bは10秒かかってしまった。実際に処理するデータは100万件である。実験結果の発表会は3日後にせまっているので、2日後には計算が終わっていて欲しい。さて、あなたならどちらの製品を選ぶか？

$x^n$ (nは自然数とする)を計算するアルゴリズムを考え、計算量を導いてみよ。ここでは、nに対する依存性だけを考え、乗算は1単位の時間で計算できるとする。次に、nが偶数の場合は $x^n=(x^{\frac{n}{2}})^2$ と計算できることを使って、効率的なアルゴリズムを導き、その計算量を見積もれ。

データを昇順に並べる操作(ソート,並べ替え)はよく使われる処理であり、それを計算するアルゴリズムもよく研究されている。ソートを行う4種類のアルゴリズム(単純ソート、クイックソート、マージソート、ヒープソート)の動きを可視化したものを見ると、アルゴリズムによる速度の違いが分かるだろう。データが100の場合の可視化と速度の変化を比べてみよ。 ((余談)ソートの計算量の下限)

計算可能性

問題の難しさの概観

問題をモデル化できる
- アルゴリズムがある(解ける)
  - その問題に対する計算モデルのアルゴリズムがあり、それを実行すれば有限時間のうちに必ず答えが出ることが保証されている。
  - 計算量によってさらに分類
    - O(log log n) ... 相当速い
    - O(log n) ... かなり速い
    - O(n^k) ... 現実的な時間で解ける
    - O(kⁿ) ... nが大きいと膨大な時間がかかる
- アルゴリズムが見つかってない
  - その問題に対するアルゴリズムは見つかっていないが、アルゴリズムがないことも証明されていない。
  - 例: 数学の未解決問題(に相当するもの)
- アルゴリズムがない(解けない)
  - その計算モデルでは答えを出すアルゴリズムがないことが分かっている。
  - 例: 停止性問題: 「プログラムを実行した時に、計算がいつか止まるか？」
    - プログラムを実行せずに、プログラムを眺めただけで答える。
    - 任意のプログラムについて答える。
    - プログラムを実行させてなかなか終わらない場合、「いつか止まる」と「永遠に止まらない」の区別はできない。
    このような問題を考えるためには、計算をできるだけ簡単にした計算モデルが必要。
問題をモデル化できない
- 問題をモデル化することができず、そもそも解けたかどうかを決められない。
- 例: 「コンピュータは人間の知能を模倣できるか？」
  - 何をもって人間の知能とするか？
  - (モデル化の試み) チューリングテスト
    - 端末による会話を通して、会話の相手が人かコンピュータかを判定させる。
      (emacs+doctorのデモ)

yamaguch@mail.ecc.u-tokyo.ac.jp
Copyright 2011 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科

計算量	n=1	10	100	1000	10000	100000	1000000	10000000
log n	-	1ns	2ns	3ns	4ns	5ns	6ns	7ns
n	1ns	10ns	100ns	1μs	10μs	100μs	1ms	10ms
n²	1ns	100ns	10μs	1ms	0.1s	10s	16分	27時間
n³	1ns	1μs	1ms	1s	16分	11日	31年	3000年
2ⁿ	2ns	1μs	40兆年	-	-	-	-	-

アルゴリズムと計算量

一見簡単そうに見えて大変な問題の例

アルゴリズムの例: 平方根

計算量

計算可能性

yamaguch@mail.ecc.u-tokyo.ac.jp Copyright 2011 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科

yamaguch@mail.ecc.u-tokyo.ac.jp
Copyright 2011 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科