みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

2分探索法 『成功・不成功探索一回の実行時間を求める』

C言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。

----------課題----------
整列されているN個のデータに対して、その中にvがあるかどうかを判断する2分探索プログラムを実行する
Nの値を10^6、5×10^6、10^7、5×10^7、10^8
と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。
このとき、Nと実行時間の関係はどのようになっているか(100字程度で)
  N  成功探索  不成功探索
 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]すべてに0~N-1を代入し、vにランダムに0~N-1の値を代入する。2分探索法で、v=a[i]となったら終了する。
実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位:マイクロ秒


として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。

↑のプログラムをそれぞれのNで実行したところ
N=
 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

このような結果になりました。
これで正しいのでしょうか?もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか?
でも、Nが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。


次に
不成功探索では↑のプログラムの
乱数vのところを変化させて
v=rand() % N;という箇所を
v=N;としました。
a[i]には0~N-1が入っているので、v=Nとすれば必ず不成功になるはずですよね?
こうして実行してみると
N=
10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても
0.719 0.54 0.625 0.534 [micro sec]
に近い値ばかり出てしまい、正しい値とは到底思えません。

不成功探索は成功探索より時間がかかるはずですよね?なのになぜこのようになってしまったのでしょうか?



後、Nと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか?
こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。


長々とスイマセン。
少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。

投稿日時 - 2008-10-23 04:32:29

QNo.4422713

すぐに回答ほしいです

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

ざっとプログラム見ましたが、特に問題は無いように見受けられます
そもそも探索ですから(N=16として)
1回目で見つかる場合もあるし、最悪4回目で見つかる、みつからないとなりますよね?(2分探索なので)
ですので平均を計算する必要があります
するとだいたい、o LOG nで検索できるとなります

ちなみに不成功探索ですがv=Nだと1回目の探索ですぐ「ないぞ」とわかってしまうのでだめです
a[i] = i*2;
とでもしておいて(データはすべて偶数)
v = N/2;
ならいいんじゃないですか?

投稿日時 - 2008-10-23 05:39:11

お礼

早速の返答ありがとうございます。とても参考になりました。

確かに、何回も繰り返して、1回目で終了することが多ければ時間は短くなり、逆に最大回数で終了するのが多ければ時間は多くかかってしまいますね。
あれほど差がでるものなのかな?と思っていましたが、納得しました。


不成功探索ですが、色々試してやって見たのですがやはり上手く行きません。
データを偶数にしてvに奇数を入れてやってみましたが同じような値が出てしまいます。


質問なんですが、v=Nの場合なぜ一回目の探索で「ない」と分かってしまうのでしょうか?
常に「r > a[i]」なので、l=m+1をしていってr>lの時終了するので最大回数まで行くと思ったのですが・・・

投稿日時 - 2008-10-23 13:44:09

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(3)

ANo.3

確認しますが、実行環境はなんですか?
linux?、windows?
さらに開発環境はどうですか?
gcc?、visualC?

投稿日時 - 2008-10-24 11:11:37

お礼

色々、ありがとうございます
一応、問題は解決しました…
中途半端な形になって申し訳ないのですがここで締め切らせて頂きます。スイマセン。

投稿日時 - 2008-10-27 00:33:46

ANo.2

>質問なんですが、v=Nの場合なぜ一回目の探索で「ない」と分かってしまうのでしょうか?
>常に「r > a[i]」なので、l=m+1をしていってr>lの時終了するので最大回数まで行くと思ったのですが・・・
あ!、そうですね勘違いしてました
たしかに最大回数いきます
(ついでにV=N/2+1でした)

それでなんですが、10^8だと探索回数は27回なので
たかだた27のループの実行速度はあっというまに終わってしまうので
誤差の範囲内なのでだめでしょう

ちゃんと計測するのなら以下のように
時間測定開始
10000回ループ
 検索する部分
時間測定終了
とやって、測定値を10000で割ったらどうでしょうか?

投稿日時 - 2008-10-23 14:35:49

お礼

時間測定開始
1000000回ループ
 検索する部分
時間測定終了

(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T)

↑として、一応やっています…(先生から同じようなことを言われてループして、そのループした回数を割って平均を出しました)

友達に聞いたら、不成功探索時間は成功探索より短くて良いと言われたんですが・・・
なぜ短くなってしまうのかが分かりません。

投稿日時 - 2008-10-23 19:47:46

あなたにオススメの質問