アルゴリズムとデータ構造 第 1 章 アルゴリズムと計算量 5 月 6 日 情報知能学科 白井英俊

計算量 問題を解く方法 何かを計算し、求める方法 は何通り かある アルゴリズ ム プログラムは、アルゴリズムをプログラミ ング言語で実現し、動くようにしたもの アルゴリズムの計算量を調べれば 速いプログラムかどうかが分かる 要するに、計算量とは、入力に対するアルゴリズムの処 理量

計算量 ( 続き） 逆に言えば 、 プログラムを作る前に 速いアルゴリズムを選び、 それに基づいてプログラム を作る ことが大事 計算量の小さい オーダーとは、計算量の大体の目安のこと

速いアルゴリズムを選ぶ例 問題： n+1 個の実数 x 1, x 2, …, x n,y が与え られた時、 x 1, x 2, …, x n のうちで y にもっ とも近いものを見つけるアルゴリズム 次の方法が考えられる： (1) データを一つ一つ調べ、 y との差が最小値とな る要素を返す（逐次探索） ( nearestS.rb ) (2) データを降順にソートしておき、「二分探 索」により該当する要素を探す ( nearestB.rb )

ちょっと「探索」の話を ｎ =17, y=77 とする： 逐次探索： 先頭から一つ一つ y と比較し、 その差が最小の要素を探す 最初の要素から一つ一つ調べるために「逐 次」探索という [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] 差 候補

ちょっと「探索」の話を ( 続 ) ｎ =17, y=77 とする： 二分探索 探索の範囲の真ん中の要素をチェックし 続けることで、範囲の絞り込みを行う： [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] チェックする候補 (0 + 16) / 2= 8 差＝ 1 77 > 76 から大の方 (8 + 16) / 2= < 90 から小の方 (8 + 12) / 2= < 82 から小の方 (8 + 10) / 2 = 93 （ 8+9)/2 = 8 なので、 [8] と [9] の要素を比較して 終了

逐次探索と二分探索 今の例では、探索対象となった数の個数が少な い (n=17) ので、どちらが速いかは分かりにくか ったかもしれない。 でも、想像力を働かせて、 n=1,000,000 のときを 考えてみよう。どちらの方式が ( いろいろな y の 値に対して）速いだろうか？ 分からない？ それでは、プログラムを走らせて試してみよう 。でもその前に、「プログラムの実行時間を計 測する」という話を。。。

時間について 実時間＝経過時間とも ＣＰＵ時間＝プログラムの実行でＣＰＵを使った時間 キーボードから入力する場合、経過時間は増えるが、Ｃ ＰＵ時間は増えない --- 実時間よりも CPU 時間の方がアル ゴリズムの「速さ」を表している ユーザーＣＰＵ時間：アプリケーションプログラム自体 が直接ＣＰＵを使っている時間。計算時間など。 システムＣＰＵ時間：アプリケーションの依頼でＯＳが 仕事をする（例えばディスクを読む）時にＯＳが使うＣ ＰＵ時間。ディスクを読む場合には、実際にディスクを 読んでいる時間中でなくその前後でＯＳがＣＰＵを使う。 Ruby では … （ Time.now とは違うよ ) Process.times

