アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 5月6日 情報知能学科 白井英俊 計算量 問題を解く方法 何かを計算し、求める方法 アルゴリズム は何通りかある プログラムは、アルゴリズムをプログラミング言 語で実現し、動くようにしたもの アルゴリズムの計算量を調べれば 速いプログラムかどうかが分かる 要するに、計算量とは、入力に対するアルゴリズムの処理量 計算量(続き） • 逆に言えば、 計算量の小さい プログラムを作る前に 速いアルゴリズムを選び、 それに基づいてプログラムを作る ことが大事 オーダーとは、計算量の大体の目安のこと 速いアルゴリズムを選ぶ例 • 問題：n+1個の実数x1, x2, …, xn ,yが与えら れた時、 x1, x2, …, xnのうちでyにもっとも近 いものを見つけるアルゴリズム 次の方法が考えられる： (1) データを一つ一つ調べ、yとの差が最小値となる 要素を返す（逐次探索）(nearestS.rb) (2) データを降順にソートしておき、「二分探索」により 該当する要素を探す(nearestB.rb) ちょっと「探索」の話を ｎ=17, y=77とする： • 逐次探索： 先頭から一つ一つyと比較し、そ の差が最小の要素を探す 最初の要素から一つ一つ調べるために「逐 次」探索という 差 76 67 55 42 候補 37 29 22 17 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] 1 3 1 10 22 35 40 48 55 60 76 80 82 88 90 93 96 98 99 ちょっと「探索」の話を(続) ｎ=17, y=77とする： • 二分探索 探索の範囲の真ん中の要素をチェックし続け ることで、範囲の絞り込みを行う： チェックする候補 77 > 76 から大の方 77< 90から小の方 77< 82から小の方 (0 + 16) / (8 + 16) / (8 + 12) / (8 + 10) / 2 2 2 2 =8 = 12 = 10 =9 差＝ 1 13 5 3 （8+9)/2 = 8 なので、[8]と[9]の要素を比較して終了 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] 1 10 22 35 40 48 55 60 76 80 82 88 90 93 96 98 99 逐次探索と二分探索 • 今の例では、探索対象となった数の個数が少ない (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の関数で表したも のがオーダ。 確認：n**2とn は同じ 今の例では、 O(n2) となる 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 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(2n) 速いアルゴリズムを選ぶ例（再） • 問題：n+1個の実数x1, x2, …, xn ,yが与えら れた時、 x1, x2, …, xnのうちでyにもっとも近 いものを見つけるアルゴリズム 計算量はO(log(n)) データ(n個）が降順にソートされているとすれば、 (1) 「二分探索」により該当する要素を探す (nearestB.rb) 計算量はO(n) (2) データを一つ一つ調べ、yとの差が最小値となる要 素を返す（逐次探索）(nearestS.rb) 速いアルゴリズムを選ぶ別な例 問題：n個のデータから最も大きいものk個を見つ け出す。(例えば n =1,000,000、 k =10） 計算量はO(n*log(n)) 計算量はO(k) 次の方法が考えられる： (1) データを降順にソートし、上から順にk個選ぶ (2) データの最大値を選び、それをデータから削 除する。これをk回繰り返す。 計算量はO(n) 計算量はO(k*n) 計算量とオーダ • 計算量の式からオーダを求めるには、 1.定数は無視する ただし、元の式がnを含まない場合は1とする 2.nが無限大に近付くときに最も大きくなるnの 項を取り出す 。 例えば、3n**2+8*n+6のオーダはn**2。 これを O(n2) と表す 計算量とオーダ(続) • オーダを求めるには、 log(n), n, n*log(n), n2, n2*log(n), n3, 2n, n!, nn のような関数が、nの値の変化に対して(特にnが大き な値のときに）どのように大きくなるかを認識する必 要がある。 • それを図示するソフトウェア の一つが GnuPlot。 • 対数 の知識も不可欠。 Gnuplotの使用例 log(x), (log(x)) 2, x, x*log(x), x2の比較 1e+008 x log(x) x*log(x) x**2 (log(x))**2 1e+007 1e+006 100000 10000 1000 100 10 1 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Gnuplotの使用例 log(x), 2 3 , x, x , x の比較 x 1e+009 x**0.5 x 1e+008 log(x) x**2 x**3 1e+007 1e+006 100000 10000 1000 100 10 1 100 200 300 400 500 600 700 800 900 1000 Gnuplotの使用例 x, x2, x3, 2x, x!, xxの比較 1e+090 x x**x 1e+080 fact(x) 2**x x**3 1e+070 1e+060 1e+050 1e+040 1e+030 1e+020 1e+010 1 5 10 15 20 25 30 35 40 45 50 計算量：時間と空間 • 時間計算量、もしくは時間複雑度(time complexity) そのアルゴリズムを実行するのに、最悪の場合、どのくらい 時間がかかるかを、入力の大きさの関数として表す • 空間計算量、もしくは空間複雑度(space complecity) そのアルゴリズムを実行するのに、最悪の場合、どのくらい 記憶領域が必要かを、入力の大きさの関数として表す 計算量（複雑度）＝時間計算量＋空間計算量 時間計算量の常識的な評価 • 教科書p.8 O(1) --- 理想的に速い O(log n) --- 非常に速い O(n) --- 速い O(n log（n)) --- 速いほう O(n2) --- かなり遅いが、許されないほどではない O(n3) --- かなり遅い。許される限界。 O(cn ) --- (cは1より大きい定数）。指数オーダ (exponential order)。とっても遅い。 計算量の演習1 • 教科書p.11 1.1 次の5種類の計算時間を、nを横軸にとって、一つ のグラフに重ねて表せ。そして、そのグラフから オーダの大小関係が読み取れることを観察せよ。 f1(n) = 10000 n f2(n) = 10000n log(n) f3(n) = １00 n**2 f4(n) = 10 n**3 f5(n) = 2**n 計算量の演習２ • 教科書p.11 1.2 ステップ数が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.11 1.4 次の式のオーダを、最も忠実で簡単な式を用いて 表せ。 (1) 6.5n3 + 8n2 + 5 (2) 5 n log(n) + 3 n2 (3) 2.5 n √n + 3.6 n log(n) (4) 5 n + 8 log(n) (5) 2n + 5 n 5 (6) 800 n log(n) + n 予習：「2章リスト構造」のために ポインタ(pointer) • ポインタの元々の意味は「指さし」。 コンピュータにおいて「何が何を指すか」というと、 「変数の値」が 「ある実体(オブジェクト)」を指すので ある。 つまり、「変数」の値として 123のような数という「実 体」が入っているのではなく、「実体」 への手がかり (記憶番地、アドレス)が入っている場合、その手が かり(アドレス)をポインタという。 • 参考: プログラミング言語Cでは、int *x のように書 いて、変数xは、整数オブジェクトへのポインタ(アド レス)を値とする、というように宣言する ポインタの詳細 今までの｢変数」の イメージ： 変数名 x n 数や文字列を記憶 するためのラベル 記憶場所 123 関係付け(ラベル） ポインタの詳細(続） • アドレス（記憶番地）：コンピュータの記憶場所 ここでは少し拡張して「データの格納場所の手が かり」（場所の情報）と考える 例： 配列のインデックス 変数名 x 記憶場所 記憶場所 アドレス かなりの場所を 必要とする複 雑なデータ
© Copyright 2024 ExpyDoc
