- ベストアンサー
探索問題
ｎ個のデータがあり，その中から与えられたキー を持つデータを探索するとき,最大計算時間の下界が Ω(log ｎ)であることを証明したいのですが,どうしても わかりません．どのようにしたらよいかどなたか教えて 下さい．よろしくお願いします．
- bulgarian
- お礼率50% (11/22)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ｎ個のデータの並び方によると思います。データを並べる時ハッシュ関数で検索できるように入れるかインデックスを付けておけばデータの検索はＯ(1)です。 非常に便利な検索法なので下記単語でインターネット検索すればたくさん出てきますので探して下さい。 ハッシュ Ｏ 検索
その他の回答 (1)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
n個のデータがデタラメにならんでいたら、先頭から順に調べるしかないのだから時間計算量はΟ(n)ですけど。 前提がまちがっていませんか? 昇順に並んでいたら二分検索によってΟ(log n)となります。
関連するQ&A
- 二分探索の平均探索回数
こんにちは、 二分探索の最大探索回数が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に近づいていきます。 考え方の間違っている箇所の指摘をお願いします。
- 締切済み
- その他（プログラミング・開発）
- 二分探索アルゴリズムの問題の解法
二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。
- 締切済み
- その他（プログラミング・開発）
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- 探索プログラムの速さの計算方法を教えてください。
以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。
- 締切済み
- 情報処理技術者
- 二分探索のアルゴリズム
分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。
- ベストアンサー
- 科学
- 基本情報技術者での質問です。
問題 ５００個の要素をもつ配列を線形探索するとき、探索キーと配列中の要素との平均比較回数をAとする。 また、昇順に整列された５００個の要素をもつ配列を2分探索するとき、探索キーと配列中の要素との平均比較回数をBとする。 このとき、AはBの約何倍か。ここで、探索キーと一致する要素が、配列中に必ず存在するものとする。 答えは３１倍なんですが。 自分の解釈としては、まず線形探索の最大比較回数＝n この場合だと500です。 この場合2分探索の最大比較回数＝（ｌｏｇ２Ｎ＋１回） を割れば何倍かがでてくるであっていますか？？ それとバカな質問ですいません高校のときにlogをならっておらず いまさら数学の先生がいなく理解にくるしんでいます。 (logとこの自分が考えてる解き方であっているか)回答おねがいします。
- 締切済み
- その他([技術者向] コンピューター)
- 基本情報技術者での質問です。
問題 ５００個の要素をもつ配列を線形探索するとき、探索キーと配列中の要素との平均比較回数をAとする。 また、昇順に整列された５００個の要素をもつ配列を2分探索するとき、探索キーと配列中の要素との平均比較回数をBとする。 このとき、AはBの約何倍か。ここで、探索キーと一致する要素が、配列中に必ず存在するものとする。 答えは３１倍なんですが。 自分の解釈としては、まず線形探索の最大比較回数＝n この場合だと500です。 この場合2分探索の最大比較回数＝（ｌｏｇ２Ｎ＋１回） を割れば何倍かがでてくるであっていますか？？ それとバカな質問ですいません高校のときにlogをならっておらず いまさら数学の先生がいなく理解にくるしんでいます。 (logとこの自分が考えてる解き方であっているか)回答おねがいします
- 締切済み
- 数学・算数
- 計算量の下界の計算
ある論文中の回路計算量の下界を求めようと思うのですが、どうも計算がうまくいかないので知恵をお貸しください。 l=√(k)(切り捨て) p=10√(k)log_{2}n(切り上げ) m=(p-1)^{l}*l! この時、size(C)・m^2・(n-l-1)Choose(k-l-1)≧(n)choose(k) という式からsize(C)の下界がn^{Ω(√(k))}と定まるらしいのですが、この導出がわからないのです。 Ωは下界オーダーの記号です。 size(C)≧～という式にしてこの右辺がn^{Ω(√(k))}で表せる式になればよいと思うのですがいまいちうまくいきません。 お分かりの方がいらっしゃいましたら教えていただけると幸いです。 よろしくお願いします。
- 締切済み
- 数学・算数
- 線形探索について
C言語の線形探索の課題なんですが ５つの整数を入力して その入力した値からみつけたい値を探索する課題なのですが #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) return (-1); /* 探索失敗 */ if (a[i] == key) return (i); /* 探索成功 */ i++; } } int main(void) { int i, ky, idx; int x[4]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); } printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); } ここまではわかるのですが、 x[0]=99 x[1]=99 x[2]=88 x[3]=99 x[4]=22 と入力したときに 99は 1番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？
- ベストアンサー
- C・C++・C#
- 情報処理で出てくる「log」とは
情報処理で出てくる「log」がよくわかりません。 どういう意味でしょうか？ 【例１】 logaM=n 【例２】 blogaM 【例３】 データ探索で出てくる探索回数のlog 解説を見ても、計算方法等の詳しい説明や、logの説明がないため、 よくわかりません。 初心者でもわかりやすいように、教えていただけないでしょうか。 お願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
