アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。
/*
2分探索
*/
#include <stdio.h>
/*--- 要素数nの配列aからkeyと一致する要素を2分探索 ---*/
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になるんでしょうか?
詳しく教えてください。
よろしくお願いします。
No.5
- 回答日時:
No.2、No.4です。
No.2の補足質問にお答えします。
No.4を見ていただくと大体分かると思いますが。
>> 平均ループ回数はデータが半分見つかる3.27回です。
> というところですが、なぜ3.27というのがでてくるのですか?
1回×1個+2回×2個+3回×4個+4回×8個=49回
平均は15で割ると49/15=3.27回です。
>> log(2)15≒3.91と比べると差は0.64
> で差ってどうして出すのですか?
3.91-3.27=0.64のことですね。ちょっと紛らわしかったですね。
差が1に近いということを示したかっただけです。
No.4ではきちんと書いておきました。
> 理論値は(logn)-1というのは、常識で知っている物ですか?
はい。2分探索を完全にマスターしたと言うには、知っているべきでしょうね。
ちなみに基本情報技術者試験では出題範囲に入っています。
No.4
- 回答日時:
No.2です。
> データ数nに対してlogn回になるというところで
> logn自体になるのはどうしてですか?
> ちなみに10の場合はどう説明できますか?
あまり小さいnで議論すると誤差が大きくなります。
1023で考えて見ましょう。
1回ループするごとに探索範囲が半分になっていきます。
探索が全て完了するために必要な回数をmとすると、
2^m≧1023が成立すればいいことになります。
両辺の2の対数をとるとm≧log1023ということになります。
一般化すると最大探索(ループ)回数≧lognとなります。
平均探索(ループ)回数は最大探索(ループ)回数-1です。
半分探し終わったところが平均ですから最大-1ということです。
実際にn=1023で半分半分で計算してみると最大10回、平均9.01回になります。
理論値はlog1024=10を使って最大約10回、平均約9回でほとんど一致します。
No.3
- 回答日時:
#1です。
処理の回数が、2倍、4倍、8倍と倍々になっていくときは、「2のn乗」と指数を使うと思います。
今回の二分探索は、半分ずつデータの数nを絞り込んでいくわけですから、指数関数の逆関数の対数になるというわけです。
No.2
- 回答日時:
簡単な例で説明します。
15個のデータがあるとします。
2分割づつしていきますから、確率で考えると
1回目で見つかるのは1個
2回目で見つかるのは2個
3回目で見つかるのは4個
4回目で見つかるのは8個
ですね。これで全部見つかります。
最大ループ回数は4回ですが、
平均ループ回数はデータが半分見つかる3.27回です。
これはlog(2)15≒3.91と比べると差は0.64になります。
データ数を増やした時の平均ループ回数の理論値は(logn)-1ですが、
これをO記法で表すと(-1)が無視されてO(logn)となります。
ちなみに、最大ループ回数の理論値はlognで当然これもO記法でO(logn)です。
言うまでもないことですが上記ではlogの底の2を省略しています。
この回答への補足
ありがとうございます。
>平均ループ回数はデータが半分見つかる3.27回です。
というところですが、なぜ3.27というのがでてくるのですか?
log(2)15≒3.91と比べると差は0.64
で差ってどうして出すのですか?
理論値は(logn)-1というのは、常識で知っている物ですか?
質問が多くてすみません。初心者なのでよろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 O(N*logN)よりN=8の時、 O(N*logN) のOはオーダー記号と推察されますから 8*l 6 2022/04/06 18:54
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# プログラミングのペーパーテスト 実行結果を表示せよ #include <stdio.h> int h 1 2022/07/09 15:27
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
UWSCに制限時間を付けたいです
-
エクセルの当番表を作っていま...
-
画面を強制的に再描画させる方法
-
プログラムの機能を変えずに高...
-
VBA for i=1 to lastrow
-
UWSCの終了の仕方
-
DoEventsが必要な理由について
-
どなたかこのプログラミングを...
-
テキストボックスの名前に変数...
-
vb.netからエクセル関数書き込み
-
pythonでファイルのコメント行...
-
GIFアニメをループさせたくない
-
無限ループの防ぐ方法
-
WHILE (CHKIMG(”A.bmp”)=FALSE)...
-
UWSCのスクリプトで行き詰って...
-
uwsc条件並列とそれの抜け方
-
VBAでの一時停止と再開の方法
-
VBAで3秒だけ時間を止めたい
-
配列について
-
レインボー色ってどうやって表...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
画面を強制的に再描画させる方法
-
VBAで3秒だけ時間を止めたい
-
VBAでの一時停止と再開の方法
-
どなたかこのプログラミングを...
-
Escキーを押すと、中断する時と...
-
UWSCの終了の仕方
-
エクセルの当番表を作っていま...
-
VBA for i=1 to lastrow
-
「偶数・奇数の和」のフローチ...
-
アクティブセルから、A列最終行...
-
DoEventsが必要な理由について
-
vb.netからエクセル関数書き込み
-
GIFアニメをループさせたくない
-
DOSコマンドのループ内のTIMEコ...
-
範囲指定したセルを1つずつ飛...
-
流れ図(フローチャート)が分か...
-
乱数の桁数指定、または範囲指定。
-
テキストボックスの名前に変数...
-
CSVファイルの特定の行だけを読...
-
vbscriptでIE自動入力(途中で...
おすすめ情報