締切済み ２分探索法の平均比較回数 2004/10/23 11:25 [log_2 N]だということはよく聞くんですが、どうやって導出するんでしょうか？ みんなの回答 （1） 専門家の回答 みんなの回答 noname#16258 2004/10/23 13:40 回答No.1 logを計算で出すのではなく、～以上～以内で回数がわかります。 2以内は1回 4以内は2回 8以内は3回 16以内は4回 32以内は5回 64以内は6回 128以内は7回 256以内は8回 512以内は9回 1024以内は10回 例えば800は512以上1024以内なので10回となります。 質問者 補足 2004/10/23 13:44 それは、最大比較回数[log_2 N]+1を導く議論であるような気がします…。 区間の真ん中の値と比較したときにうまく一致して早めに探索終了してしまうこともあると思うのです。 そのことも考慮した上で、確率やら何やら色々計算して平均比較回数を計算した結果が[log_2 N]であるように思うんですが、それが導けないでいます。m(__)m 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 カテゴリ ビジネス・キャリア職業・資格情報処理技術者 関連する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に近づいていきます。 考え方の間違っている箇所の指摘をお願いします。 2文探索法の平均回数 平均比較回数でいきなりlogとかでてきますが、なぜでしょうか？平均といえば2で割るしかわからない私には理解不能です。どうぞお教えください 探索問題 ｎ個のデータがあり，その中から与えられたキー を持つデータを探索するとき,最大計算時間の下界が Ω(log ｎ)であることを証明したいのですが,どうしても わかりません．どのようにしたらよいかどなたか教えて 下さい．よろしくお願いします． 人生100年時代！シニアでも転職できますか？ OKWAVE コラム 整列の比較回数を表す数式でよく見るO(n log n)のOって何ですか タイトルどおりなのですが、数式の(n log n)とO(n log n)では何がちがうのですか。 どなたか教えてください。 ２分探索法 『成功・不成功探索一回の実行時間を求める』 Ｃ言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。 ----------課題---------- 整列されているＮ個のデータに対して、その中にｖがあるかどうかを判断する２分探索プログラムを実行する Ｎの値を10^6、5×10^6、10^7、5×10^7、10^8 と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。 このとき、Ｎと実行時間の関係はどのようになっているか（１００字程度で） Ｎ 成功探索 不成功探索 10^6 ＊＊＊秒 ＊＊＊秒 5×10^6 ＊＊＊秒 ＊＊＊秒 10^7 ＊＊＊秒 ＊＊＊秒 5×10^7 ＊＊＊秒 ＊＊＊秒 10^8 ＊＊＊秒 ＊＊＊秒 ---------------------------------------- ～↑を元に作成したプログラム（成功探索の場合）～ #include <stdio.h> #include <stdlib.h> #include <time.h> #define T 1000000 #define N 100000000 int a[N]; int main(void) { clock_t t1,t2; int t; int i; int l, r, k, v, m; for (i = 0; i < N; i++) a[i] = i; t1=clock(); for (t = 0; t < T; t++) { v = rand() % N; l=0; r=N-1; k=-1; while (r >= l) { m = (l+r)/2; if (v == a[m]) { k=m; break; } if (v < a[m]) r = m-1; else l = m+1; } } t2=clock(); printf("cpu time=%10.6f[micro sec]\n",(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T)); return 0; } ↑a[i]すべてに０～Ｎ－１を代入し、ｖにランダムに０～Ｎ－１の値を代入する。２分探索法で、ｖ＝a[i]となったら終了する。 実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位：マイクロ秒 として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。 ↑のプログラムをそれぞれのＮで実行したところ Ｎ＝ 10^6で実行・・・1.016 0.891 0.969 1.155 1.14 [micro sec] 5×10^6で実行・・・1.422 1.500 1.563 1.250 1.406 1.297 10^7で実行・・・1.750 1.360 1.37 1.407 1.672 1.531 5×10^7で実行・・・1.859 1.797 1.812 1.800 10^8で実行・・・2.062 2.140 2.320 2.500 このような結果になりました。 これで正しいのでしょうか？もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか？ でも、Ｎが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。 次に 不成功探索では↑のプログラムの 乱数ｖのところを変化させて v=rand() % N；という箇所を ｖ＝Ｎ;としました。 a[i]には０～Ｎ－１が入っているので、ｖ＝Ｎとすれば必ず不成功になるはずですよね？ こうして実行してみると Ｎ＝ 10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても 0.719 0.54 0.625 0.534 [micro sec] に近い値ばかり出てしまい、正しい値とは到底思えません。 不成功探索は成功探索より時間がかかるはずですよね？なのになぜこのようになってしまったのでしょうか？ 後、Ｎと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか？ こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。 長々とスイマセン。 少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。 二分探索のアルゴリズム 分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。 平均について 数学ではなく統計学が正式な分類かもしれませんが。 （ｘ１＾２＋ｘ２＾２＋ｘ３＾２＋・・・＋ｘｎ＾２）／ｎ の平方根（←アとする） は、何と呼ばれるのでしょうか？ 「２乗平均」などと呼びそうにも思えるのですが。 明後日の試験のための過去問の中で、 Ａ＝ｌｏｇ（ｘ１）＋ｌｏｇ（ｘ２）＋ｌｏｇ（ｘ３）＋・・・＋ｌｏｇ（ｘｎ） とする時の１０＾（Ａ／ｎ）（←イとする） ウ：相乗平均 エ：調和平均 ア～エの中から、「平均と言えないものを選べ」という問題です。 私はイが答だと考えていますが、アは何と呼ばれるのか教えて下さると幸いです。 アが答だとしたら、イは何と呼ばれるのでしょうか？よろしくお願いします。 逐次検索と平均比較回数 アルゴリズムの解析について勉強しています。アルゴリズムに関して全くの初心者なので、アドバイスをいただけるとありがたいです。 今回、課題で出されたのですが、例として、n個の配列(array)があります。 そのArrayが [ 1, 9, 7, 4, 3, 8, 2]とソートされていない状態だとすると、平均比較回数は、 (n+1)/2と定義されています。 もし、探したいindexが 4 だとすると、４回探さなきゃいけないということだし、もし、探したいindexがn番目というケースもあります。 上記のケースは、探したいindexが１個というケースですが、 もし、n個の配列に要素が２回出現した場合、(nは必ず偶数の配列で、要素が１個だけしかないということはありません。あと、２連続で要素が出現することもありません。それぞれの要素はバラバラに散らばっています） 1. 探したい1indexが1番目の場合、2/n*1 2. 2番目の場合、 { (n-2)/n*2/(n-1) } * 2 3. 3番目の場合、 { (n-2)/n* (n-3)/(n-1)* 2/(n-2) } * 3 ...... となっていくと、教授に言われ、２回目のindexの出現は気にしなくていいと言われました。 となると、探したいindexがn/2までを考慮すればいいとなりますよね？ 以上のことをΣなり、!なりを使って表したいたいのですが、できるでしょう？ 長くなりましたが、よろしくお願いします。 二分木探索でN番目の要素を探索するには 二分木探索で特定の要素の有無を調べる関数は作れたのですが、Ｎ番目に小さい要素を見つける方法が思い浮かびません。 二分木探索でN番目に小さい(昇順でＮ番目)の要素を探索するにはどのような手法があるのか教えて頂けないでしょうか？ よろしくお願い致します。 自然数を５進法で表すには？？ 【問】 xは10桁の自然数で、その最高位の数は３である。このxを５進法で表すと何桁となるか。 ただし、log10(2)=0.3010 log10(3)=0.4771とする。 という問題なのですが、自分で考えてみて 3*10^9≦x≦4*10^9 log10(3)+9≦log10(x)≦log10(4)+9 9.4771≦log10(x)≦9.6020 ……(1) 5^(n-1)≦x≦5^n n-1≦log5(x)≦n ・ ・ ・ というとこまで考えたのですが、この先どうすればよいかわかりません。 よろしくお願いします。 二分探索について 今、学校の宿題で二分探索の課題が出てるのですがよくわかりません。どなたか教えていただけないでしょうか？内容は11,24,36,44,58,64,77の7つの数字の中で、58を二分探索を使って探し出すのですが、何回の比較で58を探し出したかをmsgboxを使って表示させるプログラミングを考えるというものです。よろしくお願いします。 二分探索木 下のプログラムはコンパイルはできたのですが、実行すると「セグメンテーション違反です」とでました。デバッガをしてみたら、 Program received signal SIGSEGV, Segmentation fault. 0x080483e8 in inorder (root=0x0) at nibun.c:12 12 inorder(root->llink); と表示されましたが解決方法が分かりません。どのように直せば、エラーを出さずに実行できるようになるか教えてください。 #include<stdio.h> #include<stdlib.h> typedef struct node *NodeP; typedef struct node { int data; NodeP llink, rlink; } Node; void inorder(NodeP root) { inorder(root->llink); printf(" %d", root->data); inorder(root->rlink); } NodeP newNode(int val) { NodeP newp = (NodeP) malloc (sizeof(Node)); newp->data = val; newp->llink = NULL; newp->rlink = NULL; return newp; } void insert(NodeP *root, int val){ NodeP curr,prev; if(*root == NULL) *root = newNode(val); else{ curr = *root; do{ prev = curr; if ( val < curr->data) curr = curr->llink; else if ( val > curr->data) curr = curr->rlink; else return; }while(curr!= NULL); if(val > prev->data){ prev->llink = newNode(val); } else{ prev->rlink = newNode(val); } } } NodeP createBSTree(void){ int i,n,val; NodeP root=NULL; printf("Number of Nodes:"); scanf("%d",&n); for (i=1;i<=n;i++){ printf("Node[%d]: ",i); scanf("%d",&val); insert(&root,val); } return root; } int main(){ NodeP root=NULL; root = createBSTree(); inorder(root); printf("\n"); return 0; } キャリアについて教えて？修行の成果を示す退職届と転職書類の書き方 OKWAVE コラム マージソートの演算回数について 授業でマージソートはn個の入力に対して、分割にかかる演算回数はlog n(底は2)であると言っていたのですが、どうしてなるかがどうしてもわかりません。 どなたかわかるかた、よろしくお願いします。 平面と平面の比較法について 最小二乗平面で（x1,y1,z1）(x2,y2,z2) (x3,y3,z3)(x4,y4,z5) (x5,y5,z5) (x6,y6,z6)の点で平面ｚ1のa1 b1 c1を導出し 同じく最小二乗平面で (x3,y3,z3)(x4,y4,z5) (x5,y5,z5) (x6,y6,z6)(x7,y7,z7) (x8,y8,z8)の点で 平面z2のa2 b2 c2を導出したところまでできています。 そこでz1とz2は同じ平面かどうか判別するには どうしたらいいのでしょうか？ もしご存知の方いらっしぃましたらお願いします 統計力学 スターリングの公式を使って logΩ(E)=NlogV+(3/2)Nlog(2E/3N)+・・・・・ を導出せよ。 ・・はVとEにはよらない項を表す。 Ω(E)=(1/N！)*(V^N/h^3N)*{π(2π^2mE)^(3/2)N-(1/2)}/Γ{(3/2)N+1} となっている (^n:n乗) この問題が分からないんで、分かる方は教えてください。お願いします 区分求積法 区分求積法からlim(n->∞)1/nΣ(k=0,n-1)1/{1+(k/n)}は∫(0->1)1/(1+x)dxでlog2 となるのは、分かりますが、 (1)lim(n->∞)(1/n)^2Σ(k=0,n-1)1/{1+(k/n)}は 単純にlog2/nとして、0にはならないと思います。 こんなことをしたら、区分求積法をわかっていないといわれてしまう と思います。これを正しく解くにはどうしたら良いでしょうか。 (2)lim(n->∞)1/nΣ(k=0,n-1)1/{1+(k/n)*((k-1)/n)}も 単純に(k-1)/nの部分をk/nとはできないと、思いますが、 どうしたらよいでしょうか。 よろしく、お願いします。 探索プログラムの速さの計算方法を教えてください。 以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。 ＡＩＣと対数尤度 このサイト http://tswww.ism.ac.jp/kawasaki/nagoya2001summer/sld074.htm を参考にして、ＡＩＣについて現在勉強しています。 Ey[log f(Y)]を導出するために、未知の分布g()を経験分布関数g^()で近似して、 Ey[log f(Y)] ＝ ∫log f(y)g(y)dy ≒ ∫log f(y)g^(y)dy ≒ 1/N Σlog f(y) と導出されるそうなのですが、なぜ未知の分布を経験分布関数で近似できるのか 分かりません。分かる方、教えてください。 線形探索と２分探索 「線形探索」と「２分探索」について、それぞれ違いが分かるように説明しなさい。またそれぞれがもう一方より優れているのはどのような場合か、その理由とともに示しなさい。 という問題の説明がうまくできません。 どうしたら分かりやすく説明できるでしょうか？ 二分探索木を用いての探索 Ｃ言語でプログラミングしています。 二分探索木を用いて探索するプログラムなのですが 与えられた値の前後の値（与えられた値より大きく(小さく）てその値 に一番近いもの）を見つけたいのですが分かりません。 いろいろとネット等で調べてみると「挿入してその左右を見る」 となっているのですが…。 普通の二分探索木ではだめなのでしょうか？ よろしくお願いします。 注目のQ&A 「You」や「I」が入った曲といえば？ Part2 結婚について考えていない大学生の彼氏について 関東の方に聞きたいです 大阪万博について 駅の清涼飲料水自販機 不倫の慰謝料の請求について 新型コロナウイルスがもたらした功績について教えて 旧姓を使う理由。 回復メディアの保存方法 好きな人を諦める方法 小諸市（長野県）在住でスキーやスノボをする方の用具 カテゴリ ビジネス・キャリア 職業・資格 弁護士行政書士司法書士社会保険労務士（社労士）公認会計士宅地建物取引主任者（宅建）保育士・幼稚園教諭旅行業務取扱管理者薬剤師・登録販売者調理師・管理栄養士建築士美容師・理容師医師看護師・助産師教員・講師国家公務員・地方公務員簿記情報処理技術者Microsoft認定資格TOEFL・TOEIC・英語検定介護福祉士・ケアマネージャー接客・販売士ファイナンシャルプランナー（FP）自動車・運転免許その他（職業・資格） カテゴリ一覧を見る OKWAVE コラム 突然のトラブル？プリンター・メール・LINE編 携帯料金を賢く見直す！格安SIMと端末選びのポイントは？ 友達って必要？友情って何だろう 大震災時の現実とは？私たちができる備え 「結婚相談所は恥ずかしい」は時代遅れ！負け組の誤解と出会いの掴み方 あなたにピッタリな商品が見つかる！ OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど インターネット回線 プロバイダ、光回線など
補足
それは、最大比較回数[log_2 N]+1を導く議論であるような気がします…。 区間の真ん中の値と比較したときにうまく一致して早めに探索終了してしまうこともあると思うのです。 そのことも考慮した上で、確率やら何やら色々計算して平均比較回数を計算した結果が[log_2 N]であるように思うんですが、それが導けないでいます。m(__)m