• ベストアンサー

アルゴリズム: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になるんでしょうか？ 詳しく教えてください。 よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • sunasearch
  • ベストアンサー率35% (632/1788)
回答No.1

3,4,6,7,8,9はすべて、 ループの中で実行され、ループの回数が、 データ数ｎに対してlogn回になるからです。

koton_
質問者

補足

ありがとうございます。 データ数ｎに対してlogn回になるというところで logn自体になるのはどうしてですか？ ちなみに10の場合はどう説明できますか？

その他の回答 (4)

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.5

No.2、No.4です。 No.2の補足質問にお答えします。 No.4を見ていただくと大体分かると思いますが。 >>　平均ループ回数はデータが半分見つかる3.27回です。 >　というところですが、なぜ3.27というのがでてくるのですか？ １回×１個＋２回×２個＋３回×４個＋４回×８個＝４９回 平均は１５で割ると４９／１５＝３．２７回です。 >>　log(2)15≒3.91と比べると差は0.64 >　で差ってどうして出すのですか？ 3.91-3.27=0.64のことですね。ちょっと紛らわしかったですね。 差が１に近いということを示したかっただけです。 No.4ではきちんと書いておきました。 >　理論値は(logｎ)－１というのは、常識で知っている物ですか？ はい。２分探索を完全にマスターしたと言うには、知っているべきでしょうね。 ちなみに基本情報技術者試験では出題範囲に入っています。

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.4

No.2です。 >　データ数ｎに対してlogn回になるというところで >　logn自体になるのはどうしてですか？ >　ちなみに10の場合はどう説明できますか？ あまり小さいｎで議論すると誤差が大きくなります。 １０２３で考えて見ましょう。 １回ループするごとに探索範囲が半分になっていきます。 探索が全て完了するために必要な回数をmとすると、 2^m≧1023が成立すればいいことになります。 両辺の２の対数をとるとm≧log1023ということになります。 一般化すると最大探索(ループ)回数≧logｎとなります。 平均探索(ループ)回数は最大探索(ループ)回数－１です。 半分探し終わったところが平均ですから最大－１ということです。 実際にn=1023で半分半分で計算してみると最大10回、平均9.01回になります。 理論値はlog1024＝10を使って最大約10回、平均約9回でほとんど一致します。

  • sunasearch
  • ベストアンサー率35% (632/1788)
回答No.3

＃１です。 処理の回数が、２倍、４倍、８倍と倍々になっていくときは、「２のn乗」と指数を使うと思います。 今回の二分探索は、半分ずつデータの数ｎを絞り込んでいくわけですから、指数関数の逆関数の対数になるというわけです。

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.2

簡単な例で説明します。 １５個のデータがあるとします。 ２分割づつしていきますから、確率で考えると １回目で見つかるのは１個 ２回目で見つかるのは２個 ３回目で見つかるのは４個 ４回目で見つかるのは８個 ですね。これで全部見つかります。 最大ループ回数は４回ですが、 平均ループ回数はデータが半分見つかる3.27回です。 これはlog(2)15≒3.91と比べると差は0.64になります。 データ数を増やした時の平均ループ回数の理論値は(logｎ)－１ですが、 これをＯ記法で表すと(－１)が無視されてＯ(logｎ)となります。 ちなみに、最大ループ回数の理論値はlogｎで当然これもＯ記法でＯ(logｎ)です。 言うまでもないことですが上記ではlogの底の２を省略しています。

koton_
質問者

補足

