2文探索法の平均回数

質問

平均比較回数でいきなりlogとかでてきますが、なぜでしょうか？平均といえば2で割るしかわからない私には理解不能です。どうぞお教えください

回答No.1

elttac · ベストアンサー

「二分探索」のことですね。では，お答えします。

　二分探索のポイントは，文字どおり，「半分半分にする」ことです。具体的な数で考えてみます。アルゴリズムの概略を追うので，細かい点はあまり考えませんが，これは気にしなくても大丈夫です。
【16 個から探す場合】
16 個の半分→8 個
8 個の半分→4 個
4 個の半分→2 個
2 個の半分→1 個
で，4 回です。
【65,536 個から探す場合】
65,536→32,768→16,384→8,192→4,096→2,048→1,024→512→256→128→64→32→16→8→4→2→1
で，16 回です。

　さて逆に，「m 回の比較で何個から絞り込めるか」を考えます。1 回探索回数が増えると，2 倍の探索対象から絞り込むことができるのはよろしいでしょうか。
　たとえば，4,096 個から絞り込める探索回数より 1 回多いと，8,192 個から絞り込めるということです（上の例をもう一度ご覧ください）。
　具体的には，
　- 1 回の探索で 2 個から絞り込めます
　- 2 回の探索で 4 個から絞り込めます
　- 3 回の探索で 8 個から絞り込めます
　- 4 回の探索で 16 個から絞り込めます
　- 5 回の探索で 32 個から絞り込めます
　- 6 回の探索で 64 個から絞り込めます
　- 7 回の探索で 128 個から絞り込めます
　- 8 回の探索で 256 個から絞り込めます
ということがおわかりでしょうか。これを式で表すと，m 回の探索回数で，2^m（2 の m 乗）個から絞り込めるということです。つまり，2^m 個からの探索回数は m 回です。

　ここで，対数を登場させます。対数は，「真数は底の何乗か」を表すものですから，
　- 8 の，底を 2 とした対数は 3（2^3 ＝ 8）
はよろしいでしょうか。では，「2^m の，2 を底とした対数」はいくらかというと，「2^m（真数）は 2（底）の m 乗」なので，「m」になります。これは，対数の底を 2 として，
　　log 2^m ＝ m
と書けるでしょう。
　ですから，探索対象が 2^m 個のとき，比較回数は log 2^m，すなわち m 回になります。
　では n 個から探索する場合はというと，同様に
　　log n [回]
になるはずです。
　二分探索では，「1 回増えるたびに 2 倍の探索範囲から探せる」，すなわち，2^m の m が 1 増えます。この，m（指数）を取り出す操作が log をとることなので，探索回数に log が出てきます。

　二分探索は，探索対象が倍になっても，回数は 1 回しか増えません。これは，すぐれた方法です。線形探索では，探索対象が倍になると，回数も倍になるでしょう。

　以上，おわかりいただけたでしょうか。

回答No.2

tatsumi01

２分探索法ですね。
簡単のため、３２個の中を探索する例を考えます。半分づつにしていけば、３２，１６，８，４，２の中でどちらの半分にあるかですから、５回の探索です。
これが１２８個の中からだと、１２８，６４，３２，１６，８，４，２と、７回の探索になります。
つまり、全個数をＮとすれば探索回数はｌｏｇ２（Ｎ）です。平均とあるのは、Ｎが丁度２のべき乗にはなっていないとき、運不運があるので、それを平均として考えるという意味でしょう。