プログラミング 4 探索と計算量.

Presentation on theme: "プログラミング 4 探索と計算量."— Presentation transcript:

1 プログラミング 4 探索と計算量

2 探索アルゴリズム 配列の中から，指定した値を見つける 代表的なものとして 2 つ扱う アルゴリズム（algorithm）：計算手順
配列中でその値を見つけた要素番号を返す 複数ある場合は，最初に見つけたもの 1 つでよいものとする 見つからない場合「見つからない」と報告する 代表的なものとして 2 つ扱う 線形探索（リニアサーチ） 二分探索（バイナリサーチ） アルゴリズム（algorithm）：計算手順

3 線形探索(1) 配列の先頭から指定された値を探していく 例：「26」を探す 配列の最後まで達してしまったら「見つからなかっ た」 31 41
a[0] は 31：違う，次へ a[1] は 41：違う，次へ a[2] は 59：違う，次へ a[3] は 26：見つかった！ 配列の最後まで達してしまったら「見つからなかっ た」 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 41 59 26 53 58 97 93 23 84

4 線形探索(2) a[] と要素数 n，探したい値 x を与えて，見つかった らその要素番号を，見つからなければ -1 を返す int linsearch(int a[], int n, int x) { int i; for (i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; } これは書けるようにしておく！

5 二分探索(1) 整列済み（昇順または降順）の対象に適用できる 探索される範囲の中央の要素と探したい値を比べ，範 囲を狭めていく
例：「31」を探す a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 23 26 31 49 53 58 59 84 93 97 23 26 31 49 53 58 59 84 93 97 23 26 31 49 53 58 59 84 93 97

6 二分探索(2) 昇順に整列された要素数 n の a[] から，x を探す（見つ からないときは -1 を返す） int binsearch(int a[], int n, int x) { int l, r, m; l = 0; r = n - 1; while (l <= r) { m = (l + r) / 2; if (a[m] == x) return m; if (x < a[m]) { r = m - 1; } else { l = m + 1; } } return -1; }

7 線形探索と二分探索の比較 アルゴリズムの特徴 適用する場合の条件 手間 線形探索：先頭から値を探していく
二分探索：「半分半分」にして範囲を絞り込む 適用する場合の条件 線形探索：特になし 二分探索：整列済みである必要がある 手間 線形探索：探索する要素数が倍になれば手間も倍になる 二分探索：探索する要素数が倍になっても手間は +1 程度 二分探索のほうが手間が少ない……！？

8 計算量(1) ある処理が，どれくらい手間がかかるのかをはかる指 標（時間計算量） 単に「計算量」といえばたいてい時間計算量をさす
どれくらい記憶容量を要するのかをはかることもある（空間 計算量） 時間計算量は，本当に時間を計ると，環境ごとに違ってしま う→手間・実行回数を計る（数える） 多くの場合，データ数に対する手間の増え方を問題にする

9 計算量(2) 例 1：配列の合計を求める関数 int sumary(int a[], int n) { int i, s; s = 0; for (i = 0; i < n; i++) { s += a[i]; } return s; } データ数（要素数）n について 要素数が倍になると，手間はおよそ倍になる この処理の手間は，およそ要素数に比例する

10 計算量(3) 例 2：配列の要素の最大値を求める int amax(int a[], int n) { int m, i; m = a[0]; for (i = 0; i < n; i++) { if (a[i] > m) { m = a[i]; } } return m; } この処理は，データ数 n に比例する程度の手間がか かる

11 計算量(4) 例 3：n 点の中のもっとも遠いものを求める double maxdist(Point pt[], int n) { double m, d; int i, j; m = 0; for (i = 0; i < n - 1; i++) { for (j = i + 1; j < n; j++) { d = (pt[j].x - pt[i].x) * (pt[j].x - pt[i].x) (pt[j].y - pt[i].y) * (pt[j].y - pt[i].y); if (d > m) { m = d; } } } return sqrt(m); } 繰り返し回数は n(n - 1) / 2 ＝ (n2 – n) / 2 回 n の 2 次式で表される

12 計算量(5) 例 4：n を 10 進表記で逆順に出力させる void revdig(int n) { while (n > 0) { printf(“%d”, n % 10); n /= 10; } printf(“\n”); return; } n の桁数だけの手間がかかる n が 10 倍になると手間が +1 になる

13 計算量(6) 計算の手間（計算量）は多くの場合，繰り返しの回数 で決まる 計算の手間を数式で表して見積もる
繰り返しがデータ数などでどのように増えるかを調べること が重要 計算の手間はデータ数に比例する 計算の手間はデータ数の 2 乗に比例する データ数が x 倍になると手間が +1 される 計算の手間を数式で表して見積もる 場合によって繰り返し回数が変動する場合がある if 文のように場合によって実行されたりされなかったりする 場合がある 計算量の見積もりは多くの場合「ざっくり」行う

14 計算量のオーダ(1) 計算量は，「比例する程度」などに近い表現で表す 対象とする量（おもにデータ数 n）がじゅうぶんに大 きい場合で見積もる
オーダ記法 O(・) で表す n に比例する程度：O(n) n の 2 乗に比例する程度：O(n2) n にかかわらずいつも同じ：O(1) かっこの中には，計算量を式で表したときのもっとも次数が 高い項を書く 計算量が厳密には n2 + 3n + 6 だったら O(n2) 最高次の係数（定数倍）は省略する

15 計算量のオーダ(2) 例 1：配列の合計→O(n) 例 2：配列の最大値→O(n) 例 3：距離の最大値→O(n2)
係数の 1/2 は省略，1 次以下の項は無視する 例 4：数を逆順出力→O(log n) 「一方を〇倍すると他方は +1」の関係は log になる 対数の底は，底変換で定数倍になるのでなんでもよい

16 計算量のオーダ(3) 加算：大きいほうを残す 乗算：乗算する
処理が続けて行われる場合（合計の計算量） O(n) + O(n2) → O(n2) O(log n) + O(n) → O(n) 乗算：乗算する 処理が繰り返される場合 O(n) × O(n) → O(n2) O(n) × O(log n) → O(n log n) 計算量の序列 O(1) ＜ O(log n) ＜ O(√n) ＜ O(n) ＜ O(n log n) ＜ O(n2) ＜ O(n3) ＜ …… ＜ O(cn)（指数） 指数オーダは計算の手間がかかりすぎる，「事実上計算でき ない」とされる

17 探索アルゴリズムの計算量 線形探索 二分探索 計算量は，平均の場合と最悪の場合を分けて議論する 場合がある
平均して n / 2 回繰り返される →平均の場合：O(n) 見つからない場合は最悪で，n 回繰り返される →最悪の場合：O(n) 二分探索 対象が倍になったら 1 増える →O(log n) 計算量は，平均の場合と最悪の場合を分けて議論する 場合がある アルゴリズムによっては，最悪の場合にひじょうに手間がか かるものがある