- ベストアンサー
二分探索のアルゴリズム
nozoooの回答
あるソートされたデータについて、データ数n、計算量xとすると 線形探索ではデータ数nに比例して処理が増えるので x = n より、時間計算量はO(n)となります。 二分探索ではデータ数を半分にして、その前半か後半のどちらかを探索する処理を再帰的に繰り返すことになるので、 2^x = n の関係が成り立ち両辺に２を底とする対数を取ると x = logn より、時間計算量はO(logn)となります。
関連するQ&A
- アルゴリズム:2分探索の時間計算量
アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。 /* ２分探索 */ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を２分探索 ---*/ int bin_search(const int a[], int n, int key) { int pl = 0;/* 探索範囲先頭の添字【1】 */ int pr = n-1;/* 〃 末尾の添字 【2】*/ int pc; /* 〃 中央の添字 */ do { pc = (pl + pr) / 2;/*【3】*/ if (a[pc] == key) /* 探索成功【4】 */ return (pc);/*【5】*/ else if (a[pc] < key)/*【6】*/ pl = pc + 1;/*【7】*/ else /*【8】*/ pr = pc - 1;/*【9】*/ } while (pl <= pr);/*【10】*/ return (-1);/* 探索失敗【11】 */ } のプログラムがありますが、【1】から【11】までの 実行回数と計算量は次のようになるそうですが、 実行回数 計算量 【1】 1 O(1) 【2】 1 O(1) 【3】 logn O(logn) 【4】 logn O(logn) 【5】 1 O(1) 【6】 logn O(logn) 【7】 logn O(logn) 【8】 logn O(logn) 【9】 logn O(logn) 【10】 logn O(logn) 【11】 1 O(1) なぜ【3】や【4】がlognになるんでしょうか？ 詳しく教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 二分探索アルゴリズムの問題の解法
二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。
- 締切済み
- その他（プログラミング・開発）
- データ構造とアルゴリズムの問題が分かりません。
以下の問題で悩んでいます。 １ 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。 ２ 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。 ３ データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。 ４ アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。 ５ データを検索する操作のほうが多い場合と、データを追加する操作が多い場 合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。 １は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。 ２は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の２点 リストの利点は扱うデータを自由に変えられる点の１点しか思いつかず、欠点はよく分かりませんでした。 ３、４、５も理由をつけて説明しろと言われたら無理です。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 二分探索の平均探索回数
こんにちは、 二分探索の最大探索回数がlog2N+1なのは 書籍にある計算式の変換で理解できたのですが、平均探索回数がlog2Nなのが理解できません。 書籍では『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』と書かれていますが どういう意味なのか判りません。 そこで具体的に考えてみました。 例えば8個のデータの中から探す場合、 a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7] とデータが並んでいて、 それぞれの位置に目的の値が入っていた時の探索回数は、 3回、2回、3回、1回、3回、2回、3回、4回 と考えました。 a[1]の場所に目的の数があった場合、 2回目の探索で見つかる、という意味合いです。 最大探索回数はa[7]の時に4回となり、log2N+1になっています。 この考え方でNを増やしていった所、最大探索回数はlog2N+1になりそうです。 そこで上記の場合の平均探索回数の方は、 (3+2+3+1+3+2+3+4)/8 と計算し、2.625と考えました。 この考え方でNを増やしていくと 16コ：3.375 32コ：4.21875 64コ：5.125 128コ：6.0703125 …と、 平均探索回数がlog2Nではなくlog2N-1に近づいていきます。 考え方の間違っている箇所の指摘をお願いします。
- 締切済み
- その他（プログラミング・開発）
- 線形と二分探索により探索を行うプログラムについて教えてください
２０個の配列にデータを入れ（プログラム内で初期化と代入を行って良い）入力した数を探索するプログラムをCmachineで作成したいのですが、線形探索により探索を行うプログラムと二分探索により探索を行うプログラムの作り方を教えていただけないでしょうか？
- 締切済み
- C・C++・C#
- Euclidの互除法の時間計算量について
Euclidの互除法の時間計算量についてなんですが、 Euclidの互除法の時間計算量 Ｏ(logN)の logN の N とは何を表しているのですか？ あと、なぜＯ(logN)になるのでしょうか？ 至急知りたいんですが教えてください。
- ベストアンサー
- 数学・算数
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- アルゴリズムを勉強していたのですが、線形探索をする
アルゴリズムを勉強していたのですが、線形探索をする時にデータ件数がNの時平均比較回数が(N+1)÷2回となっていたのですが、なぜ+1をしているのでしょうか？普通にN÷2ではダメなんでしょうか 解説お願いします
- 締切済み
- C・C++・C#
- 探索プログラムの速さの計算方法を教えてください。
以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。
- 締切済み
- 情報処理技術者