ニ分探索法の平均比較回数についての質問です。 Show また、このようにデータ数が丁度２の何乗かになっている場合は、最大比較回数はどうなりますか？ 教えていただけると幸いです。 以下のような質問にはリアクションをつけましょう
リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。 気になる質問をクリップする クリップした質問は、後からいつでもマイページで確認できます。 またクリップした質問に回答があった際、通知やメールを受け取ることができます。 下記のような質問は推奨されていません。
適切な質問に修正を依頼しましょう。  こちらの質問が他のユーザーから「過去の低評価」という指摘を受けました。 15分調べてもわからないことは ただいまの回答率 質問をまとめることで テンプレート機能で 質問する 関連した質問同じタグがついた質問を見るアルゴリズム アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。 データ構造 データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など) こんにちは、ももやまです。 今回は基本情報にもよく出てくる探索アルゴリズム（線形探索・2分探索・ハッシュ探索）について説明していきたいと思います。 目次
スポンサードリンク １．探索とは配列やリストなどのデータ構造の中から目的のデータを探した出すことを探索といいます。 「データなんて最初から順番に探し出していけばいいじゃん！」 と思うかもしれません。 しかし、もしデータ数が100億あったらどうでしょう。 地道に計算すると日がくれそうです。もっといいアルゴリズムがないかなぁと思いたくなりますよね。 そこで今回はコンピュータ上でよく使う探索アルゴリズム、具体的には
の3つを紹介していきたいと思います。 スポンサードリンク ２．線形探索(1) 線形探索とは配列の先頭から順番に目的のデータかどうかを調べていく方法を線形探索と呼びます。 しらみつぶしに探していく最も単純な探索アルゴリズムです。 アルゴリズムとしては、先頭（0番目）の配列から順番にチェックしていき、目的のデータを見つけられたら探索成功、最後まで目的のデータが見つからなければ探索失敗となります。 (2) 線形探索のプログラム要素数 // 線形探索法 配列の先頭からしらみつぶしに調べていく
int linearSearch(int data[], int n, int x) {
for(int i = 0; i < n; i += 1) {
if(data[i] == x) {
return i; // 見つかれば場所を返す
}
}
return -1; // 見つからなければ-1を返す
}
データが見つかれば見つけた場所（配列番号）を、見つからなければ-1を返しています。 (3) 線形探索の探索回数・計算量n個のデータがある配列から線形探索で目的データを探す場合の効率性（計算量）を探索回数で考えていきましょう。 最も早い場合は先頭に目的のデータがあるときで1回、最も遅い場合は最後尾に目的のデータがある場合でn回となります。 そのため、平均で (1+n)÷2 回、最悪の場合で n 回かかります。 計算量をオーダー表記で表すと、平均の場合、最悪の場合（最も計算時間がかかる場合）ともに \( O(n) \) となります*1。 ※ 最悪の場合の探索回数、計算量の求め方がわかればOKです。以後紹介するアルゴリズムでは最悪の場合の探索回数、計算量についてのみ説明します。 (4) 線形探索における番兵上のプログラムの場合、データを探していくforループの中で「目的のデータかどうか」と「配列の最後尾までチェックしたかどうか」を毎回判定しているので少しかっこわるいですよね。 そこで、下の図のようにあらかじめ目的のデータを配列の末尾につけたします。この付け足したデータのことを番兵と呼びます。 なんでそんなことするんだ？？ と思ったかもしれません。 番兵を付け加えると、配列の中に探したい目標データが少なくとも1つは存在しますよね。 そのため、「配列の最後尾までチェックしたかどうか」を毎回チェックする必要がなくなり、「目的のデータかどうか」だけをループ内で判定するだけで済み、判定が少しスマートになります。 番兵を用いた線形探索のアルゴリズムでは、見つかったデータが番兵かもともとあったデータかどうかで判定します。 番兵より前で目的のデータが見つかれば目的データがあることがわかります。 一方目的のデータがない場合、番兵しか見つかりません。 そのため、番兵が見つかった場合は目的のデータがないことがわかります。 なお、番兵があった場合でも最大で (5) 番兵あり線形探索のプログラム番兵ありバージョンの線形探索のプログラムも紹介したいと思います。 要素数 // 番兵あり線形探索
int linearSearch2(int a[],int x) {
a[N] = x; // 番兵追加
int i = 0;
// この部分を forとifから while1個 に減らせるので効率UP
while(a[i] != x) {
i += 1; // データが見つかるまでwhileループ
}
if(i != N) {
return i; // 見つかった場合（添字を返す）
}
return -1; // 番兵までデータがない -> 探索失敗
}
先程と同じくデータが見つかれば見つけた場所（配列番号）を、見つからなければ-1を返しています。 スポンサードリンク ３．2分探索(1) 2分探索とは突然ですが下の会話をご覧ください。 友1「ねぇねぇ、今日のテスト何点だった？」 まさに、友達1が上の会話のように点数を特定していく方法が2分探索（法）です。 もう少し丁寧に書くと、目的のデータとの大小を比べることでデータを探し出すアルゴリズムが2分探索です。 データの大小を利用して探すので、あらかじめデータが小さい順（昇順）もしくは大きい順（降順）にソートしておく必要があります。 2分探索法のアルゴリズムを上のデータを例にして説明しましょう。 まず、基準となる真ん中のデータと探したいデータの大小を比べます。 目標データは7に対し基準データは11なので、目標データのほうが基準データよりも小さいですね。 すると、11以上のデータは目標データではないことがわかり、目標データがある場所を左半分にしぼりこむことができます。 再び基準となる真ん中の点を決め、目標データとの大小を比べます。 今度は目標データが7に対し基準データが4なので目標データのほうが基準データよりも大きいですね。 すると、4以上のデータは目標データではないことがわかり、目標データがある場所を左半分にしぼりこむことができます。 再び基準となる真ん中の点を決めると、目標データと基準データが一致しましたね。 目標データと基準データが一致すれば探索成功です。 逆に探索データが1つのときに「目標データ＝基準データ」とならなければ探索失敗です。 このように2分探索は、データを半分ずつにしぼりこんでいくので線形探索よりも効率よく目的データの場所（有無）を調べることができます。 なお、プログラムでは探索範囲（データがありそうな場所）の先頭を (2) 2分探索のプログラム要素数 // 二分探索 データを半分ずつにしぼりこんで特定
// 二分探索
int binarySearch(int a[],int x) {
int left = 0, right = N - 1; // 探索範囲 left 〜 right
int mid; // 基準点
while(left <= right) {
mid = (left + right) / 2; // 基準データ
if(a[mid] == x) {
return mid;
}
else if(a[mid] < x) {
left = mid + 1; // データを右半分にしぼり込む
}
else {
right = mid - 1; // データを左半分にしぼり込む
}
}
return -1; // 見つからなければ-1を返す
}
線形探索のときと同じくデータが見つかれば見つけた場所（配列番号）を、見つからなければ-1を返しています。 (3) 2分探索法の探索回数・計算量n個のデータがある配列から2分探索で目的データを探す場合の効率性（計算量）を探索回数で考えていきましょう。 2分探索の場合、データを半分ずつしぼりこみながら探索します。そのため、データ数が2倍になってはじめて探索回数が1回増えますね。 データ数が1個の場合、必ず1回で見つけ出せるので n回の探索で \( 2^{n} \) 個のデータを探索することができます。 そのため、\( n \) 個のデータを探索するために約 \( \log_{2} n \) 回かかりますね。 計算量をオーダー表記で表すと、 \( O(\log n) \) となります*2。 2分探索は線形探索に比べてとても早いことがわかりましたね！ 実はデータ数が100億あっても、たったの34回で必ずデータを発見できちゃいます！ ４．ハッシュ探索(1) ハッシュ探索とはハッシュ探索法は、何かしらの計算式を用いて格納先を決めて格納する探索方法です。 この「何かしらの計算式」を計算する関数のことをハッシュ関数と呼びます。 上の図の例では、「それぞれの桁ごとの数字を足した合計を10で割ったあまり」で求めています。 （ハッシュ関数で使われる計算式ではあまりを使うことが多いです。） (2) ハッシュ探索の長所・短所ハッシュ関数は専用の計算式からデータの格納先がわかるため、原則探索回数1回でデータを見つけ出すことができます。 計算量をオーダーで表すとなんと \( O(1) \) です。 しかしいつもうまくいくとは限らず、ハッシュ関数格納しようとした場所にすでにデータが存在し、衝突してしまうことがあります。 例えば、先程のハッシュ関数だと、13の格納位置は4、95の格納位置も同じく4となり、衝突してしまいます。 衝突してしまった場合の対策として、
の3つがあります。 よく使われるのが、3番目の重複したデータを下のようにリストでつなげていく方法です。 ５．3つの探索法の比較では、今回紹介した3つの探索法を簡単にまとめていきましょう。
探索アルゴリズムの比較
６．練習問題では、いつものように基本情報などの問題で練習（復習）していきましょう。 練習12分探索に関する記述のうち，適切なものはどれか。 [基本情報技術者平成26年秋期 午前問6] ア：2分探索するデータ列は整列されている必要がある。 練習2つぎの探索方法のうちで番兵が有効なものはどれか。 [基本情報技術者平成11年秋期 午前問26] ア：2分探索 練習32分探索において、データの個数が4倍になると最大探索回数はどうなるか。 [基本情報技術者平成17年春期 午前問15] ア：1回増える 練習4探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数をnとし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また，実行時間のオーダが \( n^{2} \) であるとは，n 個のデータを処理する時間が \( c n^{2} \) (cは定数) で抑えられることをいう。 [基本情報技術者平成16年春期 午前問11]
練習5表探索におけるハッシュ法の特徴はどれか。 [基本情報技術者平成19年春期 午前問15] ア：2分木を用いる方法の一種である。 練習6（応用）キー値が1～1,000,000の範囲で一様にランダムであるレコード3件を、大きさ10のハッシュ表に登録する場合、衝突が起こらない確率は幾らか。ここで、ハッシュ値にはキー値をハッシュ表の大きさ10で割った余りを用いる。 [ソフトウェア開発技術者平成18年春期 午前問13] ア：0.28 ７．練習問題の答え解答1解答：ア それぞれの選択肢ごとにの解説 ア：正しい。ソートされているデータでないと2分探索はできない。 解答2解答：イ 番兵は線形探索のときに使われます。 「末尾に探したいデータと同じデータ（番兵）」を追加することで、判定条件の1つである「目的のデータかどうか」を省略し、効率よく探索を行うことができます。 解答3解答：イ 2分探索では、データの個数が2倍になって初めて最大探索回数が1回増えます。 そのため、データの個数が4倍になると最大探索回数は2回となり、答えはイとなります。 解答4解答：ア 2分探索：データを半分ずつに絞り込めるのでオーダーは \( \log_{2} n \) よって答えはア。 解答5解答：ウ 選択肢ごとの解説 ア：2分木を用いるのは2分探索。NG。 解答6解答：ウ 大きさ10のハッシュ表 → 10箇所入れるところがある まず、1件目、2件目、3件目のデータを入れたときに衝突する確率を求める 1件目のデータ：10箇所どこに入れても衝突は起こらない。確率は1 よって3件データを入れたときに衝突する確率は上の3つの積で求められるので、\[ 余談 この問題、メタ読みできる人は 「選択肢ア（0.28）だけやけに小さい確率だな…… もしかして、これ逆の確率（衝突する確率）なのかな…… ってことは答えはウの0.72……？？」 と思うのかもしれません……。私は少し疑いました。 ８．さいごに今回は、基本情報にもよく出てくる3つのアルゴリズム（線形探索・2分探索・ハッシュ探索）についてのまとめでした。 探索アルゴリズムの仕組み、使える条件、計算速度の3つが重要なので必ず抑えておきましょう。 二分探索の平均比較回数は？文字Nを探索対象全体の要素数とすると、2分探索法の平均比較回数は [log2N] 回、最大比較回数は[log2N]＋1 回です(※[a]はaを超えない最大の整数を表しています)。
2分探索の比較回数は？二分探索では、要素数をnとしたとき、探索で行われる比較回数は最大でもlog2n回となる。 線形探索においては今も述べた通り、比較回数は最大で「n」回となることから、二分探索では極めて高速に要素の探索が行えることが分かる。
二分探索の計算回数は？2分探索の場合、データを半分ずつしぼりこみながら探索します。 そのため、データ数が2倍になってはじめて探索回数が1回増えますね。 データ数が1個の場合、必ず1回で見つけ出せるので n回の探索で 個のデータを探索することができます。
線形探索法の平均探索回数は？線形探索法とは、探索対象データの先頭から1つずつ順番に比較することによって目的のデータを探す方法です。 線形探索法では、N個のデータの中から目的のデータを探すときの平均比較回数は (N＋1)／2 回です。
|
二分探索 平均探索回数
著作権 © 2024 berikutyang Inc.