アルゴリズムが速いかどうか … ベンチマークテスト 「プログラム」 ( やコンピュータなど）に 対し、特定の処理をさせて、それに要す る時間（ユーザー時間＋システム時間） を計測する この方法は、アルゴリズムにも適用でき る。しかし、アルゴリズムを「解析」す れば、処理時間や処理に要するメモリを 求めることができる

速さの比較 100 万個の整数が入っている sortedNums.txt それに対して、二分探索 (nearestB.rb) と逐次探索 (nearestS.rb) の二つの方法でプログラムを書き、 速さを比較する どちらが速いだろうか？ 内容：どちらも、 getNumbers と nearest という関数 を含み、処理時間を計測する。 getNumers はファイルから整数の配列を作る。 nearest は、その配列で、対象の数に最も近い数 を返す。

計算量とオーダ アルゴリズムの「理論的な」計算量は、処 理する計算機の性能と、アルゴリズムの手 続きを解析することにより求められる。 入力の大きさを n とすると、例えば、 3n ** 2+8 * n+6 のように求めることができる。 これを、できるだけ簡単な n の関数で表し たものがオーダ。 今の例では、 O(n 2 ) となる 確認： n ** 2 と n 2 は同 じ

アルゴリズムの計算量 以下のような繰り返しでは、計算量は繰り返しの回数に比例 例１： for i in 1..n print i, i**2, i**3,”\n” end 累乗計算や print 文の実行の計算量をまとめて ( 計算機やプログラミン グ言語の実装方法で異なるので）定数の a で表すとする。この例では、 これが n 回繰り返されるので、計算量は a*n 、オーダは O(n) と表され る 例２： for i in 1..n # n 回繰り返す for j in 1..n # n 回繰り返す print a[i,j]*a[j,i],”\n” end これは二重の繰り返しとなっている。 の部分が n 回、 その中で、 の部分が n 回繰り返されている。つごう、 の 部分が n**2 回繰り返される。この例でも配列の参照や print 文の実行の 計算量をまとめて定数の b で表すと、この例の計算量は b*n**2 、オー ダーは O(n**2)

関数を用いている場合 関数の性質によって計算量は異なる 入力の大きさを n とすると一般に： ソート ( 並び替え） ⇒ O(n*log(n)) 配列への操作（代入、アクセス） ⇒ O(1) 配列への要素の追加 ⇒ O(n) 再帰関数の場合はいろいろ．．．第 5 章参照 階乗計算の場合は O(n), ハノイの塔の場合は O(2 n ) アルゴリズムの計算量 ( 続 )

速いアルゴリズムを選ぶ例 （再） 問題： n+1 個の実数 x 1, x 2, …, x n,y が与え られた時、 x 1, x 2, …, x n のうちで y にもっ とも近いものを見つけるアルゴリズム データ (n 個）が降順にソートされているとすれば、 (1) 「二分探索」により該当する要素を探す ( nearestB.rb ) (2) データを一つ一つ調べ、 y との差が最小値とな る要素を返す（逐次探索） ( nearestS.rb ) 計算量は O(log(n)) 計算量は O(n)

速いアルゴリズムを選ぶ別な例 問題： n 個のデータから最も大きいもの k 個を 見つけ出す。 ( 例えば n =1,000,000 、 k =10 ） 次の方法が考えられる： (1) データを降順にソートし、上から順に k 個 選ぶ (2) データの最大値を選び、それをデータか ら削除する。これを k 回繰り返す。 計算量は O(n*log(n)) 計算量は O(k) 計算量は O(n) 計算量は O(k*n)

計算量とオーダ 計算量の式からオーダを求めるには、 1. 定数は無視する ただし、元の式が n を含まない場合は 1 とする 2.n が無限大に近付くときに最も大きくなる n の項を取り出す 。 例えば、 3n**2+8*n+6 のオーダは n**2 。 これを O(n 2 ) と表す

計算量とオーダ ( 続 ) オーダを求めるには、 log(n), n, n * log(n), n 2, n 2 * log(n), n 3, 2 n, n!, n n のような関数が、 n の値の変化に対して ( 特に n が 大きな値のときに）どのように大きくなるかを 認識する必要がある。 それを図示するソフトウェア の一つが GnuPlot 。GnuPlot 対数 の知識も不可欠。 対数

Gnuplot の使用例 log(x), (log(x)) 2, x, x*log(x), x 2 の比較

Gnuplot の使用例 log(x),, x, x 2, x 3 の比較

Gnuplot の使用例 x, x 2, x 3, 2 x, x!, x x の比較

計算量：時間と空間 時間計算量、もしくは時間複雑度 (time complexity) そのアルゴリズムを実行するのに、最悪の場合、どの くらい時間がかかるかを、入力の大きさの関数として 表す 空間計算量、もしくは空間複雑度 (space complecity) そのアルゴリズムを実行するのに、最悪の場合、ど のくらい記憶領域が必要かを、入力の大きさの関数と して表す 計算量（複雑度）＝時間計算量＋空間計算量

時間計算量の常識的な評価 教科書 p.8 O(1) --- 理想的に速い O(log n) --- 非常に速い O(n) --- 速い O(n log （ n)) --- 速いほう O(n 2 ) --- かなり遅いが、許されないほどではない O(n 3 ) --- かなり遅い。許される限界。 O(c n ) --- (c は 1 より大きい定数）。指数オーダ (exponential order) 。とっても遅い。

計算量の演習 1 教科書 p 次の 5 種類の計算時間を、 n を横軸にとって、 一つのグラフに重ねて表せ。そして、そのグ ラフからオーダの大小関係が読み取れること を観察せよ。 f1(n) = n f2(n) = 10000n log(n) f3(n) = １ 00 n**2 f4(n) = 10 n**3 f5(n) = 2**n

計算量の演習２ 教科書 p ステップ数が f(n)=100000n, g(n)=10n**3, h(n)=2**n の 3 つのアルゴリズムに n=100 の大き さのデータを与えたとする。 1 ステップが 10**(-9) 秒で実行できるコンピュータで走らせ たときの計算時間は次のどれに近いか？ 1 ミリ秒、 1 秒、 1 分、 1 時間、 1 日、 1 ヶ月、 1 年、 1 世紀

計算量の演習３ 教科書 p 次の式のオーダを、最も忠実で簡単な式を用 いて表せ。 (1) 6.5n 3 + 8n (2) 5 n log(n) + 3 n 2 (3) 2.5 n √n n log(n) (4) 5 n + 8 log(n) (5) 2 n + 5 n 5 (6) 800 n log(n) + n

予習：「 2 章リスト構造」のた めに

ポインタ (pointer) ポインタの元々の意味は「指さし」。 コンピュータにおいて「何が何を指すか」とい うと、「変数の値」が 「ある実体 ( オブジェク ト ) 」を指すのである。 つまり、「変数」の値として 123 のような数 という「実体」が入っているのではなく、「実 体」 への手がかり ( 記憶番地、アドレス ) が入っ ている場合、その手がかり ( アドレス ) をポイン タという。 参考 : プログラミング言語 C では、 int *x のよう に書いて、変数 x は、整数オブジェクトへのポイ ンタ ( アドレス ) を値とする、というように宣言 する

ポインタの詳細 今までの｢変数」の イメージ： x n 変数名記憶場所 関係付け ( ラベル） 123 数や文字列を記憶 するためのラベル

ポインタの詳細 ( 続） アドレス（記憶番地）：コンピュータの 記憶場所 ここでは少し拡張して「データの格納場所の手 がかり」（場所の情報）と考える 例： 配列のインデックス x 変数名 アドレス 記憶場所 かなりの場所 を必要とする 複雑なデータ 記憶場所