ありがとうございます。 ＞平均ループ回数はデータが半分見つかる3.27回です。 というところですが、なぜ3.27というのがでてくるのですか？ log(2)15≒3.91と比べると差は0.64 で差ってどうして出すのですか？ 理論値は(logｎ)－１というのは、常識で知っている物ですか？ 質問が多くてすみません。初心者なのでよろしくお願いします。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • bsearch関数の内容について

    stdlib関数のbsearch関数で、次のことを教えてください。 void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,　int (*compar)(const void *, const void *)) { size_t pl = 0; /* 探索範囲先頭の添字 */ size_t pr = nmemb - 1;/* 探索範囲末尾の添字 */ char *x = (char *)base;/*なぜchar *にキャスト？*/ if (nmemb > 0) { while (1) { size_t pc = (pl + pr) / 2;/* 探索範囲中央の添字 */ int comp = compar((const void *)&x[pc * size], key); ~~~~~~~~~~~~~~~~~~~~~~~~~~~ /*なぜsizeを掛けるのか？*/ if (comp == 0) /* 探索成功 */ return (&x[pc * size]); else if (pl == pr) break; else if (comp < 0) pl = pc + 1;/* 探索範囲を後半に絞り込む */ else pr = pc - 1;/* 探索範囲を前半に絞り込む */ } } return (NULL);/* 探索失敗 */ }

  • 線形探索について

    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番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？

  • 二分探索木のheightを見つけるアルゴリズム2

    誠に申し訳ありません。 前回下記のとおり質問して、 二分探索木のheight(高さ?)を見つけるアルゴリズム http://www.okweb.ne.jp/kotaeru.php3?q=710354 丁寧な回答を頂き、自分では解決したと思い、 お礼も差し上げたのですが 私のメソッドは正しく動いていないようです。 どうやら私が間違って解釈してしまったようです。 public int height() { return height(root, 0); } public int height(IntBSTNode p, int h) { if (p != null && p.right != null && p.left != null) { if (p.left.key < p.right.key) return height(p.right, h+1); else return height(p.left, h+1); } return h; } 何を思ったのか、 if (p.left.key < p.right.key)では 左と右の「値」を比較しています。 なので入力した値によって「たまたま」動いてました。 本当は左と右の「height」を比較しなければならなかったのに…。 if (p != null && p.right != null && p.left != null)の条件もこれでいいのか…。 いろいろやってみたのですが行き詰まりました。 どうか、更にヒントを下さい。お願いします。

    • ベストアンサー
    • Java
  • アルゴリズム(2分探索木)の問題について

    ２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。

  • 二分探索アルゴリズムの問題の解法

    二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。

  • 線形探索と二分探索

    線形探索と二分探索のプログラムを作成中です。 自力(本やwebに落ちているサンプルを参考にして)でここまで作りましたが正直自信がありません。どうかお願いします。 #include <stdio.h> #define ARRAYI1_MAX sizeof(array1) #define ARRAYI2_MAX sizeof(array2) //int binary_search(int*,int,int); //二分探索関数のプロトタイプ宣言 int liner_search(int*,int,int); //線形探索関数のプロトタイプ宣言 void main(void) { int array1[]={2,3,5,8,12,20,32,52}; int array2[]={22,34,65,66,12,33,43,5,1}; int result,key; printf("探す文字を入力して下さい。\n"); sacnf("%d",&key); result=liner_search(array1,ARRAYI1_MAX,key); if(result<0){ printf("見つかりませんでした\n");} else{ printf("%d番目に見つかりました\n",result);} } //線形探索 int liner_search(int*array,int num_array,int key) { int i=0; for(i=0;i<result;i++) } /*二分探索 int binary_search(int*array,int num_array,int key) { }*/

  • C言語の二分探索法について質問です。

    C言語の２分探索法について質問です。 以下のようなプログラムを作りたいのですが，途中でよく分からなくなってしまいました。添削お願いします。 入力された整数を配列に順次格納する(必ず昇順になるように入力)。0が入力された時に整数の入力を終了し， 次に入力された数字を二分探索によって配列から探索し，その配列の添字番号を出力するプログラムを作成せよ。 実行例 (例1) (例2) 9 ←入力 1 ←入力 7 ←入力 42 ←入力 69 ←入力 99 ←入力 31 ←入力 13 ←入力 93 ←入力 0 ←入力 59 ←入力 5 ←入力 17 ←入力 not found ←出力 0 ←入力 7 ←入力 2 ←出力 プログラム #include <stdio.h> #include <stdlib.h> #define ARRAY_SIZE 10 int swap(int a, int b) { int c; c = a; a = b; b = a; } int main(void) { int array[] ; int low = 0; int high = n - 1; int mid; int key; int i, j, n; int data; struct node *p; puts("整数を入力して下さい。"); for(i = 0; i < ARRAY_SIZE && scanf("%d", array + i) == 1; ++i){ if(array[i] == 0) break; for(j = i; j > 0 && array[j-1] > array[j]; j--) swap(array[j-1], array[j]); } n = i; puts( "探索する値を入力して下さい" ); scanf( "%d", &key ); while( low <= high ) / { mid = (low + high) / 2; if( array[mid] == key ) { return ; } else if( array[mid] < key ) { low = mid + 1; } else { high = mid - 1; } } puts( "not found" ); return 0; }

  • 多分探索木の高さを測定する関数について

    今、多分探索木の高さを測定する関数を作成していますが、行き詰ってしまいました。 二分探索木の深さを求める関数を改良すればよろしいと思ったんですが。 どうもうまくいきません。助言お願いします。 以下、二分探索木の高さを求める関数を貼っときます。 int compute_height(NODE *root){ int lh=0, rh=0, Max; if(root==NULL){ return 0; } lh=compute_height(root->left)+1; rh=compute_height(root->right)+1; if(lh > rh){ return Max=lh; }else{ return Max=rh; } } 多分木探索の構造体定義は以下のようです typedef struct node{ 　int key[16]; //キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[17] ; // 子への参照欄 } NODE

  • 多分探索木の昇順出力

    多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが 途中でセグメントエラーが起きてしまいます。 void out_MS(NODE *p){ int i,n=0 ; for(i = 0; i <= p->nkeys; ++i) if (p->refs[i] != NULL) out_MS(p->refs[i]) ; while(p->keys[n+1]!='\0'){ printf("No:%3d \"%s\"\n",count,p->keys[n]) ; count++; n++; } } この、多分木に使われている、構造体は以下のとおりです #define KK 16 typedef struct node{ // 多分探索木、B(B*)木構造体 char *keys[KK] ; // キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[KK + 1] ; // 子への参照欄 } NODE ; この構造体に以下の関数で、10万要素の単語（ランダム）に追加していきます。 int add(NODE *root, char *inv) { NODE *now , // 当該節 *prnt ; // nowの親節 int pos ; // 節内のキーの追加位置 prnt = now = root ; while(now != NULL) { // キーの探索 pos = binsearch(now->keys, now->nkeys, inv) ; // 二分探索 if (pos < now->nkeys && strcmp(inv,now->keys[pos])==0) // 探索値はある return FLS ; // 追加の必要なし if (now->nkeys == KK) { // 当該節に無い、節内に空きが無い prnt = now ; now = now->refs[pos] ; // 子の節へ }else if (pos <= now->nkeys) // 当該節に無い－追加位置が範囲内 break ; } if (now != NULL) // 当該節は在る store_key(now, inv, pos, &(now->nkeys)) ; // 当該節にキーを追加格納 else { // 当該節は無い－新規生成 if (now != root) { // nowは根ではない now = set_key(KK, inv) ; // キーを新節に格納 prnt->refs[pos] = now ; // 親節の参照欄に新節の番地を格納 }else return FLS ; } return 1 ; } 上記の関数で使われている、store_key set_key binserch の関数は以下のとおりです void store_key(NODE *trgt, char *inv, int pos, int *nkeys) { if (trgt->keys[pos] == INTV) // 当該位置は空 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 else { // 当該位置に入っている shift_element(trgt, 'R', pos, *nkeys) ; // 要素を移動 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 } ++*nkeys ; return ; } int binsearch(char *array[], int size, char *inv){ // 二分探索 int mid, // 当該位置 low, // 探索範囲の下限 high ; // 探索範囲の下限 if (size == 0) // キーは格納されていない return 0 ; if (strcmp(inv,array[0])<0) // 探索範囲以下 return 0 ; if (0 < strcmp(inv,array[size - 1] )) // 探索範囲以上 return size ; low = 0 ; // 下限設定 high= size - 1 ; // 上限設定 while(0 <= high - low) { // 二分探索本体 mid = (high + low) >> 1 ; // 中間位置を調べる if (strcmp(inv,array[mid])==0) // 入力値が一致したとき return mid ; if (strcmp(inv,array[mid])<0) // 入力値が小さいとき high = mid - 1; else // 入力値が大きいとき low = mid + 1 ; } return low ; } NODE *set_key(int size, char *key) { NODE *new ; new = crt_node(size) ; // 節の生成 new->keys[0] = strdup(key) ; // 配列の先頭に入力値を格納 new->nkeys = 1 ; // 節内の実際の要素数 return new ; } ぜひ、お力をお貸しください。よろしくお願いします。

  • 二分探索アルゴリズムの終了条件について

    いつもお世話になっています。 現在他人のプログラムを読解する力をつけようと 訓練しています。 以下の文はとあるアルゴリズム本の２分探索の個所を 抜粋したものです。 int bs(*array, size, mokuteki) { 　　ue=size-1, sita=0; 　　while(1){ 　　　　naka=(sita+ue) / 2; 　　　　if(array[naka] == mokuteki) 　　　　　　return ARU; 　　　　else if(sita > ue) //・・・・・・★ 　　　　　　return NAI; 　　　　else { 　　　　　　if(array[naka] < mokuteki) 　　　　　　　　sita = naka+1; 　　　　　　else 　　　　　　　　ue = naka-1; 　　　　} 　　} } ここで★部分の終了条件なのですが、なぜ 　　sita >= ue でいけないのか自分では理解できません。 要はsitaとueが同じ値になり、目的値が見つからなかった のに再度ループする必要があるのか？、ということです。 特に明確な答えはいりませんがぜひ ご意見を聞かせてください。 ちなみに作者は 「ue==sitaの状態ならば、幅１の範囲がありますから 　ループをもう一回実行する必要があります。」 と書いています。私には理解できません。 ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」 という本です。だいたい一通り読みましたが読んでて 楽しいしわかりやすいし良書だと思います。高価ですが・・・。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する